对大合数分解的一种新的思考
本帖最后由 wsc810 于 2009-9-8 18:42 编辑设待要分解的大合数为D,我们知道利用sqrt(D)的连分式展开式最终可得到如下同余式，
p_n^2=(-1)^n*Q_(n+1)(mod D),如果我们再能得到一个关于Q的平方同余式，则同余式两边同时达到平方，若不是非平凡解，则可分解D,下面我们可以构造一个较为特殊的Pell方程，
x^2-Q*y^2=D,然后求解此不定方程，得到x,y的解。于是有
x^2=Q*y^2(mod D),最后将p代入，便可两边同时得到平方。现在问题的焦点是求解D大于Q的Pell方程方便吗，都用什么算法。希望知道的朋友讲解讲解，多谢了。 好像Pell方程就是用D的平方根的连分数解吧？
需要求出一个完整的循环节，通常很大
接近于D的平方根吧？
反正觉得你的主意似乎不行
不知道我说的对不对？ 现在成功的算法都是基于因子基的概率算法
是以某种方式凑出一个小素数集合的其中某些素数的偶数次幂的乘积来
类似
$x_1^2 -= y_1 (mod D)$
$x_2^2 -= y_2 (mod D)$
$x_3^2 -= y_3 (mod D)$
$x_4^2 -= y_4 (mod D)$
...
其中的$y_i$都能完全分解为一个预先设定的素数集合P中的素数的乘积
会得到一个以幂为项的矩阵
收集到足够信息后
进行某种组合，以得到两边都是偶数幂的平方剩余 麻烦无心人查一下《数论导引》中是怎样求解x^2-dy^2=c(注意是c＞d)的Pell方程式的，或者解此方程的最新方法。《数论导引》也有电子版的，在数学资源网。我现在上网不甚方便。多谢。 现在要求的是下列特殊Pell方程，
x^2-Q*y^2=D(D是一个较大的数，即待要分解的数，而Q是一个较小的数，小于2sqrt(D),问该不定方程怎么解，举例x^2-7y^2=4181,(4181是待要分解的数)谁能指点一下思路，我思考了很久都没想到办法，拜求了！ See:http://www.physicsforums.com/showthread.php?t=78855
页:
[1]