0

我使用了一些取自 Rosetta Code 的代码。我重命名了一些东西，但我并没有真正改变任何东西。

import random

def is_probable_prime(n, num_trials = 5):
    assert n >= 2
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    s = 0
    d = n-1
    while True:
        quotient, remainder = divmod(d, 2)
        if remainder == 1:
            break
        s += 1
        d = quotient
    assert(2**s * d == n-1)

    def try_composite(a):
        if pow(a, d, n) == 1:
            return False
        for i in range(s):
            if pow(a, 2**i * d, n) == n-1:
                return False
            return True

    for i in range(num_trials):
        a = random.randrange(2, n)
        if try_composite(a):
            return False
    return True

它与一些伪代码非常匹配。但是，当我测试数字时

123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901

它返回False。Miller-Rabin 的其他（python 和 java）实现返回True可能的素数。经过一些测试，仅回合后try_composite返回！我真的很想知道任何错误，我猜是缩进错误或我不知道的某些功能。True2

4

1 回答 1

2

在您的try_composite函数中，for循环应该是for i in range(1,s). 不要测试i为零的情况。

编辑：另外，你的try_composite函数中缺少一个测试。这是我的伪代码版本：

def isPrime(n, k=5):
    def isComposite(s, d):
        x = pow(randrange(2,n-1), d, n)
        if x == 1 or x == n-1: return False
        for r in range(1, s):
            x = pow(x, 2, n)
            if x == 1: return True
            if x == n-1: return False
        return True
    if n < 2: return False
    for p in [2, 3, 5, 7, 11, 13, 17]:
        if n % p == 0: return n == p
    s, d = 0, n-1
    while d % 2 == 0: s, d = s+1, d/2
    for i in range(k):
        if isComposite(s, d): return False
    return True

Python 不允许在breakorcontinue语句上使用标签，这太糟糕了。这是该函数更漂亮版本的伪代码：

function isPrime(n, k=5)
    if n < 2 then return False
    for p in [2,3,5,7,11,13,17,19,23,29]
        if n % p == 0 then return n == p
    s, d = 0, n-1
    while d % 2 == 0
        s, d = s+1, d/2
    for i from 0 to k
        x = powerMod(randint(2, n-1), d, n)
        if x == 1 or x == n-1 then next i
        for r from 1 to s
            x = (x * x) % n
            if x == 1 then return False
            if x == n-1 then next i
        return False
    return True

注意控制流去的两个地方next i。在 Python 中没有很好的方法来编写它。一种选择使用一个额外的布尔变量，可以设置和测试以确定何时绕过其余代码。我在上面选择的另一个选择是编写一个本地函数来执行任务。这个“loop-and-a-half”的成语既方便又有用；它是在PEP 3136中提出的，但被 Guido拒绝。

于 2014-05-10T12:07:14.780 回答