フェルマーテスト

フェルマーテスト (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)

参考ページ