<p>今天一直在尝试实现Rabin-Miller强伪素数测试。</p>
<p>使用了<a href="http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html" rel="nofollow">Wolfram Mathworld</a>作为引用,第3-5行总结了我的代码。</p>
<p>然而,当我运行这个程序时,它会说(有时)素数(即使是5,7,11这样的低素数)也不是素数。我看了很长一段时间代码,不知道出了什么问题。</p>
<p>为了获得帮助,我查看了这个站点以及许多其他站点,但大多数站点都使用了另一个定义(可能是相同的,但由于我是这种数学的新手,我看不到相同的明显联系)。</p>
<p>我的代码:</p>
<pre><code>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))
</code></pre>
<p>这与Mathworld给出的定义有何不同?</p>