Miller-Rabin Primality Test

How the test works

Given an odd integer n > 3 to test for primality, the algorithm proceeds in four steps:

1. Strip out powers of 2 from n−1. Write n − 1 = 2^r · d where d is odd. This is just repeated halving of n − 1 until it's odd; r is the number of halvings.
2. Pick a random base a ∈ [2, n−2]. Anything coprime to n works in principle, but a uniformly random base gives the strongest guarantee against composites.
3. Compute x = a^d mod n by fast modular exponentiation (square-and-multiply, O(log d) multiplications).
4. Check the squaring chain. If x = 1 or x = n − 1, accept (inconclusive). Otherwise square x up to r − 1 times. If you ever see x = n − 1, accept. If you never do, declare n composite — a is a witness.

The whole test takes O(log³ n) bit operations per round. Repeating k rounds with independent random bases multiplies the error: any single round's error is at most 1/4, so k rounds give error at most (1/4)^k.

Why does the squaring chain work?

The test rests on a simple fact about ℤ/nℤ when n is prime: the only square roots of 1 modulo a prime are ±1. If p is prime and x² ≡ 1 (mod p), then p divides x² − 1 = (x − 1)(x + 1), so p divides x − 1 or x + 1, meaning x ≡ ±1 (mod p).

By Fermat's Little Theorem, aⁿ⁻¹ ≡ 1 (mod n) when n is prime. Factor n − 1 = 2^r · d. Then aⁿ⁻¹ = (a^d)^2r. The sequence a^d, a^2d, a^4d, …, aⁿ⁻¹ is repeated squaring; it must end at 1. For a prime, the only way to reach 1 by squaring is via ±1 — so the sequence either starts at 1 or hits −1 somewhere along the way.

If neither happens, then some intermediate square root of 1 is neither +1 nor −1 — impossible mod a prime. So n is definitely composite, and a is the witness.

Worked example — n = 561 (Carmichael)

The smallest Carmichael number is 561 = 3 · 11 · 17. It fools Fermat's test for every base coprime to 561. Watch how Miller-Rabin catches it.

n = 561
n − 1 = 560 = 2⁴ · 35
so r = 4, d = 35

Pick a = 2.
x = 2³⁵ mod 561

2³⁵ mod 561 — compute by square-and-multiply:
2¹ = 2
2² = 4
2⁴ = 16
2⁸ = 256
2¹⁶ = 256² mod 561 = 65536 mod 561 = 460
2³² = 460² mod 561 = 211600 mod 561 = 103
2³⁵ = 2³² · 2² · 2¹ = 103 · 4 · 2 = 824 mod 561 = 263

So x = 263. Neither 1 nor 560 (n−1). Keep squaring:

x² = 263² mod 561 = 69169 mod 561 = 166      ≠ ±1
x⁴ = 166² mod 561 = 27556 mod 561 = 67       ≠ ±1
x⁸ = 67²  mod 561 = 4489  mod 561 = 1        ← Nontrivial √1 of unity!

We reached 1 by squaring something that wasn't ±1: 67² ≡ 1 (mod 561). For a prime, this is impossible. So 561 is composite — and a = 2 is the witness.

Fermat's test would have computed aⁿ⁻¹ = a⁵⁶⁰ = 1 (Fermat-correct), declared inconclusive, and missed the compositeness. Miller-Rabin sees the rogue square root along the way and flags it.

Proof sketch — at least 3/4 of bases are witnesses

Rabin proved (1980) that for any composite n, the set of bases a ∈ (ℤ/nℤ)* that fail to witness — the set of so-called "strong liars" — has cardinality at most φ(n)/4. So at least three quarters of the bases are witnesses.

The proof sketch:

• Strong liars form a subgroup of (ℤ/nℤ)*.
• For composite n with at least two distinct prime factors, this subgroup has index ≥ 4 (uses the Chinese Remainder Theorem to split (ℤ/nℤ)* by prime factor).
• By Lagrange, a subgroup of index ≥ 4 has at most φ(n)/4 elements.

So picking a uniformly random a gives witness probability ≥ 3/4 per round. k rounds give error ≤ (1/4)^k. The bound is tight for some composites (worst-case roughly 1/4) but is much smaller for most n in practice — for random 1024-bit candidates, a single Miller-Rabin round catches all observed composites.

JavaScript — Miller-Rabin with 40 rounds

// BigInt version — handles arbitrarily large n
function modPow(base, exp, mod) {
  let result = 1n;
  base = base % mod;
  while (exp > 0n) {
    if (exp & 1n) result = (result * base) % mod;
    exp >>= 1n;
    base = (base * base) % mod;
  }
  return result;
}

function millerRabin(n, k = 40) {
  if (n < 2n) return false;
  if (n === 2n || n === 3n) return true;
  if ((n & 1n) === 0n) return false;

  // Write n − 1 = 2^r · d with d odd
  let d = n - 1n;
  let r = 0n;
  while ((d & 1n) === 0n) { d >>= 1n; r++; }

  outer: for (let i = 0; i < k; i++) {
    // Pick random base a in [2, n − 2]
    const a = 2n + BigInt(Math.floor(Math.random() * Number(n - 4n)));
    let x = modPow(a, d, n);
    if (x === 1n || x === n - 1n) continue;
    for (let j = 0n; j < r - 1n; j++) {
      x = (x * x) % n;
      if (x === n - 1n) continue outer;
    }
    return false;  // a is a witness — n composite
  }
  return true;     // probably prime: error ≤ (1/4)^k
}

millerRabin(561n);       // false  ← catches the Carmichael
millerRabin(1000003n);   // true   ← 1000003 is prime
millerRabin(2n ** 521n - 1n);  // true — Mersenne prime M521

Variants

Test	Type	Per-round error	Catches Carmichaels?	Time
Trial division	Deterministic	0	Yes	O(√n) — infeasible past ~10¹⁵
Fermat test	Probabilistic	≤ 1/2 (composites only)	No — always fails on Carmichaels	O(log³ n) per round
Solovay-Strassen	Probabilistic	≤ 1/2	Yes (via Jacobi symbol)	O(log³ n) per round
Miller-Rabin	Probabilistic	≤ 1/4	Yes (square-root check)	O(log³ n) per round
Baillie-PSW	Probabilistic	No known counterexample	Yes	~2 × Miller-Rabin
AKS (2002)	Deterministic	0	Yes	O(log⁶ n) — slow constants
ECPP	Deterministic certificate	0	Yes	Heuristic O(log⁴ n)

Common pitfalls

• Using non-cryptographic randomness for bases. Pinch's tables list pseudoprimes that pass Miller-Rabin for specific small base sets. With a PRNG seeded predictably, an attacker can craft a composite n that passes your test. Use a CSPRNG to draw bases in security-sensitive code.
• Skipping the trivial cases. Always handle n < 2, n = 2, n = 3, and even n directly. The main loop assumes n is odd and > 3.
• Confusing the two acceptance conditions. The test accepts if either x = 1 at the start, or some squaring step produces n − 1. Both forms are needed; checking only one misses witnesses.
• Off-by-one in the squaring loop. You square at most r − 1 times after the initial a^d, because a^2r·d = aⁿ⁻¹ is the final value and we don't care about it (Fermat says it's 1 if n is prime).
• Believing "1 round is enough" for crypto. 1 round gives error ≤ 1/4 — completely unacceptable for key generation. NIST FIPS 186-5 mandates at least 40 rounds for 1024-bit prime candidates; OpenSSL defaults to ~64.
• Calling it AKS-equivalent. Miller-Rabin is probabilistic; AKS is deterministic. Miller-Rabin's 2⁻⁸⁰ error rate is, in practice, smaller than the chance of a hardware fault during the test — but it is not zero, and that distinction matters for some applications (formal proofs, ECPP certificates).

Applications

• RSA key generation. Generating 2048-bit RSA primes scans ~700 candidates on average; each is screened with small-prime trial division then 40+ rounds of Miller-Rabin. OpenSSL, BoringSSL, GMP, mbedTLS, libsodium — every modern TLS library uses Miller-Rabin here.
• Diffie-Hellman parameter generation. Safe primes p with (p−1)/2 also prime are found by Miller-Rabin on both p and (p−1)/2.
• Elliptic curve parameter generation. Generating prime-order subgroups for ECC (P-256, Curve25519) requires testing curve order primality — Miller-Rabin again.
• Cryptographic library defaults. Python's sympy.isprime, Java's BigInteger.isProbablePrime, Go's big.Int.ProbablyPrime all use Miller-Rabin (often combined with Baillie-PSW Lucas tests as belt-and-suspenders).
• Competitive programming & CTFs. Standard tool for 64-bit-range primality where trial division is too slow. Deterministic with fixed bases {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} for all n < 3.3 · 10²⁴.
• Mersenne and large-prime hunting. GIMPS uses Lucas-Lehmer for the Mersenne-specific final test, but Miller-Rabin and trial division pre-filter candidates aggressively.

A bit of history

Gary Miller (1976) gave a deterministic test conditional on the Generalized Riemann Hypothesis: testing all bases up to 2(ln n)² suffices. Without GRH, Michael Rabin (1980) turned Miller's test into the randomized algorithm we use today, proving the 3/4 witness density.

The Miller-Rabin pseudoprimes — composites that fool the test for specific base sets — have been catalogued for small base lists, giving deterministic bounds: bases {2, 3} decide primality for all n < 1.4 · 10⁹; {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} decide for all n < 3.3 · 10²⁴ (Sorenson & Webster 2017). Beyond that range, randomization is the standard.