我的主要测试代码有什么问题？

Question

我用Python3实现了在维基百科上找到的Miller-Rabin prime test algorithm。

它似乎在大多数数字上都能正常工作，但在某些数字上偶尔会失败。

例如，质数99999999999999997被判断为不是质数。

我逐行实现了算法，但我不知道问题出在哪里。有人能帮我吗？

这是我的代码。

测试输入为：

1

99999999999999997

(两行之间没有空行。)

预期的输出应该是YES，但在我的机器上它给出了NO。

import random

def isPrime(n, k = 5):
'''
Primality test using Miller-Rabin method.
n The number to test primality.
k The number of M-R test to perform.
'''
if n == 1:
    return False
if n == 2 or n == 3:
    return True
if n % 2 == 0:
    return False

# Calculate d
nn = n - 1
s = 1
while nn % (2 ** s) == 0:
    s += 1
s -= 1
d = int(nn / (2 ** s))

for i in range(k):
    a = random.randint(2, n - 1)
    x = pow(a,d,n)
    if x == 1 or x == n - 1:
        continue
    flag = True
    for r in range(1, s):
        x = pow(x,2,n)
        if x == 1:
            return False
        if x == n - 1:
            flag = False
            break
    if not flag:
        continue
    return False
return True

count = int(input())
for i in range(count):
    if isPrime(int(input())):
        print('YES')
    else:
        print('NO')

Answer 1

这是我不久前写的Miller-Rabin的实现。它从未给我带来意想不到的结果--尽管这并不意味着它不会！它与您粘贴的那个基本相同，并将99999999999999997声明为质数。当我测试它的时候，你的也是如此--所以比Mikola's opinion快了一秒。，但下面是我不能轻易测试的一个可能的问题...去掉它，我测试了它，这就是问题。

当谈到素数测试时，我不是专家，但我花了很多时间思考和理解Miller-Rabin，我非常确定您的实现是准确的。

def is_prime_candidate(self, p, iterations=7):  
    if p == 1 or p % 2 == 0: return False       
    elif p < 1: raise ValueError("is_prime_candidate: n must be a positive integer")
    elif p < self.maxsmallprime: return p in self.smallprimes

    odd = p - 1
    count = 0
    while odd % 2 == 0:
        odd //= 2
        count += 1

    for i in range(iterations):
        r = random.randrange(2, p - 2) 
        test = pow(r, odd, p)
        if test == 1 or test == p - 1: continue
        for j in range(count - 1):
            test = pow(test, 2, p)
            if test == 1: return False
            if test == p - 1: break
        else: return False
        print i
    return True

关于你的代码，我注意到的一件事是：

d = int(nn / (2 ** s))

为什么是int，我心想。然后我意识到你一定是在使用Python3，这意味着你在这里做浮点运算，然后转换成int。这看起来很可疑。所以我在ideone上测试了它。And lo!的结果是False。因此，我更改了代码以使用显式楼层划分(d = nn // (2 ** s))。And lo!是True。

Answer 2

我将重申我的意见，因为我的测试似乎表明您的示例是有效的。我强烈怀疑您只是输入了错误的测试用例。也许你可以试着再看一眼？下面是我从运行它得到的结果：

12中的

：millerrabin.isPrime(99999999999999997，5)

Out12: True

编辑:我刚刚运行了更新后的版本，下面是控制台的输出：

1
99999999999999997
YES

同样，这看起来是正确的。

Answer 3

据我所知，Miller-Rabin算法仅是概率的。您是否没有意识到这一点，或者您正在使用修改后的非概率版本？