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

Question

我实现了在维基百科上找到的Miller-Rabin素数测试算法 Python 3。

它似乎可以正确处理大多数数字，但偶尔会在某些数字上失败。

例如素数99999999999999997被判断为NOT素数。

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

这是我的代码。

测试输入是：

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

我将重申我的评论，因为我的测试似乎表明你的示例正在运行。我强烈怀疑你刚刚输错了你的测试用例。也许你可以尝试再看一下？这是我运行它得到的结果：

在[12]中：millerrabin.isPrime(99999999999999997, 5)

输出[12]：正确

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

1
99999999999999997
YES

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

Answer 2

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

Answer 3

这是我不久前写的 Miller-Rabin 的实现。它从未给我带来意想不到的结果——但这并不意味着它不会！它与您粘贴的基本相同，并且它声明 99999999999999997 是素数。当我测试它时，你的也这样做了——所以这是 米科拉的意见。 但是请参阅下面的一个可能的问题，我无法轻松测试...从头开始，我测试了它，这就是问题。

当谈到素性测试时，我不是专家，但我花了很多时间思考并理解 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，我心里想。然后我意识到你一定使用的是 Python 3。所以这意味着你在这里进行浮点算术，然后转换为 int。这看起来很可疑。所以我在ideone上测试了一下。 瞧！结果是False。因此，我更改了代码以使用显式楼层划分 (d = nn // (2 ** s))。 瞧！这是正确的。