Miller–Rabin Primality Test

Miller–Rabin Primality Test (also known as the Rabin–Miller primality test) is a polynomial-time algorithm in computation and algorithms that determines whether a given odd integer n > 2 is composite or probably prime. First formulated by Gary L. Miller in 1976 as a deterministic polynomial-time algorithm conditional on the unproven Extended Riemann Hypothesis (ERH), and subsequently transformed by Michael O. Rabin in 1980 into an unconditional randomized Monte Carlo algorithm in the complexity class coRP (and BPP within computational complexity theory), the Miller–Rabin test is the industry-standard method for generating large cryptographic primes across the RSA cryptosystem, Diffie–Hellman key exchange, and digital signature standards (FIPS 186-5).

Unlike the simpler Fermat primality test—which checks only aⁿ⁻¹ ≡ 1 (mod n) and fails unconditionally on Carmichael numbers (such as 561 = 3 × 11 × 17, which satisfy aⁿ⁻¹ ≡ 1 mod n for every base a coprime to n)—the Miller–Rabin test eliminates Carmichael numbers by factoring n − 1 = 2^s d with d odd and inspecting the entire squaring chain a^d, a^2d, a^4d, ..., a^2sd (mod n) for non-trivial square roots of 1 modulo n. By the Monier–Rabin theorem (1980), every odd composite integer n has at least 3/4 of all bases a ∈ {1, ..., n − 1} as strong witnesses to its compositeness, ensuring that k independent random rounds yield a false-prime probability of at most 4^−k = 2^−2k.

Why Fermat's Test Fails on Carmichael Numbers

By Fermat's Little Theorem, if p is prime and 1 ≤ a ≤ p − 1, then:

If an odd integer n satisfies aⁿ⁻¹ ≢ 1 (mod n) for some base a ∈ {1, ..., n − 1}, then n is certainly composite, and a is called a Fermat witness for the compositeness of n. However, the converse fails: there exist infinitely many composite integers n (proved by Alford, Granville, and Pomerance in 1994), known as Carmichael numbers (561, 1105, 1729, 2465, 2821, ...), that are square-free products of at least three primes p₁ p₂ ··· p_r satisfying (p_i − 1) | (n − 1) for all i. For a Carmichael number n, aⁿ⁻¹ ≡ 1 (mod n) holds for every a with gcd(a, n) = 1, rendering the pure Fermat test helpless unless a happens to share a prime factor with n.

Only ±1 Are Square Roots of 1 Modulo a Prime

The Miller–Rabin test strengthens Fermat's Little Theorem with a second algebraic property unique to fields ℤ_p (where p is prime): the quadratic polynomial x² − 1 ≡ (x − 1)(x + 1) ≡ 0 (mod p) has only the two trivial roots x ≡ 1 and x ≡ −1 ≡ p − 1 (mod p), because ℤ_p is an integral domain with no zero divisors.

In contrast, if n is an odd composite integer with at least two distinct odd prime factors (such as any Carmichael number), then by the Chinese Remainder Theorem the congruence x² ≡ 1 (mod n) possesses at least four distinct solutions, including non-trivial square roots of unity x ≢ ±1 (mod n) (for example, modulo n = 15, x = 4 satisfies 4² = 16 ≡ 1 mod 15, and gcd(4 − 1, 15) = 3 directly splits n).

The Strong Pseudoprimality Condition

Let n > 2 be an odd integer. Because n − 1 is even, factor out all powers of 2 from n − 1 by counting trailing zero bits:

For any base a ∈ {1, 2, ..., n − 1}, consider the sequence of s + 1 successive squares modulo n:

If n is prime, then x_s = aⁿ⁻¹ mod n = 1 by Fermat's Little Theorem. Reading the sequence backward from x_s = 1 toward x₀, the first entry before a 1 cannot be a non-trivial root of unity: either every entry down to x₀ equals 1, or the entry directly preceding the first 1 equals −1 ≡ n − 1 (mod n). Thus, if n is prime, every base a ∈ {1, ..., n − 1} must satisfy at least one of the two strong primality conditions:

1. a^d ≡ 1 (mod n), OR
2. ∃ r ∈ {0, 1, ..., s − 1} such that a^2rd ≡ −1 ≡ n − 1 (mod n).

Any base a that violates both conditions—meaning a^d ≢ 1 (mod n) and a^2rd ≢ n − 1 (mod n) for all 0 ≤ r ≤ s − 1—is a Miller–Rabin witness proving with 100% mathematical certainty that n is composite. Conversely, if n is composite but satisfies (1) or (2) for a particular base a, n is called a strong pseudoprime to base a, and a is a strong liar for n.

Step-by-Step Randomized Miller–Rabin Algorithm

Given an odd integer n > 3 and a security parameter k ≥ 1 (number of rounds):

1. Factor n − 1: Write n − 1 = 2^s · d with d odd by shifting n − 1 right by s = ctz(n − 1) bits.
2. Witness Loop (Repeat k times):
   • 2a. Sample a base a uniformly at random from {2, 3, ..., n − 2}.
   • 2b. Compute x ← a^d mod n using binary modular exponentiation.
   • 2c. If x == 1 or x == n − 1, this base a passes; continue to the next iteration of the k-round loop.
   • 2d. Repeat s − 1 times (for r = 1 to s − 1):
   • Update x ← x² mod n.
   • If x == n − 1, this base a passes; break out of the inner r-loop and continue to the next k-round iteration.
   • (Optional early-exit: if x == 1 without having seen n − 1 on the directly preceding step, a non-trivial square root of 1 has been found, so return COMPOSITE directly.)
   • 2e. If the inner loop finishes s − 1 squarings without ever seeing x == n − 1, return COMPOSITE (base a is a witness).
3. Probable Prime Output: If all k independent bases pass, return PROBABLY PRIME.

Using schoolbook modular multiplication, each round performs O(log n) modular multiplications of (log n)-bit integers, taking O(k (log n)³) bit operations—or O(k (log n)² log log n) when combined with Cooley–Tukey FFT algorithm / Schönhage–Strassen / Harvey–van der Hoeven fast multiplication.

The Monier–Rabin Theorem and Average-Case Damgård–Landrock–Pomerance Bounds

In 1980, Louis Monier and Michael O. Rabin independently proved that for every odd composite integer n > 9, the number of strong liars L(n) in {1, 2, ..., n − 1} is bounded by:

where φ(n) is Euler's totient function (with equality L(n) = φ(n)/4 approached only by twin-prime products of the form n = (3m + 1)(6m + 1) such as 9 × 1 = 9 or Carmichael numbers of specific 3-prime structure). Consequently, across k independent uniform bases a₁, ..., a_k:

• If n is prime: Pr[Output = PROBABLY PRIME] = 1 (zero false negatives for primality).
• If n is composite: Pr[Output = PROBABLY PRIME] ≤ (1/4)^k = 2^−2k.

Even stronger bounds hold when testing a randomly chosen odd b-bit integer n to generate cryptographic keys: Ronald Damgård, Peter Landrock, and Carl Pomerance (1993) proved that the posterior probability p_b,k that a random b-bit integer passing k rounds of Miller–Rabin is actually composite decreases vastly faster than 4^−k because composite numbers with near-1/4 liar density are exceptionally sparse. For a random 2,048-bit integer, just k = 4 rounds reduce the posterior composite error probability below 2⁻¹²⁸.

Under the Extended Riemann Hypothesis (ERH), Eric Bach (1990) proved that the smallest Miller–Rabin witness for any odd composite n is at most 2(ln n)², making Gary Miller's deterministic test run in Õ((log n)⁴) time by testing all bases a ≤ 2(ln n)².

For fixed machine-word sizes (n < 2⁶⁴), exhaustive distributed searches by Pomerance, Selfridge, Wagstaff (1980), Jaeschke (1993), and Sorenson and Webster have determined the precise smallest strong pseudoprimes, yielding 100% deterministic constant-time primality tests with zero randomness:

• For all n < 2,047: testing the single base a ∈ {2} suffices deterministically.
• For all n < 4,759,123,141 (> 2³²): testing the 3 bases a ∈ {2, 7, 61} suffices deterministically.
• For all n < 2⁶⁴ = 18,446,744,073,709,551,616: testing the 7 prime bases a ∈ {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} (the first 12 primes) or the 7 Sinclair bases {2, 325, 9375, 28178, 450775, 9780504, 1795265022} determines primality with zero error across the entire 64-bit unsigned integer range, often paired with Pollard's rho algorithm to factor composite 64-bit integers in microseconds.

If the AKS algorithm (2002) proved that primality testing is in deterministic polynomial time P, why is Miller–Rabin still used everywhere?

While Manindra Agrawal, Neeraj Kayal, and Nitin Saxena's landmark 2002 AKS primality test resolved a centuries-old theoretical question by proving unconditionally that PRIMES ∈ P in Õ((log n)⁶) time, verifying a single 2,048-bit prime with AKS requires evaluating polynomials of degree ~10⁶ modulo n and takes several seconds to minutes, whereas 64 rounds of Miller–Rabin take under 2 milliseconds and achieve an error bound of 4⁻⁶⁴ = 2⁻¹²⁸ (orders of magnitude smaller than the probability of a cosmic-ray hardware bit flip).

How can finding a non-trivial square root of 1 in Miller–Rabin directly factor n?

Whenever the squaring loop encounters an integer x ≢ ±1 (mod n) such that x² ≡ 1 (mod n), we have n | (x² − 1) = (x − 1)(x + 1), yet n divides neither (x − 1) nor (x + 1). Computing gcd(x − 1, n) via the Euclidean algorithm directly returns a non-trivial factor of n—the precise mechanism used to recover the private key from a public/private exponent pair (e, d) in the RSA cryptosystem.

1. Miller, G. L. (1976). "Riemann's hypothesis and tests for primality." Journal of Computer and System Sciences, 13(3), 300–317. https://doi.org/10.1016/S0022-0000(76)80043-880043-8)
2. Rabin, M. O. (1980). "Probabilistic algorithm for testing primality." Journal of Number Theory, 12(1), 128–138. https://doi.org/10.1016/0022-314X(80)90084-090084-0)
3. Monier, L. (1980). "Evaluation and comparison of two efficient probabilistic primality testing algorithms." Theoretical Computer Science, 12(1), 97–108. https://doi.org/10.1016/0304-3975(80)90007-990007-9)
4. Damgård, I., Landrock, P., & Pomerance, C. (1993). "Average case error estimates for the strong probable prime test." Mathematics of Computation, 61(203), 177–194. https://doi.org/10.1090/S0025-5718-1993-1189518-9
5. Agrawal, M., Kayal, N., & Saxena, N. (2004). "PRIMES is in P." Annals of Mathematics, 160(2), 781–793. https://doi.org/10.4007/annals.2004.160.781