那就是说求其连分数的平均时间复杂度是$O(sqrt(N)lg^2NlglgN)$
试除的时间复杂度是$O(1//2 sqrt(N)*lgNlglgN )$
另外需要强调：连分数因数分解法和本文楼主的思路是两码事
主要区别在于连分数方法和我上面的因子基算法是联系在一起的
而不是直接求平方剩余
:) 嗯，这个方法基本上是不实用的了。
不过能够将这个问题转化成Pell方程，然后转化为一个连分数问题，想法还是不错的，鼓励鼓励:lol :)
因子分解算法是目前数论特别是计算数论的一个资源产生点
很多有用处的理论在快速产生 根据资料可以看到,GNFS是目前最好的算法,想跟我的算法做个比较,不知怎么做,GNFS的时间复杂度在下面两个网站可以看到,我的算法是:渐近分数的时间复杂度（相当于解不定方程x²-Ny²=1的时间复杂度）+Stein算法（由J. Stein 1961年提出，可以算是转辗相除法的一种好算法）。如不清楚可到我的空间!
来源:1.http://www.mediawiki.motocykle.slask.pl/zh/wiki/%E6%99%AE%E9%80%9A%E6%95%B0%E5%9F%9F%E7%AD%9B%E9%80%89%E6%B3%95.html
2.http://www.wikilib.com/wiki?title=%E8%B4%A8%E5%9B%A0%E6%95%B0%E5%88%86%E8%A7%A3&variant=zh-sg
3.我的空间:http://hi.baidu.com/%CB%EF%CD%F2%B8%A3 我很感谢大家能够在这里讨论,有缘分! GNFS的介绍很少
我是在分解F9的论文上看到的
上面是NFS的介绍 关于41楼的问题,麻烦您能把时间复杂度的计算式子看一下吗?我怎么在WIMS上无发做出关于您给出公式的图形? :)
那是本论坛的一个功能
是文字方式的符号
通过JS显示的 这么计算的
$N$平均连分数周期$sqrt(N)lgN$
计算一个数字$lgNlglgN$
乘在一起就是了