素性检测与整数分解

无心人 · 发表于 2008-5-17 20:00:03

那就是说求其连分数的平均时间复杂度是$O(sqrt(N)lg^2NlglgN)$ 试除的时间复杂度是$O(1//2 sqrt(N)*lgNlglgN )$ 另外需要强调：连分数因数分解法和本文楼主的思路是两码事主要区别在于连分数方法和我上面的因子基算法是联系在一起的而不是直接求平方剩余

mathe · 发表于 2008-5-17 21:14:20

嗯，这个方法基本上是不实用的了。不过能够将这个问题转化成Pell方程，然后转化为一个连分数问题，想法还是不错的，鼓励鼓励

无心人 · 发表于 2008-5-17 21:19:13

因子分解算法是目前数论特别是计算数论的一个资源产生点很多有用处的理论在快速产生

福娃PNP · 发表于 2008-5-18 20:05:55

根据资料可以看到,GNFS是目前最好的算法,想跟我的算法做个比较,不知怎么做,GNFS的时间复杂度在下面两个网站可以看到,我的算法是:渐近分数的时间复杂度（相当于解不定方程x²-Ny²=1的时间复杂度）+Stein算法（由J. Stein 1961年提出，可以算是转辗相除法的一种好算法）。如不清楚可到我的空间! 来源:1.http://www.mediawiki.motocykle.s ... 80%89%E6%B3%95.html 2.http://www.wikilib.com/wiki?titl ... A7%A3&variant=zh-sg 3.我的空间:http://hi.baidu.com/%CB%EF%CD%F2%B8%A3

福娃PNP · 发表于 2008-5-18 20:07:55

我很感谢大家能够在这里讨论,有缘分!

无心人 · 发表于 2008-5-18 20:13:19

GNFS的介绍很少我是在分解F9的论文上看到的上面是NFS的介绍

福娃PNP · 发表于 2008-5-20 18:58:22

关于41楼的问题,麻烦您能把时间复杂度的计算式子看一下吗?我怎么在WIMS上无发做出关于您给出公式的图形?

无心人 · 发表于 2008-5-20 20:29:45

那是本论坛的一个功能是文字方式的符号通过JS显示的

无心人 · 发表于 2008-5-20 20:37:23

这么计算的 $N$平均连分数周期$sqrt(N)lgN$ 计算一个数字$lgNlglgN$ 乘在一起就是了

福娃PNP · 发表于 2008-5-21 20:01:18

我刚在WIMS网站作了一些图，作出来了，太感谢您了！我发现我的办法好象比GNFS快一样，我也不知道我搞的对不对？如果你能保证你的结论正确，那我想应该是对的，如有兴趣，可自己做一下！

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

[讨论] 素性检测与整数分解