Agrawal–Biswas primality test

The Agrawal–Biswas primality test tests a formal polynomial identity in $(\mathbb{Z}/n\mathbb{Z})[X]$:For $n\ge 2$, the identity holds exactly when $n$ is a prime number. Testing a formal polynomial is stronger than evaluating it at residues.

The randomized algorithm first handles prime numbers at most thirteen, divisibility by them, and perfect powers. For remaining $n$, choose a monic polynomial $Q$ of polynomial degree $\ell =\lceil {\log }_{2}n\rceil$, with independent uniform lower coefficients modulo $n$. Compute the remainder of $P_n$ modulo $Q$ using exponentiation by squaring. A nonzero remainder proves compositeness. The monic polynomial permits division even when the coefficient ring has zero divisors.

Every prime number passes. After preprocessing, a composite number is rejected with probability at least $2/3$ per trial, so $r$ independent trials give error at most $3^{-r}$. Keeping remainders below polynomial degree $\ell$ makes the computation polynomial time in the bit length of $n$.^[ref]