= Agrawal–Biswas primality test
{c}
The <Agrawal–Biswas primality test> tests a formal <polynomial identity> in $(\mathbb Z/n\mathbb Z)[X]$:
$$
P_n(X)=(1+X)^n-1-X^n=0.
$$
For $n\geq2$, 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_2n\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$.<Primality and Identity Testing via Chinese Remaindering by Manindra Agrawal and Somenath Biswas>[section 3, Lemma 3.1, Prime(n) and Theorem 3.2]{ref}
Back to article page
