Agrawal's conjecture

In number theory, Agrawal's conjecture, due to Manindra Agrawal in 2002, forms the basis for the cyclotomic AKS test. Agrawal's conjecture states formally:

Let ${\displaystyle n}$and ${\displaystyle r}$be two coprime positive integers. If

${\displaystyle (X-1)^{n}\equiv X^{n}-1{\pmod {n,\,X^{r}-1}}\,}$

then either ${\displaystyle n}$is prime or ${\displaystyle n^{2}\equiv 1{\pmod {r}}}$

If Agrawal's conjecture were true, it would decrease the runtime complexity of the AKS primality test from ${\displaystyle {\tilde {O}}{\mathord {\left(\log ^{6}n\right)}}}$to ${\displaystyle {\tilde {O}}{\mathord {\left(\log ^{3}n\right)}}}$.

The conjecture was formulated by Rajat Bhattacharjee and Prashant Pandey in their 2001 thesis. It has been computationally verified for ${\displaystyle r<100}$and ${\displaystyle n<10^{10}}$, and for ${\displaystyle r=5,n<10^{11}}$.

However, a heuristic argument by Carl Pomerance and Hendrik W. Lenstra suggests there are infinitely many counterexamples. In particular, the heuristic shows that such counterexamples have asymptotic density greater than ${\displaystyle {\tfrac {1}{n^{\varepsilon }}}}$for any ${\displaystyle \varepsilon >0}$.

Assuming Agrawal's conjecture is false by the above argument, Roman B. Popovych conjectures a modified version may still be true:

Let ${\displaystyle n}$and ${\displaystyle r}$be two coprime positive integers. If

${\displaystyle (X-1)^{n}\equiv X^{n}-1{\pmod {n,\,X^{r}-1}}}$

and

${\displaystyle (X+2)^{n}\equiv X^{n}+2{\pmod {n,\,X^{r}-1}}}$

then either ${\displaystyle n}$is prime or ${\displaystyle n^{2}\equiv 1{\pmod {r}}}$.

Both Agrawal's conjecture and Popovych's conjecture were tested by distributed computing project Primaboinca which ran from 2010 to 2020, based on BOINC. The project found no counterexample, searching in ${\displaystyle 10^{10}<n<10^{17}}$.

• Primaboinca project