The Miller–Rabin test

Setup. Write $n-1=2^s\cdot d$ with $d$ odd. Choose a base $a$ with $1<a<n-1$.

Test. Compute $x=a^d\bmod n$. Then square $s$ times:
- if $x\equiv1$ or $x\equiv n-1$, the base is a witness for primality;
- otherwise, if after squaring $s$ times we reach neither $1$ nor $n-1$, the base is a witness for compositeness.

Correctness. If $n$ is prime, Fermat's little theorem plus the structure of $\mathbb{Z}/n\mathbb{Z}^*$ ensures every coprime base is a witness for primality. If $n$ is composite, at least $3/4$ of bases are witnesses for compositeness (for odd composite $n$).

Conclusion. Miller–Rabin is a probabilistic test with error probability $\le(1/4)^k$ for $k$ bases.