The idea: test for primes, don't factor
An RSA key needs two primes of about 1024 bits each. A sieve cannot reach numbers that big, and trial division would take longer than the age of the universe. Instead a library picks a random odd number n and tests it: it picks a base a, computes one modular power, and checks a property every prime has. If the check fails, n is certainly composite and a is a witness. If it passes, n is probably prime; a few more bases make "probably" as sure as you like.
The Fermat test
Fermat's little theorem says that for a prime p and any a it does not divide, ap − 1 ≡ 1 (mod p). So compute an − 1 mod n. If the result is not 1, n is not prime: 2⁹⁰ mod 91 = 64, so 91 is composite, and the test never found the factors 7 and 13 (Demo: Fermat catches 91 (a = 2)). For the prime 97, 2⁹⁶ mod 97 = 1 (Demo: Fermat test, 97 passes (a = 2)). The power takes about log₂ n squarings with square-and-multiply, so even a 2048-bit n needs only a few thousand multiplications.
The catch: some composites pass. 341 = 11·31, yet 2³⁴⁰ mod 341 = 1. Such an n is a pseudoprime to base 2, and 2 is a Fermat liar for it (Demo: 341 fools Fermat, not Miller–Rabin). Another base usually exposes it: 3³⁴⁰ mod 341 = 56.
Carmichael numbers fool every base
A Carmichael number passes the Fermat test for every base that shares no factor with it. The smallest is 561 = 3·11·17: all 318 coprime bases between 2 and 559 are liars (Demo: scan every base of 561). Only bases that happen to share a factor (3, 6, 9, 11, …) reveal it, and for a big Carmichael number with big factors those are as rare as finding a factor by luck. There are infinitely many Carmichael numbers, so the Fermat test alone is not enough.
Miller–Rabin: look at the whole chain
Write n − 1 = 2s·d with d odd. For 561, 560 = 2⁴·35. Instead of jumping straight to an − 1, compute x0 = ad and square it s times. The last box is an − 1, the number the Fermat test looks at:
a^d → a^(2d) → a^(4d) → … → a^(2^s·d) = a^(n − 1) (each arrow: square mod n)
n passes base a as a strong probable prime when ad ≡ 1, or when n − 1 (that is, −1) appears in some box before the last. For 97 and base 5 the chain is 28, 8, 64, 22, 96: −1 shows up, so the next square is 1 and 97 passes (Demo: Miller–Rabin on a prime, 97 (a = 5)).
Why: square roots of 1
Mod a prime p, the only numbers whose square is 1 are 1 and −1: x² ≡ 1 means p divides (x − 1)(x + 1), so it divides one of them. The chain of a prime therefore ends in 1, and the box before the first 1 must hold −1. If the first 1 comes from anything else, that value is a third square root of 1, and n cannot be prime.
For 561 and base 2 the chain is 263, 166, 67, 1, 1. 67² = 4489 = 8·561 + 1, and 67 is neither 1 nor 560. So 561 is composite, even though the last box is 1 and Fermat passed. The square root even gives a factor: gcd(67 − 1, 561) = 33 = 3·11 (Demo: Miller–Rabin unmasks Carmichael 561). The same happens for 341: 32² ≡ 1 and gcd(31, 341) = 31. The gcd comes from Euclid's algorithm.
How many bases?
A composite that passes base a anyway is a strong pseudoprime, and a a strong liar. 2047 = 23·89 is the smallest one for base 2: 2¹⁰²³ mod 2047 = 1. Base 3 catches it at once (Demo: strong liar, 2047 passes base 2). The Monier–Rabin theorem says that for any odd composite n, at most a quarter of the bases are strong liars, so k independent random bases miss with probability at most 4−k. Real numbers do much better than the bound:
| n | factors | Fermat liars (bases 2 … n − 2) | strong liars |
|---|---|---|---|
| 91 | 7·13 | 34 of 88 | 16 of 88 |
| 341 | 11·31 | 98 of 338 | 48 of 338 |
| 561 | 3·11·17 | 318 of 558 | 8 of 558 |
| 2047 | 23·89 | 482 of 2044 | 240 of 2044 |
How libraries use it
To make an RSA prime, OpenSSL and similar libraries draw a random odd number of the right size, throw it out if a small prime divides it (a quick sieve-like filter), then run Miller–Rabin with a few dozen random bases; FIPS 186-5 lists the number of rounds per key size. For numbers below a fixed limit a fixed set of bases is enough: bases 2, 3, 5, 7 decide every n below 3 215 031 751, and the first 12 primes decide every 64-bit n. Finding a prime is easy; splitting a product of two of them back into its prime factors is what RSA relies on being hard.
What the page leaves out
The page uses small n so every number fits in a box, and a fixed menu of bases instead of random ones. It does not prove the 1/4 bound, and does not cover the Solovay–Strassen test (Euler's criterion with the Jacobi symbol), the Baillie–PSW test (Miller–Rabin base 2 plus a Lucas test, with no known counterexample), or AKS, which proves primality in polynomial time but is too slow in practice. Real code also uses Montgomery multiplication and constant-time arithmetic for the powers.