素性检测与整数分解

medie2005

很早就有利用连分数法来分解大数的方法了.MathWorld上也有介绍:http://mathworld.wolfram.com/ContinuedFractionFactorizationAlgorithm.html 只不过,人家是找满足$x^2=y^2(mod N)$的$(x,y)$,而楼主是求它的一种特殊情况y=1而已. 由此,可以想见,求解的困难程度更大了.所以,楼主的这条路是到不了罗马了.

无心人

mathe 因子分解的筛算法第一个是Fermat算法 第二个成功的就是连分数算法 所以，尝试这个方法并没有意义了 而使用根号N的方法就是二次筛算法 已经发展到多项式筛 是仅次于数域筛的一个算法 无论从理论上还是从实践上 我们都无法进行这个问题的任何尝试 太复杂了 所以说，因子分解我们只有用大牛写的程序的能耐

无心人

初期的算法都是尝试求平方同余 后期的方法都是一个综合性的 具体是找尽可能多的同余式 分解两边，综合到一起 然后计算两边的素因子的方幂 其素因子以事先计算的范围为主 超出范围的因子及其结果可能被抛弃 一旦两边方幂同时达到2的倍数 那就找到一个分解了 称为因子基算法

无心人

而楼主的思路还是停留在初期 求平方剩余的原始阶段 所以说，并不是一个好方法啊

无心人

举个例子 假设因子基选择$2, 3, 5, 7$ 计算得到(仅做演示，任何细节均可能不符合实际) $x_1^2 -= 2*3*5 mod N$ $x_2^2 -= 3*5 mod N$ $x_3^2 -= 7 mod N$ $x_4^2 -= 2*7 mod N$ 显然 $(x_1x_2x_3x_4)^2 = (2*3*5*7)^2 mod N$ $N$得到分解

无心人

实际得到的结果可能上几十万甚至上百万 其结果的处理是使用线性代数的方法 类似于求矩阵的行或者列的相关

medie2005

呵呵,Fermat方法和连分数法,taocp第二卷讲的很清楚.

无心人

至于具体如何求$sqrt(N)$的算法 假设$a_1$为小于$sqrt(N)$最大整数 计算$sqrt(N) - a_1$的连分数展开，直到出现结果$2a_1$则结束，下面的连分数将循环前面的结果，即从$a_2$开始重复出现，是一个很简单的高精度浮点计算的程序。

无心人

首先声明对19#的错误纠正 对25#假设N没有小因子，则计算连分数就是一个简单的O(N)算法 嘿嘿，由于N很大，所以消耗多少时间你可以计算了 由于计算除法的时间是O(lgNlglgN)，所以在真实机器上的时间是O(NlgNlglgN) 再次对19#的错误表示抱歉 时间复杂度很小，但是N很大 嘿嘿 现在明白了么？ 即使分解了N，sqrt(N)的连分数的循环节长度是所有素因子循环节长度的最小公倍数 也是个O(N)算法

mathe

找到一个有用的页面: http://en.wikipedia.org/wiki/Periodic_continued_fraction 其中最后说$sqrt(D)$连分数的周期大概为$O(sqrt(D)log(D))$,所以这个时间复杂度太高了一些。