Primality testing

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

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.