素性检测与整数分解

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))$,所以这个时间复杂度太高了一些。