Factoring a 300-digit number is infeasible — yet cryptography needs to generate huge primes constantly. Miller–Rabin tests primality without factoring. Write n−1 = 2ˢ·d, pick a base a, and check whether the chain aᵈ, a²ᵈ, a⁴ᵈ, … (mod n) behaves the way it must for a prime. If it doesn’t, a is a witness that proves n composite — with certainty. If it does, n is probably prime, and each extra base you try cuts the error to at most 4⁻ᵏ. Test bases and watch composites get caught.
O(k · log³ n) · one witness = certainly composite · k passes = prime, error ≤ 4⁻ᵏ
n − 1 = 2ˢ·d
Factor out all the twos: d is odd, s counts the twos removed.
base a
A number tested as a potential witness against n’s primality.
witness
A base whose square-chain misbehaves — it proves n is composite, no doubt.
probably prime
Passing k bases leaves error ≤ 4⁻ᵏ — vanishing fast with more bases.
miller-rabin.js — witnesses and pseudoprimes
Ready
Testing a number for primality. We factor n−1 = 2ˢ·d, then try bases one at a time. A base whose modular-square chain misbehaves is a witness proving n composite. Test base to begin.
0
bases tried
?
verdict
–
max error
How it works
The test rests on a fact about primes: modulo a prime, the only square roots of 1 are +1 and −1. For a prime n, the chain aᵈ, a²ᵈ, …, a²ˢ⁻¹ᵈ must therefore either start at 1, or hit n−1 somewhere before the end (so that squaring it gives 1 legitimately). If a base produces a chain that reaches 1 having not passed through n−1 — a “nontrivial square root of 1” — then n cannot be prime, and that base is a witness. The deep guarantee is that at least three-quarters of all bases are witnesses for any composite, so each random base you pass shrinks the error by a factor of four.
1
Factor out the twos
Write n − 1 = 2ˢ · d with d odd. This exposes the chain of s squarings the test will inspect.
2
Compute the base’s chain
For base a, compute aᵈ mod n, then keep squaring: a²ᵈ, a⁴ᵈ, …, up to s−1 squarings.
3
Check the chain
It passes if the first value is 1, or if any value in the chain equals n−1. Otherwise the base is a witness — n is composite, with certainty.
✓
Repeat to shrink the error
One witness proves composite for good. If a base passes, try more: at least ¾ of bases witness any composite, so after k passing bases the chance n is actually composite is at most 4⁻ᵏ.
Time
O(k · log³ n)
One witness
certainly composite
k passes
error ≤ 4⁻ᵏ
Used in
RSA key-gen
The code
# one Miller-Rabin round for odd n > 2 and base adef is_probable_prime(n, a):
d, s = n - 1, 0
while d % 2 == 0: d //= 2; s += 1 # n-1 = 2^s * d
x = pow(a, d, n) # a^d mod nif x == 1 or x == n - 1: return True # passes this basefor _ in range(s - 1):
x = x * x % n # square up the chainif x == n - 1: return True # reached -1: okreturn False # a is a WITNESS -> composite
Quick check
1. What does it mean when a base is a "witness" in Miller–Rabin?
A witness is a definitive proof of compositeness. Its modular-square chain misbehaves in a way impossible for a prime, so a single witness settles the question — n is composite, no probability involved.
2. What does passing k random bases tell you?
At least three-quarters of bases are witnesses for any composite, so a composite has at most a ¼ chance of fooling one random base — and 4⁻ᵏ of fooling k of them. Passing k bases means prime with error ≤ 4⁻ᵏ.
3. Why does Miller–Rabin beat the Fermat primality test?
Carmichael numbers pass the Fermat test for every base coprime to n, so Fermat can be fooled with certainty. Miller–Rabin’s stronger square-root condition exposes them — every appropriate base witnesses a Carmichael number.
FAQ
What is the Miller–Rabin primality test?
A probabilistic algorithm that tests primality without factoring. It writes n − 1 = 2ˢ·d, then for a base a checks whether the chain aᵈ, a²ᵈ, … mod n behaves as it must for a prime. If not, a is a witness proving n composite for certain; if it passes, n is probably prime, with error ≤ 4⁻ᵏ after k bases.
Is Miller–Rabin ever wrong?
It never calls a prime composite — a witness is a proof. It can, with probability ≤ 4⁻ᵏ, call a composite "probably prime" if every base is a non-witness, but that shrinks fast. For numbers below known bounds, testing a fixed base set makes it fully deterministic.
What is a Carmichael number and why does it matter here?
A composite that passes the Fermat test for every coprime base, making Fermat unreliable. Miller–Rabin’s stronger square-root condition exposes them — every suitable base witnesses a Carmichael number — which is a main reason it’s preferred over Fermat.
Where is Miller–Rabin used?
Prime generation in cryptography — RSA, Diffie–Hellman, and DSA all need large random primes, and Miller–Rabin tests candidates fast. Libraries run several rounds so the error is negligible, sometimes with a deterministic follow-up.