Miller–Rabin primality test

Summary

The Miller–Rabin test is a probabilistic primality test for an odd integer $n > 2$. Write $n - 1 = 2^s d$ with $d$ odd, and choose a base $a$ with $1 < a < n - 1$. The number $n$ passes for base $a$ if $a^d \equiv 1 \pmod n$, or if $a^{2^r d} \equiv -1 \pmod n$ for some $r$ with $0 \le r < s$. Each odd prime $n$ passes for each base. If $n$ fails for some base, then $n$ is composite.

Remarks

The prime case follows from Fermat's little theorem and the fact that $\pm 1$ are the only square roots of $1$ modulo a prime. If $n$ is an odd composite number, then at most $\frac{1}{4}$ of the bases let it pass. So $k$ random bases give an error probability of at most $4^{-k}$. Gary Miller found the test in 1976, in a deterministic form that depends on the extended Riemann hypothesis. Michael Rabin made it an unconditional probabilistic test in 1980.

Explanations

L1 human

The test checks a property that every prime has, for a few random bases. A composite number fails for most bases, so a few rounds expose it with high probability. The powers are fast to compute by modular exponentiation.