 Miller-Rabin primality test

For an odd candidate $n>3$, write $n-1=2^{s}d$ with $d$ odd. A base $a$ passes when $a^d\equiv 1(\mathrm{mod}n)$ or $a^{2^{j}d}\equiv -1(\mathrm{mod}n)$ for some $0\le j<s$; a nontrivial common divisor of $a,n$ or failure of these conditions proves compositeness. A prime passes every base, while an odd composite passes at most one quarter of possible bases. Independent rounds give a false probable-prime probability at most $4^{-r}$. A passing composite is a strong pseudoprime, stronger than a Fermat pseudoprime.