对大合数分解的一种新的思考

wsc810 · 发表于 2009-9-8 12:31:58

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

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

×

本帖最后由 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方程方便吗，都用什么算法。希望知道的朋友讲解讲解，多谢了。

无心人 · 发表于 2009-9-10 19:56:19

好像Pell方程就是用D的平方根的连分数解吧？需要求出一个完整的循环节，通常很大接近于D的平方根吧？反正觉得你的主意似乎不行不知道我说的对不对？

无心人 · 发表于 2009-9-10 20:02:40

现在成功的算法都是基于因子基的概率算法是以某种方式凑出一个小素数集合的其中某些素数的偶数次幂的乘积来类似 $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中的素数的乘积会得到一个以幂为项的矩阵收集到足够信息后进行某种组合，以得到两边都是偶数幂的平方剩余

wsc810 · 发表于 2009-9-12 05:39:46

麻烦无心人查一下《数论导引》中是怎样求解x^2-dy^2=c(注意是c＞d)的Pell方程式的，或者解此方程的最新方法。《数论导引》也有电子版的，在数学资源网。我现在上网不甚方便。多谢。

wsc810 · 发表于 2009-10-17 16:13:06

现在要求的是下列特殊Pell方程， x^2-Q*y^2=D(D是一个较大的数，即待要分解的数，而Q是一个较小的数，小于2sqrt(D),问该不定方程怎么解，举例x^2-7y^2=4181,(4181是待要分解的数)谁能指点一下思路，我思考了很久都没想到办法，拜求了！

northwolves · 发表于 2009-11-18 01:32:56

See:http://www.physicsforums.com/showthread.php?t=78855

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

[原创] 对大合数分解的一种新的思考

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