Rabin-Miller强伪素测试实现将不起作用
今天我一直在尝试实现Rabin-Miller强伪素性测试。
使用Wolfram Mathworld作为参考，第3-5行总结了我的代码。
然而，当我运行程序时，它告诉我(有时)质数(即使是5，7，11这样的低值)也不是质数。我已经看了很长一段时间的代码，找不出哪里出了问题。
为了寻求帮助，我看过这个网站和许多其他网站，但大多数都使用另一种定义(可能是相同的，但由于我对这种数学不熟悉，我看不到明显的联系)。
我的代码：
import random
def RabinMiller(n, k):
# obviously not prime
if n < 2 or n % 2 == 0:
return False
# special case
if n == 2:
return True
s = 0
r = n - 1
# factor n - 1 as 2^(r)*s
while r % 2 == 0:
s = s + 1
r = r // 2 # floor
# k = accuracy
for i in range(k):
a = random.randrange(1, n)
# a^(s) mod n = 1?
if pow(a, s, n) == 1:
return True
# a^(2^(j) * s) mod n = -1 mod n?
for j in range(r):
if pow(a, 2**j*s, n) == -1 % n:
return True
return False
print(RabinMiller(7, 5))这与Mathworld给出的定义有什么不同？
回答 4
Stack Overflow用户
发布于 2013-01-31 05:19:30
除了Omri Barel所说的之外，for循环还有一个问题。如果找到一个通过测试的a，您将返回true。然而，所有的a都必须通过测试才能使n成为可能的素数。
Stack Overflow用户
发布于 2013-01-31 05:05:40
我想知道这段代码：
# factor n - 1 as 2^(r)*s
while r % 2 == 0:
s = s + 1
r = r // 2 # floor以n = 7为例。所以n - 1 = 6。我们可以将n - 1表示为2^1 * 3。在本例中为r = 1和s = 3。
但是上面的代码发现了一些其他东西。它以r = 6开头，所以r % 2 == 0。最初，在一次迭代之后，我们得到了s = 1和r = 3。但是现在r % 2 != 0和循环终止了。
我们最终得到了s = 1和r = 3，这显然是不正确的：2^r * s = 8。
您不应该在循环中更新s。相反，您应该计算可以除以2的次数(这将是r)，除法后的结果将是s。在n = 7，n - 1 = 6的例子中，我们可以将它除以一次(所以是r = 1)，除法之后我们得到3(所以是s = 3)。
Stack Overflow用户
发布于 2013-01-31 05:52:50
以下是我的版本：
# miller-rabin pseudoprimality checker
from random import randrange
def isStrongPseudoprime(n, a):
d, s = n-1, 0
while d % 2 == 0:
d, s = d/2, s+1
t = pow(a, d, n)
if t == 1:
return True
while s > 0:
if t == n - 1:
return True
t, s = pow(t, 2, n), s - 1
return False
def isPrime(n, k):
if n % 2 == 0:
return n == 2
for i in range(1, k):
a = randrange(2, n)
if not isStrongPseudoprime(n, a):
return False
return True如果你想了解更多关于素数编程的知识，我在我的博客上谦虚地推荐this essay。
https://stackoverflow.com/questions/14613304
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号