Primality test

How it works

Deciding whether $n$ is prime is much easier than factoring it. Trial division by every prime up to $\sqrt n$ is a proof, but it is only practical up to about $10^{12}$. Fermat’s little theorem gives a fast test: for a prime $n$, $a^{n-1} \equiv 1 \pmod n$. A result other than 1 proves $n$ composite without finding a factor. Unfortunately some composites pass for every base coprime to them, the Carmichael numbers $561, 1105, 1729, \dots$

Miller-Rabin repairs this. Write $n - 1 = 2^s d$ with $d$ odd and look at $a^d, a^{2d}, \dots, a^{2^s d}$. For a prime the only square roots of 1 are $\pm 1$, so the chain starts with 1 or reaches $-1$ before the first 1. For every odd composite, at least three quarters of the bases break this rule, Carmichael numbers included. A base that breaks it is a witness; a square root of 1 other than $\pm 1$ even gives a factor through a gcd.

Exhaustive searches have shown which fixed bases suffice below given bounds: base 2 alone below 2047, the primes up to 41 below $3.3 \cdot 10^{24}$. Above that the answer is “probable prime”, with an error chance that can be made as small as one likes. This is how key generation for RSA finds its primes.