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

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

设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方程却是二次的，
前者肯定更简单高效。
页: [1]
查看完整版本: 特殊pell方程的非平凡解与因子分解