找回密码
 欢迎注册
楼主: 素数粉

[求助] 请教gxqcn一个问题

[复制链接]
发表于 2008-10-23 20:50:27 | 显示全部楼层
椭圆曲线和二次筛都不很容易实现的
所以
这个比素性测试难很多吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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 | 显示全部楼层


你了解的这么多啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-24 08:47:08 | 显示全部楼层
昨天实现了一下shanks的复杂度为$O(n^(1/4))$ 的分解算法,不知道是我写错了,还是资料上没写清,发现这个算法对一些数分解的时间也很不乐观。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-24 13:50:51 | 显示全部楼层
小数字下RHO是最有效的方法了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-24 22:43:18 | 显示全部楼层
shanks的Square Forms Factorization分解算法对某些数可能无法分解。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-25 20:25:13 | 显示全部楼层
这种概率算法,包括RHO随机性太大
不如椭圆曲线的稳定
不过胜在简单
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-27 15:39:21 | 显示全部楼层
无意中找到一个软件,分解质因数2.02版
测试了一下,分解一个64bit的数还是很慢的,分解 18446713399053876329=4294960261×4294967189, 用时3220秒。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-27 16:18:56 | 显示全部楼层
VB的,C写应该会快很多。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-27 17:02:20 | 显示全部楼层
不可否认,用C写的程序比VB快。但VC写的程序速度相对于VB,用时之多比VB快一个常数因子,比如说快10倍。但即使这样,速度依然不够理想,9#说,分解64bit的数,只需秒级,看来这个程序的算法仍然不是最优的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 21:52 , Processed in 0.050100 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表