18.19 Miller-Rabin Primality Test
The Miller-Rabin test is the practical standard for fast primality testing.
18.19 Miller-Rabin Primality Test
The Miller-Rabin test is the practical standard for fast primality testing. It improves on Fermat's test by checking not only whether a number satisfies a modular exponent identity, but also whether its square-root structure behaves like a prime.
For large integers, trial division is too slow. Fermat testing is faster, but can be fooled by Carmichael numbers. Miller-Rabin keeps the speed of modular exponentiation while detecting far more composite numbers.
Problem
Given an odd integer:
n > 2
determine whether n is probably prime or definitely composite.
The test is probabilistic in its general form:
composite → always detected by some bases
probably prime → passed all tested bases
For fixed-width integers, carefully chosen bases make the test deterministic.
Starting Point
Fermat's Little Theorem says that if n is prime and a is not divisible by n, then:
a^(n-1) ≡ 1 (mod n)
Fermat's test checks this directly.
Miller-Rabin refines the test by factoring:
n - 1
into:
n - 1 = 2^s × d
where d is odd.
This decomposition lets us inspect the chain:
a^d
a^(2d)
a^(4d)
...
a^(2^s d)
The last value is:
a^(n-1)
which should be 1 for prime n.
Key Observation
For an odd prime n, the only square roots of 1 modulo n are:
1
-1
That means if a repeated squaring chain eventually reaches 1, then immediately before that it should have been either 1 or -1.
Miller-Rabin uses this fact to detect composites that pass Fermat's test.
Decomposing n - 1
To run the test, write:
n - 1 = 2^s × d
with d odd.
Example:
n = 21
Then:
n - 1 = 20 = 2^2 × 5
So:
s = 2
d = 5
Implementation:
def decompose(n):
d = n - 1
s = 0
while d % 2 == 0:
d //= 2
s += 1
return s, d
One Miller-Rabin Round
A single test round chooses a base a.
First compute:
x = a^d mod n
If:
x = 1
or:
x = n - 1
then this base passes.
Otherwise, repeatedly square:
x = x^2 mod n
up to s - 1 times.
If any squared value becomes:
n - 1
then this base passes.
If none do, n is definitely composite.
Implementation of One Round
def miller_rabin_round(n, a, s, d):
x = pow(a, d, n)
if x == 1 or x == n - 1:
return True
for _ in range(s - 1):
x = x * x % n
if x == n - 1:
return True
return False
The return value means:
True → base a did not prove compositeness
False → base a proved n is composite
Complete Probabilistic Test
import random
def is_probable_prime(n, rounds=20):
if n < 2:
return False
small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
for p in small_primes:
if n == p:
return True
if n % p == 0:
return False
s, d = decompose(n)
for _ in range(rounds):
a = random.randrange(2, n - 2)
if not miller_rabin_round(n, a, s, d):
return False
return True
This function quickly rejects composites and returns True only when all tested bases pass.
Example: Detecting a Composite
Test:
n = 21
Decompose:
20 = 2^2 × 5
Choose:
a = 2
Compute:
x = 2^5 mod 21 = 32 mod 21 = 11
This is neither:
1
nor:
20
Square once:
11^2 mod 21 = 121 mod 21 = 16
This is still not:
20
The base 2 proves that 21 is composite.
Example: A Prime Passes
Test:
n = 17
Decompose:
16 = 2^4 × 1
Choose:
a = 3
Compute:
x = 3^1 mod 17 = 3
Now square:
3^2 mod 17 = 9
9^2 mod 17 = 13
13^2 mod 17 = 16
We reached:
-1 mod 17
which is:
16
So base 3 passes.
Witnesses and Liars
If a base a proves that n is composite, a is called a witness.
If n is composite but base a still passes, a is sometimes called a strong liar.
The power of Miller-Rabin is that for any odd composite n, at most one quarter of possible bases are strong liars. Randomly chosen bases therefore reduce the error probability rapidly.
After k independent random rounds, the probability of a composite passing all rounds is at most:
(1/4)^k
In practice, far fewer composites survive than this worst-case bound suggests.
Deterministic Miller-Rabin for 64-Bit Integers
For 64-bit unsigned integers, Miller-Rabin can be made deterministic by testing a fixed set of bases.
One commonly used set is:
2, 3, 5, 7, 11, 13, 17
This works for many practical ranges, but not the full 64-bit range.
For all numbers below 2^64, a known sufficient witness set is:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37
Another compact 64-bit set often used in implementations is:
2, 325, 9375, 28178, 450775, 9780504, 1795265022
These bases make the test exact for 64-bit integers.
Deterministic Implementation
def is_prime_64(n):
if n < 2:
return False
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
s, d = decompose(n)
witnesses = [
2,
325,
9375,
28178,
450775,
9780504,
1795265022,
]
for a in witnesses:
a %= n
if a == 0:
continue
if not miller_rabin_round(n, a, s, d):
return False
return True
In Python, multiplication does not overflow. In fixed-width languages, modular multiplication must be implemented carefully for large n.
Complexity
Each Miller-Rabin round performs modular exponentiation.
For machine integers, one round is effectively:
O(log n)
multiplications.
For arbitrary-precision integers, the bit complexity depends on the multiplication algorithm. A useful high-level estimate is:
O(k log^3 n)
for k rounds using classical big-integer multiplication.
Space usage is:
O(1)
besides the storage needed for big integers.
Why Miller-Rabin Beats Fermat
Fermat checks only:
a^(n-1) ≡ 1 (mod n)
Miller-Rabin checks the path that reaches that value.
A composite number may satisfy the final Fermat condition but still have an invalid square-root chain. Miller-Rabin catches that failure.
This is why Carmichael numbers can fool Fermat testing but are much less effective against Miller-Rabin.
Common Mistakes
Testing Even Numbers Late
Handle even numbers immediately. Miller-Rabin is designed for odd candidates.
Forgetting Small Primes
Small primes simplify edge cases and reject many composites cheaply.
Choosing Invalid Random Bases
Use bases in:
2 ≤ a ≤ n - 2
For small n, handle cases before random selection.
Treating Probable Prime as Proven Prime
Random Miller-Rabin gives high confidence, not a proof. For bounded integer ranges, deterministic witness sets provide exact results.
Ignoring Overflow
In C, C++, Go, Rust, or Java, x * x % n can overflow before reduction. Use 128-bit arithmetic, Montgomery multiplication, or a safe modular multiplication routine.
Testing
Basic tests:
def test_miller_rabin_small():
primes = [2, 3, 5, 7, 11, 13, 17, 19, 97]
composites = [1, 4, 6, 8, 9, 15, 21, 25, 91, 561]
for p in primes:
assert is_prime_64(p)
for c in composites:
assert not is_prime_64(c)
Compare against trial division for small ranges:
def trial_is_prime(n):
if n < 2:
return False
d = 2
while d * d <= n:
if n % d == 0:
return False
d += 1
return True
def test_against_trial_division():
for n in range(1, 10000):
assert is_prime_64(n) == trial_is_prime(n)
Include Carmichael numbers:
def test_carmichael_numbers():
for n in [561, 1105, 1729, 2465, 2821, 6601]:
assert not is_prime_64(n)
These are useful regression tests because they expose weak Fermat-style implementations.
Takeaway
Miller-Rabin is a fast and reliable primality test based on modular exponentiation and the square-root structure of prime fields. It decomposes n - 1 into 2^s d, tests selected bases, and rejects n if the resulting squaring chain cannot occur for a prime. Random bases give a strong probabilistic test, while known witness sets make the algorithm deterministic for fixed-width integers. Miller-Rabin is the practical default for testing large candidate primes before factorization, cryptography, and advanced number-theoretic algorithms.