Exercise 2203Number theory › PrimesM1Added 3 Nov 2026

The Miller–Rabin test

#Miller-Rabin#primality#probabilistic

Statement

Describe the Miller–Rabin test and apply it to $n=13$ with base $a=2$ .

Hint

Write $n-1=2^s\cdot d$ with $d$ odd. Compute $a^d\bmod n$ , then square up to $s$ times.

Show solutionHide solution

Setup. $n=13$ , $n-1=12=2^2\cdot3$ , so $s=2$ , $d=3$ .

Compute. $a^d=2^3=8\pmod{13}$ . Square: $8^2=64\equiv12\equiv-1\pmod{13}$ . Witness for primality: we hit $-1$ before squaring $s=2$ times.

Conclusion. $13$ passes Miller–Rabin for base $2$ .

Application. The test is used in RSA key generation; with $k$ bases, error probability $\le4^{-k}$ for composite inputs.