特殊pell方程的非平凡解与因子分解

wsc810 · 发表于 2010-9-12 15:47:48

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

设n是待要分解的数，P是参数，构造一pell方程 x^2-(n+P^2)*y^2=-n,容易得出此方程有一平凡解， x1=P,y1=1.如果再得出一非平凡解， x2,y2,计算x1y2+x2y1,并与n求最大公约数，则此种方法给出n的一个因子。举例，n等于247,P=4,得pell方程， x^2-263*y^2=-247 解得，x=259,y=16,则259*1+16*4=17*19

mjs1wh · 发表于 2010-9-12 16:24:42

这有什么用，任何与n求最大公约数，都会给出n的一个因子。

wsc810 · 发表于 2010-9-12 17:06:03

敢定楼上小学都没毕业，居然有如此之“结论”

wsc810 · 发表于 2010-9-12 17:11:39

明白了，楼上的是所谓给出的因子就是1和这个数本身吧！这与我们通常所说的因子分解有什么相干。

wsc810 · 发表于 2010-9-13 05:52:41

求GCD(x+P*y,n)或者GCD(x-P*y,n)给出n的一个因子。现在的问题是求解这种类型的pell方便吗？都用什么算法？

gxqcn · 发表于 2010-9-14 07:47:30

求最大公约数最多是一次的，而解的pell方程却是二次的，前者肯定更简单高效。

账号		自动登录	找回密码
密码			欢迎注册

[原创] 特殊pell方程的非平凡解与因子分解

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。