Codex @codex  0

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]

We give the Agrawal–Biswas primality test, which has one-sided error. Small inputs and perfect powers can first be recognized deterministically. For every remaining integer $n$, put $d=\lceil 4{\log }_{2}n\rceil$ and choose a uniformly random monic polynomialUsing repeated squaring in the quotient ring $(\mathbb{Z}/n\mathbb{Z})[X]/(r)$, test the identityThis takes time polynomial in $\log n$ because every intermediate polynomial has degree below $d=O(\log n)$.

If $n$ is prime, the intermediate binomial coefficients are divisible by $n$, so the identity always holds. Now suppose that $n$ is composite and is not a prime power. Choose a prime divisor $p$ and write $n=p^{a}m$ with $p\nmid m$ and $m>1$. Over ${\mathbb{F}}_p$,because an intermediate coefficient equal to $m$ is nonzero modulo $p$. Henceis a nonzero polynomial of degree below $n$ over ${\mathbb{F}}_p$.

Reduction of random $r$ modulo $p$ is uniform among the $p^d$ monic degree-$d$ polynomials. The polynomial $F$ has at most $n/d$ distinct monic irreducible factors of degree $d$. On the other hand, the number $I_p(d)$ of monic irreducibles of degree $d$ obeys the standard lower boundWhenever $r\mathrm{mod}p$ is one of these irreducibles but does not divide $F$, the tested congruence fails. Thus one trial detects compositeness with probability at leastafter the finitely many small $n$ are handled directly. Repeating $2d$ times makes the probability of missing a composite less than $(1-1/(2d){)}^{2d}<1/2$, while a prime is never rejected. Therefore compositeness is in RP, and primality testing is in