Miller–Rabin 素性测试

What · 是什么

Miller–Rabin 素性测试用于判定大整数是否为素数。将费马小定理 a^(n-1)≡1 的指数 n-1 分解为 u·2^t，结合二次探测定理（奇素数 p 下 x²≡1 的解只有 ±1）检查：若对基底 a 有 a^u≡1 或某个 a^(u·2^i)≡-1 (mod n)，则通过该轮。随机 k 个基底，合数通过所有轮的概率 ≤ 4^(-k)。关键结论：对 64 位整数，取基底 {2,325,9375,28178,450775,9780504,1795265022} 是【确定性的】；对 32 位取 {2,7,61} 或前 4 个素数即可。单轮 O(log n) 次模乘。它是 Pollard-Rho 分解大整数时的前置素性判定，Python 中 pow(a, e, n) 内建快速模幂，大整数优势明显。

Why · 为什么

How · 实现

伪代码

BASES_64 = [2,325,9375,28178,450775,9780504,1795265022]
def is_prime(n):
  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, s = n-1, 0
  while d % 2 == 0: d //= 2; s += 1
  for a in BASES_64:
    a %= n
    if a == 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

Python 实现

import random


def is_prime_mr(n, bases=None):
    """Miller-Rabin 素性测试.
    - bases=None 时使用确定性基底: [2,325,9375,28178,450775,9780504,1795265022],
      对 < 2^64 的所有整数确定性正确.
    - bases 可传入自定义基底列表 (如随机基底做概率测试).
    小整数直接试除/特判."""
    if n < 2: return False
    small = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for p in small:
        if n % p == 0:
            return n == p
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
    if bases is None:
        bases = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
    for a in bases:
        a %= n
        if a == 0:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        ok = False
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                ok = True
                break
        if not ok:
            return False
    return True


def is_prime_probabilistic(n, k=12):
    """概率版: 随机 k 个基底. 误判概率 <= 4^{-k}."""
    if n < 2: return False
    if n in (2, 3): return True
    if n % 2 == 0: return False
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(k):
        a = random.randint(2, n - 2)
        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


if __name__ == "__main__":
    # 已知小素数/合数
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 97, 9973, 1000003, 2147483647]
    comps = [1, 4, 6, 9, 341, 561, 1105, 1729, 41041, 825265, 3215031751]
    for p in primes:
        assert is_prime_mr(p), p
    for c in comps:
        assert not is_prime_mr(c), c

    # 强伪素数: 3215031751 = 151*751*28351, 是基底 {2,3,5,7} 的最小伪素数,
    # 但 7 基底确定性集 {2,325,...} 能正确判出合数.
    assert not is_prime_mr(3215031751), "3215031751 = 151*751*28351"
    # 展示 {2,3,5,7} 4 基底集确实被这个数骗过 (它是 32 位确定性界的最小反例)
    assert is_prime_mr(3215031751, bases=[2, 3, 5, 7]) == True

    # 2^64 附近的确定性验证
    mersenne_primes = [3, 7, 31, 127, 8191, 131071, 524287, 2147483647,
                       2305843009213693951, 618970019642690137449562111]
    for p in mersenne_primes:
        assert is_prime_mr(p), p

    # 随机交叉验证: 与试除法一致
    import random
    random.seed(2026)
    def trial(x):
        if x < 2: return False
        i = 2
        while i * i <= x:
            if x % i == 0: return False
            i += 1
        return True
    for _ in range(3000):
        n = random.randint(1, 10**7)
        assert is_prime_mr(n) == trial(n), n
    # 概率版
    for _ in range(500):
        n = random.randint(1, 10**6)
        assert is_prime_probabilistic(n) == trial(n), n
    print("miller-rabin: all tests passed")

易错点

• 忘了先处理小质因数（2,3）与 n<4 特判
• 指数分解时把 n-1 写成 n
• 检测 x==n-1 时误写 x==-1（Python 中 x 恒在 [0,n)）
• 基底未对 n 取模直接 pow（a 可能 ≥ n 影响正确性但 pow 会处理；跳过 a%n==0）
• 用 {2,3,5,7} 判定 32 位以上整数（3215031751 会骗过）
• 概率版固定随机种子导致对特定数误判不可复现排查

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/number-theory/prime/#millerrabin-素性测试
• CP-Algorithms✓ https://cp-algorithms.com/algebra/primality_tests.html
• article✓ https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test