Primality testing

Primality testing is the decision problem of determining whether an input integer is a prime number.

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.

The Fermat test looks for a coprime base $a$ with $a^{N-1}\not\equiv 1(\mathrm{mod}N)$. Such a witness proves compositeness by the Fermat little theorem, but Carmichael numbers pass for every coprime base.

A base $b$ coprime to the tested odd composite $N$ for which a specified probable-prime criterion passes. The sets of passing bases depend on the criterion and need not be subgroups.

The Agrawal–Biswas primality test checks the identity $(X+1{)}^n=X^n+1$ modulo $n$ and a random low-degree monic polynomial. Prime inputs always pass, while a composite input that is not a prime power fails with inverse-polynomial probability per trial.