Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 3 / 11G / Solution

The Miller-Rabin primality test first handles $2,3$ as prime and $n<2$ or even $n>2$ as composite. For odd $n>3$, write $n-1=2^{s}d$ with $d$ odd and choose a base $2\le a\le n-2$. A nontrivial $\gcd (a,n)$ proves compositeness. Otherwise compute $x=a^d\mathrm{mod}n$: the round passes if $x=1$ or $x=-1$. If neither holds, square successively, at most $s-1$ times, and pass if a value $-1$ occurs; otherwise declare composite. An occurrence of $1$ before $-1$ exhibits a nontrivial square root of one and is also a failure. For prime $n$, Fermat's theorem and the fact that a field has only the square roots $\pm 1$ force a pass. The standard strong-liar bound says that an odd composite passes for at most one quarter of the bases; independent random rounds therefore have error probability at most $4^{-r}$ after $r$ rounds. Passing is a probable-prime verdict, not a proof of primality. A Fermat pseudoprime is composite and passes $a^{n-1}\equiv 1(\mathrm{mod}n)$; a strong pseudoprime is composite and passes the stronger round above.