无心人 发表于 2008-10-23 20:50:27

椭圆曲线和二次筛都不很容易实现的
所以
这个比素性测试难很多吧

medie2005 发表于 2008-10-23 21:00:36

2^64还是很容易的.既有平均复杂度为O(n^(1/4))的Pollard rho算法,也有shanks的复杂度为O(n^(1/4)) 的分解算法.

无心人 发表于 2008-10-24 08:04:28

:b:

你了解的这么多啊

medie2005 发表于 2008-10-24 08:47:08

昨天实现了一下shanks的复杂度为$O(n^(1/4))$ 的分解算法，不知道是我写错了，还是资料上没写清，发现这个算法对一些数分解的时间也很不乐观。

无心人 发表于 2008-10-24 13:50:51

小数字下RHO是最有效的方法了

medie2005 发表于 2008-10-24 22:43:18

shanks的Square Forms Factorization分解算法对某些数可能无法分解。

无心人 发表于 2008-10-25 20:25:13

这种概率算法，包括RHO随机性太大
不如椭圆曲线的稳定
不过胜在简单

liangbch 发表于 2008-10-27 15:39:21

无意中找到一个软件，分解质因数2.02版
测试了一下，分解一个64bit的数还是很慢的，分解 18446713399053876329=4294960261×4294967189， 用时3220秒。

风云剑 发表于 2008-10-27 16:18:56

VB的，C写应该会快很多。

liangbch 发表于 2008-10-27 17:02:20

不可否认，用C写的程序比VB快。但VC写的程序速度相对于VB,用时之多比VB快一个常数因子，比如说快10倍。但即使这样，速度依然不够理想，9#说，分解64bit的数，只需秒级，看来这个程序的算法仍然不是最优的。
页: 1 [2] 3 4
查看完整版本: 请教gxqcn一个问题