vault

Miller-Rabin Primality Test

28 min read

Miller-Rabin Primality Test

Miller-Rabin is the standard probabilistic primality test for arbitrary integers: given a candidate n, it certifies compositeness with probability ≥ 3/4 per random witness, and after k independent witnesses, the probability of a composite slipping through is at most 4^(-k). The algorithm runs in O(k · log³ n) bit operations using Fast Exponentiation for the modular powers, making it practical for cryptographic-size primes (thousands of digits) where deterministic tests are infeasible. The original deterministic form was proposed by Gary Miller in his 1976 paper “Riemann’s hypothesis and tests for primality” — its correctness for polynomial-time deterministic primality testing depends on the Generalized Riemann Hypothesis. Michael Rabin in 1980 stripped the GRH dependency by randomizing the witness selection, producing the test now in universal use. The test rests on a sharpening of Fermat’s little theorem: for prime n, the equation x² ≡ 1 (mod n) has only the trivial roots ±1, but composites typically have non-trivial square roots of unity that the algorithm uses to detect compositeness. For numbers below specific bounds (notably n < 3.42 × 10^14 with the seven witnesses {2,3,5,7,11,13,17}, or n < 3.317 × 10^24 with the first twelve primes), Miller-Rabin is deterministic — no probabilistic doubt at all. This note develops the algorithm, proves the witness bound, traces a concrete trial, catalogs the known deterministic witness sets, and flags subtle pitfalls (Carmichael numbers do not fool Miller-Rabin the way they fool the basic Fermat test, but a related notion of strong pseudoprimes requires careful witness choice).

1. Intuition — Detecting Compositeness via Roots of Unity

A direct primality test would factor n and check that the only divisors are 1 and n. Factoring is hard — that is the basis of RSA security. So we look for a certificate of compositeness that is easy to verify: a witness that proves n is not prime, even if we don’t recover its factors.

Fermat’s little theorem (Modular Inverse §4.3) says: if n is prime and gcd(a, n) = 1, then a^(n-1) ≡ 1 (mod n). Contrapositive: if a^(n-1) ≢ 1 (mod n), then n is composite. The naive Fermat primality test checks this for several random a. Problem: there are composite n (called Carmichael numbers) for which a^(n-1) ≡ 1 (mod n) for every a coprime to n — they pass the Fermat test for all witnesses simultaneously, making the test useless for them. The smallest Carmichael number is 561 = 3 · 11 · 17. There are infinitely many (Alford, Granville, Pomerance 1994).

Miller-Rabin sharpens Fermat using a deeper fact about prime moduli: for prime n, the equation x² ≡ 1 (mod n) has exactly two solutions, x = 1 and x = -1. For composite n with multiple distinct prime factors, there are additional “non-trivial” square roots of 1 — and these expose the compositeness.

The algorithm: write n - 1 = d · 2^s (extract all factors of 2). If n is prime and gcd(a, n) = 1, then a^(n-1) = a^(d · 2^s) ≡ 1 (mod n). Take repeated square roots: a^(d · 2^(s-1)) is a square root of 1, so it must be ±1. If it is 1, take another square root and repeat. The sequence

a^d, a^(2d), a^(4d), ..., a^(2^(s-1) · d), a^(2^s · d) = a^(n-1)

ends at 1. Working backward, the first time we hit 1 must be preceded by -1 (i.e., n - 1), or the sequence must already start at 1. Any other behavior — a value other than ±1 whose square is 1 — proves n has a non-trivial square root of unity, hence is composite.

The test on a single witness a:

  1. Compute a^d mod n. If it is 1 or n-1, a does not witness compositeness; the test passes for this a.
  2. Square repeatedly up to s-1 times. If any of a^(2d), a^(4d), …, a^(2^(s-1) d) equals n-1, a does not witness; pass.
  3. If we reach a^(2^s · d) = a^(n-1) without ever seeing n-1, then either a^(n-1) ≢ 1 (Fermat-fail) or we crossed through 1 from a non-trivial square root. Either way, n is composite. a is a witness to compositeness.

A prime n will never have a witness — the test always passes. A composite n may pass the test for some a (the strong liars for n) but, as we prove in §6, at most 1/4 of the values in [1, n-1] can be strong liars. So a single random a has probability ≥ 3/4 of catching a composite, and k independent witnesses give an error bound of (1/4)^k = 4^(-k).

2. Tiny Worked Example — Test n = 561 and n = 41

2.1 Testing n = 561 (a Carmichael number) with witness a = 2

561 - 1 = 560 = 35 · 16, so d = 35, s = 4.

Compute 2^35 mod 561:

2^10 = 1024 mod 561 = 463. 2^20 = 463² mod 561 = 214,369 mod 561 = 214369 - 382·561 = 214369 - 214302 = 67. Combining the binary pieces (35 = 32 + 2 + 1) gives 2^35 mod 561 = 263 (confirmed: pow(2, 35, 561) == 263).

Trace:

  • a^d = 2^35 mod 561 = 263. Not 1, not 560. Continue.
  • a^(2d) = 263² mod 561 = 69169 mod 561 = 69169 - 123·561 = 69169 - 69003 = 166. Not 560. Continue.
  • a^(4d) = 166² mod 561 = 27556 mod 561 = 27556 - 49·561 = 27556 - 27489 = 67. Not 560. Continue.
  • a^(8d) = 67² mod 561 = 4489 mod 561 = 4489 - 8·561 = 4489 - 4488 = 1. We hit 1, but the previous value (67) was not 560! This is a non-trivial square root of unity (since 67 ≠ ±1 but 67² ≡ 1).

561 is composite — caught. (It is 3 · 11 · 17.)

2.2 Testing n = 41 (a true prime) with witness a = 2

41 - 1 = 40 = 5 · 8, so d = 5, s = 3.

  • a^d = 2^5 mod 41 = 32. Not 1, not 40. Continue.
  • a^(2d) = 32² mod 41 = 1024 mod 41 = 1024 - 24·41 = 1024 - 984 = 40. We hit 40 = n-1. Test passes for a = 2.

41 is reported probably-prime. (It is in fact prime.) Try other witnesses — they all pass. With k = 7 standard witnesses (see §7.2), this is a deterministic certificate that 41 is prime.

2.3 Testing n = 25 (small composite) with witness a = 7

25 - 1 = 24 = 3 · 8, so d = 3, s = 3.

  • a^d = 7^3 mod 25 = 343 mod 25 = 18. Not 1, not 24. Continue.
  • a^(2d) = 18² mod 25 = 324 mod 25 = 24. Hit 24 = n-1. Test passes for a = 7.

So a = 7 is a strong liar for n = 25 — 25 is composite but witness 7 doesn’t catch it. We need another witness:

  • Try a = 2: 2^3 mod 25 = 8. 8² mod 25 = 64 mod 25 = 14. 14² mod 25 = 196 mod 25 = 21. We reached a^(n-1) mod 25 = 21, never 1 or 24 along the way → 21 ≠ 1 so Fermat-fails too. Composite.

So one random witness can fail to catch n = 25, but a different witness succeeds. The probability bound says at most 1/4 of witnesses are liars — so on average at least 3 in 4 witnesses catch any given composite. For n = 25, the strong liars in [1, 24] are exactly {1, 7, 18, 24} — that is 4 out of 24, a liar fraction of 1/6 ≈ 0.167, comfortably under the 1/4 worst-case bound. (The bound is only attained, not exceeded, by the single composite n = 9, whose strong liars {1, 8} give exactly 2/8 = 1/4; see §6.2.)

3. The Algorithm

3.1 Pseudocode

miller_rabin(n, witnesses):
    # Handle small cases first
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n is even: return False

    # Decompose n - 1 = d · 2^s with d odd
    d := n - 1
    s := 0
    while d is even:
        d := d / 2
        s := s + 1

    # For each witness, run the strong-pseudoprime test
    for a in witnesses:
        if a >= n: continue        # skip witnesses ≥ n (irrelevant)
        x := mod_pow(a, d, n)
        if x == 1 or x == n - 1:
            continue               # witness doesn't catch n
        composite_witnessed := True
        repeat s - 1 times:
            x := (x · x) mod n
            if x == n - 1:
                composite_witnessed := False
                break              # witness doesn't catch n
        if composite_witnessed:
            return False           # n is definitely composite
    return True                    # n is probably prime

For probabilistic testing, the witnesses are random values in [2, n-2]. For deterministic testing of small n, use a fixed witness set known to be sufficient (§7).

3.2 Why Decompose n - 1 = d · 2^s?

The decomposition extracts the largest power of 2 from n - 1. The sequence of squares a^d, a^(2d), …, a^(2^s d) = a^(n-1) then has length s + 1, terminating at a^(n-1). By Fermat, this final value is 1 if n is prime. The intermediate values let us probe for non-trivial square roots of unity, which only exist mod composite numbers (§6).

If n - 1 had no factor of 2 (i.e., n - 1 odd, hence n even), we couldn’t apply this — but every n > 2 is either prime (and hence we test specially for n = 2) or odd, so n - 1 is even, giving s ≥ 1.

4. Python Implementation

def miller_rabin(n: int, witnesses: list[int] | None = None, k: int = 20) -> bool:
    """Test whether n is prime using Miller-Rabin.
 
    If `witnesses` is provided, run the test for each fixed witness (deterministic).
    Otherwise, run k random witnesses (probabilistic, error <= 4^(-k)).
 
    Returns True if n is (probably) prime, False if composite.
    """
    import random
 
    if n < 2:
        return False
    # Small primes hard-coded for speed and to handle n in [2, 3]
    small_primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)
    for p in small_primes:
        if n == p:
            return True
        if n % p == 0:
            return False
 
    # Decompose n - 1 = d · 2^s
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
 
    if witnesses is None:
        # Probabilistic: pick k random witnesses in [2, n-2]
        witnesses = [random.randrange(2, n - 1) for _ in range(k)]
 
    for a in witnesses:
        if a % n == 0:               # witness divisible by n is meaningless
            continue
        x = pow(a, d, n)             # uses fast exponentiation
        if x == 1 or x == n - 1:
            continue
        composite_witnessed = True
        for _ in range(s - 1):
            x = (x * x) % n
            if x == n - 1:
                composite_witnessed = False
                break
        if composite_witnessed:
            return False             # definitely composite
    return True                      # probably prime (or definitely if witnesses are deterministic set)
 
 
def is_prime_deterministic(n: int) -> bool:
    """Deterministic primality test for n < 3.317 × 10^24 using 12 specific witnesses.
 
    For n below 3.317 × 10^24 (Sorenson & Webster 2017), the witnesses
    {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} are sufficient to make
    Miller-Rabin deterministic — no false positives.
    """
    return miller_rabin(n, witnesses=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37])
 
 
def is_prime_64bit(n: int) -> bool:
    """Deterministic for all n < 2^64: use witnesses {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}.
 
    From Sorenson & Webster 2017: these 12 witnesses are sufficient for n < 3.317 × 10^24,
    which subsumes 2^64 ≈ 1.844 × 10^19. For tighter bounds with fewer witnesses, see §7.
    """
    return is_prime_deterministic(n)
 
 
# Demonstrations
if __name__ == "__main__":
    # Known primes
    for p in [2, 3, 5, 7, 11, 13, 41, 97, 103, 1_000_000_007]:
        assert miller_rabin(p, k=10), f"{p} should be prime"
    # Known composites
    for c in [4, 9, 25, 561, 1729, 1_000_000_000]:
        assert not miller_rabin(c, k=10), f"{c} should be composite"
    # The infamous strong pseudoprimes
    # 3215031751 = 151 · 751 · 28351 is a strong pseudoprime to 2, 3, 5, 7 simultaneously
    # (Pomerance, Selfridge & Wagstaff 1980), so the {2,3,5,7} witness set WRONGLY reports it prime:
    assert miller_rabin(3_215_031_751, witnesses=[2, 3, 5, 7]) is True   # fooled — false positive
    # ...but adding witness 11 catches it:
    assert miller_rabin(3_215_031_751, witnesses=[11]) is False          # correctly composite
    # Large prime test (Mersenne)
    M_31 = 2**31 - 1                  # 2147483647
    assert miller_rabin(M_31, k=10)
    # Carmichael number
    assert not miller_rabin(561, k=10)
    assert not miller_rabin(1729, k=10)        # Hardy-Ramanujan number, also Carmichael

Python 3 also has the sympy.isprime function (uses Miller-Rabin + small additional checks) and gmpy2.is_prime (very fast). For raw speed on machine-word integers, is_prime_64bit above is competitive with anything.

5. Complexity

5.1 Time

For each witness a, the work is dominated by the modular exponentiation pow(a, d, n), which takes O(log d · M(log n)) bit operations, where M(b) is the cost of one multiplication of two b-bit numbers.

For machine-word n (≤ 64 bits): O(log n) = O(64) modular multiplications, each one CPU instruction. Total per witness: hundreds of nanoseconds. With 7-12 witnesses for deterministic test, ~microseconds per number.

For RSA-scale n (~2048 bits): O(log n) ≈ 2048 modular multiplications, each O((log n)²) = O(4 · 10^6) bit operations with schoolbook (or faster with Karatsuba/Montgomery). Total per witness: ~milliseconds. With ~20 witnesses: tens of milliseconds. This is fast enough that prime generation for cryptography (millions of primality tests per key) is practical.

In big-O: O(k · log² n · log log n · log log log n) with FFT-based multiplication, or O(k · log³ n) with schoolbook. The cubic-log bound is the most-cited.

5.2 Space

O(log n) bits to store the candidate, the witnesses, and intermediate residues. Effectively O(1) machine words for fixed-precision arithmetic. The algorithm is streamy; no large auxiliary structures.

5.3 Error Probability

For each random witness, the probability that a composite n passes is at most 1/4 (proved in §6 — the Monier-Rabin theorem). After k independent witnesses, the probability of a composite passing all is at most 4^(-k) = 2^(-2k).

For k = 20: error ≤ 4^(-20) ≈ 10^(-12) — astronomically less likely than a hardware fault during the test. For k = 64: error ≤ 2^(-128), equivalent to a 128-bit cryptographic security parameter. In practice, k = 20 to k = 40 is more than sufficient for any application.

This 4^(-k) is a worst-case bound, attained only by adversarially structured composites. The far more relevant figure for random prime generation is the average-case error: when n is itself drawn at random (as in key generation) rather than chosen adversarially, the probability that a random k-witness run mislabels a composite as prime is dramatically smaller. Per the Wikipedia treatment, for most n this probability is bounded by 8^(-k) rather than 4^(-k), and Damgård–Landrock–Pomerance (1993) showed that for randomly chosen b-bit candidates the failure probability falls off far faster still — so production key generation with even modest k is safe. The intuition: most composites have far fewer than (n-1)/4 strong liars; the 1/4 ceiling is reached only by a sparse family of crafted composites that a random candidate is overwhelmingly unlikely to be.

For deterministic testing within known bounds (§7), the error probability is exactly 0.

6. Why It Works — The Monier-Rabin Theorem

6.1 The Key Lemma — Square Roots of Unity Mod a Prime

Lemma. If p is an odd prime, the only solutions to x² ≡ 1 (mod p) are x ≡ ±1 (mod p).

Proof. x² ≡ 1 (mod p) ⟺ p | (x² - 1) = (x - 1)(x + 1). Since p is prime, by Euclid’s lemma (a prime dividing a product divides one of the factors), p | (x - 1) or p | (x + 1), i.e., x ≡ 1 or x ≡ -1 (mod p).

Corollary. For composite n with multiple distinct prime factors, there exist x ≢ ±1 (mod n) with x² ≡ 1 (mod n). By the Chinese Remainder Theorem, if n = p · q with p, q distinct odd primes, then x ≡ 1 (mod p), x ≡ -1 (mod q) gives an x ≢ ±1 (mod n) with x² ≡ 1. So composites with ≥ 2 distinct odd prime factors always have non-trivial square roots of unity.

This is the structural fact Miller-Rabin exploits.

6.2 The Probability Bound — Monier 1980, Rabin 1980

Theorem (Monier, Rabin). For odd composite n > 9, the number of strong liars (witnesses a ∈ [1, n-1] for which the Miller-Rabin test passes) is at most (n - 1)/4.

Proof sketch. The set of strong liars is a subset of the multiplicative group (ℤ/nℤ)*, but it is generally not itself a subgroup. The argument has two parts:

  1. For n not a prime power: Use the Chinese Remainder Theorem decomposition (ℤ/nℤ)* ≅ ∏(ℤ/pᵢ^eᵢ ℤ)*. The strong liars are intersections of certain subsets in each factor; their density is at most 1/4 of the group order.

  2. For n a prime power p^k with k ≥ 2: Use Hensel’s lemma and direct counting in (ℤ/p^k ℤ)*. The bound is even tighter (≤ 1/p of the group, which for odd p is ≤ 1/3).

The full proof is in Monier 1980 and Rabin 1980. CLRS §31.8 gives a full but technical version.

The 1/4 is tight: for n = 9 exactly, the strong-liar fraction is 2/8 = 1/4. For most composites, the fraction of liars is far smaller — closer to 0 as n grows.

6.3 Composites for Which Many Witnesses Lie

Even though the average liar fraction is < 1/4, specific composites can have surprisingly many strong liars. Carmichael numbers are composite but pass the Fermat test for all coprime witnesses; they pass Miller-Rabin for some witnesses but not all. The smallest “really annoying” composite for Miller-Rabin is the strong pseudoprime simultaneously to bases {2, 3, 5, 7}: the number 3,215,031,751 = 151 · 751 · 28351. This is why deterministic witness sets need to be chosen carefully (§7).

7. Deterministic Witness Sets — Miller-Rabin Without Probabilistic Doubt

7.1 The Idea

For a fixed set of witnesses, there is a smallest composite n that fools them all (the “strong pseudoprime” to those bases). If we know that smallest n, then for any n below it, our witness set gives a deterministic primality test — zero error.

These bounds are tabulated in OEIS A014233 and refined over decades by careful number-theoretic computation. The most important entries:

7.2 The Standard Deterministic Witness Sets

WitnessesSmallest pseudoprimeImplication: Miller-Rabin is deterministic for n <
{2}2,0472,047
{2, 3}1,373,6531,373,653
{2, 3, 5}25,326,00125,326,001
{2, 3, 5, 7}3,215,031,7513,215,031,751
{2, 3, 5, 7, 11}2,152,302,898,7472.15 × 10¹²
{2, 3, 5, 7, 11, 13}3,474,749,660,3833.47 × 10¹²
{2, 3, 5, 7, 11, 13, 17}341,550,071,728,3213.42 × 10¹⁴
{2, 3, 5, 7, 11, 13, 17, 19, 23} (first 9 primes)3,825,123,056,546,413,0513.82 × 10¹⁸ (covers 2⁶³ but not all of 2⁶⁴ ≈ 1.84 × 10¹⁹)
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} (first 12 primes)3,317,044,064,679,887,385,961,981 (Sorenson–Webster 2017)3.317 × 10²⁴

So:

  • For all n < 3.215 × 10⁹ (about half a 32-bit unsigned), four witnesses {2, 3, 5, 7} make the test deterministic.
  • For all n < 3.42 × 10^14, seven witnesses {2, 3, 5, 7, 11, 13, 17} suffice.
  • For all n < 2^64, the first twelve primes {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} certainly suffice (since 2^64 ≈ 1.844 × 10^19 is far below their 3.317 × 10²⁴ bound), but a smaller curated set also works (Sinclair’s 7 bases, below). A common misconception is that the first nine primes {2, 3, 5, 7, 11, 13, 17, 19, 23} cover all 64-bit integers — they do not. Their A014233 bound is 3,825,123,056,546,413,051 ≈ 3.825 × 10^18, which is below both 2^63 ≈ 9.22 × 10^18 and 2^64 ≈ 1.844 × 10^19. So the first-nine-primes set is only deterministic up to ≈3.8 × 10^18 — fine for problems capped at 10^18, but insufficient for the full unsigned 64-bit range. To cover all of 2^64 using first-k-primes witnesses you need bases through 37 (the first twelve primes).
  • With the first twelve primes {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} the smallest strong pseudoprime — and hence the deterministic bound — is exactly ψ₁₂ = 3,317,044,064,679,887,385,961,981 ≈ 3.317 × 10²⁴. This was computed and published by Sorenson and Webster (2017), “Strong Pseudoprimes to Twelve Prime Bases” (Math. Comp. 86, 985–1003), and is recorded as the twelfth term of OEIS A014233. The verified bound is confirmed by Wikipedia’s deterministic-variants table, which states the same 25-digit integer. So Miller-Rabin with these twelve bases is a deterministic primality test for every n below ≈3.317 × 10²⁴ — comfortably covering all 64-bit and even 80-bit integers.
  • Beyond these bounds, no deterministic witness set is known unconditionally; we revert to probabilistic Miller-Rabin or use the deterministic AKS test (much slower).

For machine-word work, two practically useful curated sets are worth memorizing. First, the seven bases {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} (the first twelve primes) are deterministic well past 2^64. Second — and tighter — Jim Sinclair found that the seven bases {2, 325, 9375, 28178, 450775, 9780504, 1795265022} are deterministic for all n < 2^64; this is the set most competitive-programming templates actually use because seven modular exponentiations beat twelve. (These curated bases are not “first k primes” and so do not appear in A014233; they are empirically verified against the full 64-bit range.)

7.3 Generalized Riemann Hypothesis Variant

If the Generalized Riemann Hypothesis (GRH) is true, Miller (1976) showed that the multiplicative group (ℤ/nℤ)* is generated by its elements smaller than O((log n)²), so testing every base a in that range makes Miller-Rabin deterministic for every n. Eric Bach later pinned the constant down: under GRH it suffices to test all a ∈ [2, ⌊2 (ln n)²⌋] (per the Wikipedia derivation), giving an O((log n)⁴) deterministic test (with fast multiplication, lower). This is the original “Miller test,” sometimes distinguished from the randomized Miller-Rabin. Since GRH is unproven, this is not relied on for correctness in practice; the AKS test (2002) gives unconditional polynomial-time primality but is much slower for real-world sizes.

8. The Killer Applications

8.1 RSA Key Generation

To generate an RSA key, find two large primes p, q (~1024 bits each). The standard procedure: pick a random odd integer of the right size, run Miller-Rabin with ~40 witnesses, repeat until a probable prime is found. By the prime number theorem, ~1 in (log n) ≈ 700 random odd numbers near 2^1024 is prime, so on average ~700 trials suffice. Each trial is ~milliseconds, so key generation takes seconds.

The 40-witness count chosen in production crypto libraries gives error probability < 2^(-80), smaller than the probability of any other failure mode (RAM bit flips, etc.).

8.2 Cryptographic Random Number Generators

Some PRNGs need to find random primes for parameters (e.g., the q in DSA, the prime modulus in DH). Miller-Rabin is the standard test.

8.3 Number Theory Research

Searching for primes with specific properties — Mersenne primes 2^p - 1, Fermat primes 2^(2^k) + 1, Sophie Germain primes p with 2p + 1 also prime — uses Miller-Rabin for the “fast filter” before applying more specialized tests (Lucas-Lehmer for Mersenne, Pépin for Fermat).

8.4 Competitive Programming

For problems requiring primality of integers up to 10^18 or so, the deterministic 9-witness Miller-Rabin is the standard tool. Sieve of Eratosthenes precomputes primes up to ~10^7 in memory; Miller-Rabin handles individual queries beyond that range.

8.5 Smart Contract / Blockchain Cryptography

Modular arithmetic and primality are core to elliptic-curve operations on Ethereum and Bitcoin. Miller-Rabin (or its deterministic variants) verifies prime parameters in zero-knowledge proofs and zk-SNARK setups.

9. Diagram — One Witness’s Trace Through the Algorithm

flowchart TD
  A["Input n; check n is odd, > 3"] --> B["Decompose n - 1 = d · 2^s, d odd"]
  B --> C["x = a^d mod n"]
  C --> D{x == 1 or x == n-1?}
  D -->|yes| W["Witness a does not catch n;\ntry next witness"]
  D -->|no| E["Repeat at most s-1 times:"]
  E --> F["x = x² mod n"]
  F --> G{x == n-1?}
  G -->|yes| W
  G -->|no| H{Iterations exhausted?}
  H -->|no| F
  H -->|yes| Z["Composite!\nwitness a catches n"]
  W --> Y{More witnesses?}
  Y -->|yes| C
  Y -->|no| P["Probably prime\n(or deterministically prime if witness set is sufficient)"]

What this diagram shows. The control flow of Miller-Rabin for one witness a. After decomposing n - 1 = d · 2^s, we compute the initial residue x = a^d mod n (via Fast Exponentiation). If this is already 1 or n - 1, the witness can’t certify compositeness — proceed to the next witness. Otherwise, square x repeatedly up to s - 1 times. If at any point x ≡ n - 1, we’ve found a “trivial” square root of unity in the chain, and the witness passes (cannot catch). If we square s - 1 times without ever seeing n - 1, then the next squaring would give a^(n-1) mod n which by Fermat must be 1 if n is prime — but the value just before that 1 wasn’t ±1, so we found a non-trivial square root of unity. Composite. The diagram makes explicit that: a witness catches a composite either by Fermat-failing or by exposing a non-trivial square root of 1; otherwise it passes silently. The probability of passing is ≤ 1/4 per random witness, giving the famous 4^(-k) error bound after k independent witnesses.

10. Variants

10.1 Solovay-Strassen Test

Predecessor to Miller-Rabin (Solovay & Strassen, 1977). Tests whether a^((n-1)/2) ≡ (a/n) (mod n), where (a/n) is the Jacobi symbol. Error probability ≤ 1/2 per witness — worse than Miller-Rabin’s 1/4. Used historically; superseded by Miller-Rabin.

10.2 Baillie-PSW Test

A deterministic (no proven counterexamples) hybrid: run Miller-Rabin with witness 2, then a Lucas pseudoprime test. No counterexample is known up to at least 2^64, despite ~$30,000 in prize money offered for one. Some libraries (PARI/GP, sympy.isprime) use this as a fast deterministic test.

10.3 AKS Primality Test

Agrawal, Kayal, Saxena 2002: the first deterministic, polynomial-time, unconditional primality test. Runs in O((log n)^(6+ε)) (after improvements). Theoretically beautiful but practically much slower than Miller-Rabin or Baillie-PSW for any number under 10^1000 or so. Used to settle the theoretical question “is PRIMES in P?”, but not in production.

10.4 Elliptic Curve Primality Proving (ECPP)

Atkin and Morain (1993). Produces a certificate of primality verifiable in polynomial time, faster than AKS in practice for very large primes (thousands of digits). Used to verify world-record primes.

10.5 Lucas-Lehmer Test (Mersenne Specific)

M_p = 2^p - 1 is prime iff s_(p-2) ≡ 0 (mod M_p), where s_0 = 4, s_(k+1) = s_k² - 2. Specialized for Mersenne candidates; faster than general Miller-Rabin for these. Used by GIMPS (Great Internet Mersenne Prime Search) to find new Mersenne primes.

10.6 Pépin’s Test (Fermat Specific)

F_n = 2^(2^n) + 1 is prime iff 3^((F_n - 1)/2) ≡ -1 (mod F_n). Specialized to Fermat numbers.

10.7 Frobenius Pseudoprime Test

A more sophisticated test using polynomial arithmetic. Stronger error bound than Miller-Rabin per witness but more expensive. Not commonly implemented.

11. Pitfalls

11.1 Forgetting the Even-n Pre-Check

If n is even (and > 2), the decomposition n - 1 = d · 2^s works (since n - 1 is odd, d = n - 1, s = 0), but the algorithm is degenerate: we’d compute a^(n-1) mod n and check if it’s 1, with no squaring step (s - 1 = -1). Always check n % 2 == 0 first and return False (or True if n == 2).

11.2 Witness a == 0 or a Multiple of n

If a ≡ 0 (mod n), then a^d ≡ 0 and the test would falsely flag n as composite (since 0 is neither 1 nor n-1). Skip witnesses that are multiples of n. Random selection from [2, n-2] typically avoids this.

11.3 Witness a == n-1

(n-1)^d mod n: if d is odd, this is -1 mod n = n - 1, which the algorithm immediately accepts (passes the test). If d is even (impossible since we required d odd), would behave differently. So a = n - 1 always passes, and gives no information. Don’t bother including it in your witness set.

11.4 Confusing Strong Pseudoprime with Carmichael Number

A Carmichael number is a composite n such that a^(n-1) ≡ 1 (mod n) for all a coprime to n — passes the basic Fermat test for all coprime witnesses. A strong pseudoprime to base a is a composite that passes Miller-Rabin for the specific witness a. Every Carmichael number is a “Fermat liar” universally, but only some are strong-pseudoprime to specific bases. Miller-Rabin correctly catches Carmichael numbers (with probability ≥ 3/4 per witness) — the Carmichael property does NOT defeat Miller-Rabin.

11.5 Using Only One Witness

A single witness gives error ≤ 1/4, which sounds small but is way too high for any serious application. Use ≥ 20 random witnesses (probability < 10^(-12)) or a deterministic witness set for n in the bounded range.

11.6 Not Using gcd(a, n) > 1 as a Free Composite Detection

If gcd(a, n) > 1, then n shares a factor with a — you’ve found a divisor. This immediately certifies compositeness without running the rest of the test. Some implementations check gcd(a, n) == 1 upfront for code clarity; the gain is negligible since gcd > 1 is rare for random a against large n.

11.7 Off-By-One in the Squaring Loop

The inner loop squares s - 1 times, not s. The first squaring makes x = a^(2d); the last makes x = a^(2^(s-1) · d). The next squaring would give a^(n-1), which by Fermat is 1 — that’s the value we’re trying to back-check by seeing whether the previous value was n - 1. If you square s times, you cross the “1 boundary” without realizing it. Always exactly s - 1 iterations.

11.8 Forgetting That the Test Has Some Probability of Error

Miller-Rabin is probabilistic outside the deterministic bounds. Don’t claim “Miller-Rabin proves this number is prime” in a context where exact certainty is needed (e.g., a formal proof) — use AKS or ECPP instead. For all practical applications including all of cryptography, the probability is small enough to ignore.

11.9 Big-Integer Overflow in x * x mod n

For 64-bit n, x * x needs __int128 or 128-bit multiplication. For Python, no concern. For C/C++, static_cast<__int128>(x) * x % n is the standard idiom.

11.10 Performance Tip: Pre-Filter by Trial Division

Before running Miller-Rabin, divide n by small primes (up to ~50 or 100). Most random odd integers fail this fast filter (more than 90% are caught by primes ≤ 100). Only run the expensive Miller-Rabin on survivors. Production crypto code does this.

12. Common Interview Problems

ProblemLeetCode # / SourceConnection
Count PrimesLC 204Sieve up to n; Miller-Rabin for individual queries beyond sieve range
Closest Prime in [L, R] for huge RcompetitiveMiller-Rabin per candidate
Find next prime ≥ ncompetitiveMiller-Rabin loop
Generate RSA-style key parameterscrypto courseworkMiller-Rabin to test 1024-bit candidates
Prime Factorization of huge ncompetitiveMiller-Rabin to test if prime; Pollard’s rho if composite
Check primality of a single 64-bit numbercompetitive standardDeterministic Miller-Rabin with Sinclair’s 7 bases (or first-12-primes); the first-9-primes set only covers up to ≈3.8×10¹⁸ < 2⁶⁴
Largest prime factorLC / Project Euler 3Trial division + Miller-Rabin for the remainder
Goldbach Conjecture verificationcompetitiveIterate over primes (sieve-based) and verify
Find safe prime p (with (p-1)/2 also prime)cryptoMiller-Rabin twice
Verify a claimed RSA modulus is compositecrypto / forensicMiller-Rabin (often catches bad primes immediately)

13. Open Questions

  • Is the Baillie-PSW test deterministic? Empirically yes up to extensive bounds (no counterexample known up to 2^80 and likely far beyond), but no proof. A proof would require a structural understanding of strong pseudoprimes that mathematicians don’t yet possess.
  • Are there infinitely many strong pseudoprimes to all bases simultaneously? Analogous to the Carmichael question. The conjecture is yes (the “Erdős conjecture” is for Fermat, and similar reasoning applies). Proven only conditionally on extensions of the prime number theorem.
  • Could Miller-Rabin’s 4^(-k) be improved with cleverer witness selection? The bound is information-theoretically tight in the worst case (some composites have exactly 1/4 strong liars). But average-case the bound is much smaller; selecting witnesses adaptively (e.g., from prior knowledge) gives better practical bounds.
  • What is the smallest pseudoprime simultaneously to all primes ≤ 100? Currently unknown beyond the entries in OEIS A014233; an open computational question.

14. See Also

Graph View

Backlinks