|
发表于 2009-6-11 19:20:08
|
显示全部楼层
对于梅森素数的素性判断来说 Rabin-Miller 算法的效率并不比 Prime95(GIMPS) 用的卢卡斯-莱默测试(Lucas-Lehmer testing)高多少, 说不定还会更慢些.
Rabin-Miller 中关键一步是判断 a^((m - 1)/2) = 1 (mod m)
其中 m = 2^p - 1 为待验证的梅森数, a 是随机选的一个数. 需要计算 log2((m - 1)/2) ≈ p-1 次模乘法.
而卢卡斯-莱默测试需要计算 p-2 次 型如 (S^2 - 2) mod m 的模乘法....
更关键的, Rabin-Miller 不能确定一个数的素性, 多次测试测试的话效率就更低了.
参考:
Rabin-Miller Strong Pseudoprime Test
http://mathworld.wolfram.com/Rab ... seudoprimeTest.html
Prime95(GIMPS) 用的卢卡斯-莱默测试(Lucas-Lehmer testing)
http://www.equn.com/gimps/math.htm |
|