Miller–Rabin 素数判定

$n - 1 = 2^s d$（ $d$ は奇数）と表し、いくつかの底 $a$ について $a^d, a^{2d}, \ldots, a^{2^{s-1} d} \bmod n$ を調べます。 $n$ が素数なら、 $a^d \equiv 1$ になるか、どこかで $-1$ が現れます。 $n < 2^{64}$ なら、決まった 7 個の底（ $n < 4759123141$ なら 3 個）で調べれば、必ず正しく判定できます。

• is_prime(n): $n$ が素数か（ $0 \le n < 2^{64}$）。 $O(\log n)$ 回の掛け算

$10^{12}$ 程度までなら 試し割り でも判定できますが、それより大きいときや、たくさんの数を判定するときに使います。素因数分解には Pollard’s rho 素因数分解 を使います。

コード

def is_prime(n):
    # 決定的 Miller–Rabin（n < 2^64 で正しい）
    if n < 2:
        return False
    for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
        if n % p == 0:
            return n == p
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    if n < 4759123141:
        bases = (2, 7, 61)
    else:
        bases = (2, 325, 9375, 28178, 450775, 9780504, 1795265022)
    for a in bases:
        if a % n == 0:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False
    return True