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

breakPython がorcontinueステートメントにラベルを付けられないのは残念です。関数のよりきれいなバージョンの擬似コードを次に示します。

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

制御フローが移動する 2 つの場所に注意してくださいnext i。それを Python で書く良い方法はありません。1 つの選択肢は、残りのコードをいつバイパスするかを決定するために設定およびテストできる追加のブール変数を使用します。上記で選択したもう 1 つの選択肢は、タスクを実行するローカル関数を作成することです。この「ループ半」イディオムは便利で便利です。これはPEP 3136で提案され、Guido によって拒否されました。

于 2014-05-10T12:07:14.780 に答える