フェルマーテスト

フェルマーテスト (Fermat primality test)

巨大な数が素数であるかを判定する。

カーマイケル数 を誤って素数と判定してしまう。

# フェルマーテスト
import random
def fermat(k):
    for _ in range(1000):
        a = random.randint(2, k-1)
        if pow(a, k-1, k) != 1:
            return 0
    return 1

Verified

  • yukicoder: "No.308 素数は通れません": source (Python2, WA)

カーマイケル数で落ちてWA

ミラーラビン素数判定法

ミラーラビン素数判定法 (Miller-Rabin primality test)

異なる \(k\) 個の乱数で素数判定を行った場合、誤って素数と判定してしまう確率は \(\frac{1}{4^k}\) 以下になる。

# ミラーラビン素数判定法
import random
def miller_rabin(n, t):
    if n == 2:
        return 1
    if n == 1 or n & 1 == 0:
        return 0
    d = n-1
    d //= d & -d
    for _ in range(t):
        a = random.randint(1, n-1)
        t = d
        y = pow(a, t, n)
        while t != n-1 and y != 1 and y != n-1:
            y = y**2 % n
            t <<= 1
        if y != n-1 and t & 1 == 0:
            return 0
    return 1

Verified

  • yukicoder: "No.308 素数は通れません": source (Python2, 45ms)

参考

戻る