Is this number prime? From Fermat's test to Miller-Rabin Image: Carlo Nardone, Computer History Museum (CC BY-SA 2.0)

Is this number prime? From Fermat's test to Miller-Rabin

To generate an RSA key, a program must find two primes of about 300 digits each. It does so by picking random odd numbers of that size and testing them, and the prime number theorem says that about one in 350 of them will be prime. So the test must be fast. Trial division by every prime up to the square root would need about 10^147 divisions, which is not a number of operations any machine will ever perform. The tests actually used take a few thousand multiplications and are built on a theorem Fermat stated in 1640.

Fermat's test

Fermat's little theorem says that if p is prime and a is not a multiple of p, then a^(p-1) ≡ 1 (mod p). Turn it around: to test whether n is prime, pick a base a, compute a^(n-1) mod n by repeated squaring, and look. If the answer is not 1, then n is certainly composite, because a prime would have given 1. If the answer is 1, n may be prime.

The computation is cheap. Repeated squaring needs about 2 log₂ n multiplications modulo n, which for a 300-digit number is about 2,000 multiplications of 300-digit numbers, done in a millisecond. The weakness is the "may be". A composite n with a^(n-1) ≡ 1 (mod n) is called a pseudoprime to the base a, and the smallest one to the base 2 is 341 = 11 × 31: since 2^10 = 1024 = 3 × 341 + 1, we have 2^10 ≡ 1 and so 2^340 ≡ 1 (mod 341). Changing the base helps: 3^340 ≡ 56 (mod 341), which exposes it. One might hope that a few bases always suffice.

Carmichael numbers

They do not. There are composite numbers that pass Fermat's test for every base coprime to them. The smallest is 561 = 3 × 11 × 17, found by Robert Carmichael in 1910, and the reason it passes is Korselt's criterion of 1899: a composite n is a Carmichael number exactly when it is squarefree and p - 1 divides n - 1 for every prime p dividing n. For 561, the number n - 1 = 560 is divisible by 2, by 10, and by 16, and so a^560 ≡ 1 modulo 3, 11, and 17 separately by Fermat's theorem, hence modulo 561 by the Chinese remainder theorem. The next ones are 1105, 1729 (Hardy's taxi number again), 2465, 2821, and 6601. They are rare, with 43 below a million and 646 below a billion, but Alford, Granville, and Pomerance proved in 1994 that there are infinitely many, so Fermat's test alone can never be made safe by adding bases.

The repair

Gary Miller in 1976 and Michael Rabin in 1980 fixed the test with one more fact about primes: modulo a prime p, the only square roots of 1 are 1 and -1. The lemma follows from Euclid's lemma, since x² - 1 = (x - 1)(x + 1), and a prime dividing the product divides a factor. Modulo a composite there can be more; modulo 561 the number 67 satisfies 67² ≡ 1, as do 188, 254, and others.

The Miller-Rabin test uses this as follows. Write n - 1 = 2^s × d with d odd. Compute a^d mod n, then square it repeatedly, s times, to reach a^(n-1). If n is prime, the final value is 1, and the sequence of squarings reaches 1 for the first time either at the start (a^d ≡ 1) or from the value -1, since the only way to square to 1 modulo a prime is from 1 or -1. So n passes the test for base a if a^d ≡ 1 or one of the values a^d, a^(2d), ..., a^(2^(s-1) d) is ≡ -1 (mod n). Otherwise n is composite, with certainty.

For 561 we have 560 = 2^4 × 35, and the sequence for a = 2 is 2^35 ≡ 263, 263² ≡ 166, 166² ≡ 67, 67² ≡ 1 (mod 561). The chain reaches 1 from 67, which is neither 1 nor -1, so 561 is composite, and the test found it with the first base. Rabin proved that for a composite n, at most a quarter of the bases a between 1 and n - 1 fool the test, so with k random bases the chance that a composite number passes is at most 4^(-k). With k = 40 the chance is below 10^(-24), far below the chance of a hardware fault during the computation. Every major library uses this test, usually with a short trial division by small primes first.

A composite number that passes for a given base is called a strong pseudoprime to that base. The smallest strong pseudoprime to the bases 2, 3, 5, and 7 together is 3,215,031,751 = 151 × 751 × 28351, and the bases 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37 together have no strong pseudoprime below 3.1 × 10^23, so for numbers of that size the twelve fixed bases make the test deterministic.

Proof against probability

A Miller-Rabin "probably prime" is not a proof. For most purposes nobody cares; the error is below any physical probability. But for a record prime, or for a theorem that depends on a number being prime, one wants a certificate, and there are methods that provide one. The Lucas-Lehmer test for Mersenne numbers is one, and it is how the 41-million-digit record of 2024 was certified after a probable-prime test had flagged it. The elliptic curve primality test of Atkin and Morain handles general numbers of a few thousand digits and produces a certificate that can be checked independently.

Whether primality could be decided in polynomial time, without randomness and without luck, was open until 2002. In that year Manindra Agrawal and his undergraduate students Neeraj Kayal and Nitin Saxena at IIT Kanpur gave an algorithm that does it. The AKS test rests on a polynomial version of Fermat's theorem: n is prime exactly when (x + a)^n ≡ x^n + a as polynomials modulo n, and they showed that checking this congruence modulo a small auxiliary polynomial, for a few values of a, is enough. The paper, PRIMES is in P, appeared in the Annals of Mathematics in 2004 and is nine pages long. The algorithm is slower in practice than Miller-Rabin and is not used for real keys; its importance is that the question is closed. The research spotlight of Unit 3 of the masterclass is this paper.

Testing is not factoring

The thing to carry away is that deciding whether a number is prime and finding its factors are different problems with very different costs. Miller-Rabin can tell you in a millisecond that a 600-digit number is composite without giving the slightest hint of its factors. Factoring that number is what would break RSA, and the best known method, the number field sieve, took about 2,700 core-years for 250 digits. The whole of public-key cryptography lives in the gap between the two problems, and the gap is a theorem about Fermat's little theorem on one side and a conjecture about factoring on the other.

Unit 5 of the masterclass proves Fermat's and Euler's theorems, works through 341 and 561, derives the Miller-Rabin test from the square-root lemma, and builds RSA on the same foundations; the Lucas-Lehmer test appears in Unit 6 with the perfect numbers.

Study the integers properly

The NT Masterclass: weekly units, quizzes, a final exam, and a certificate.
About the program