= 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\bmod 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 $\pm1$ 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}\equiv1\pmod n$; a <strong pseudoprime> is composite and passes the stronger round above.
Back to article page
