素性检测与整数分解

无心人 · 发表于 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 ... 3&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快一样，我也不知道我搞的对不对？如果你能保证你的结论正确，那我想应该是对的，如有兴趣，可自己做一下！

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

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