Agrawal's conjecture

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.[2] It has been computationally verified for ${\displaystyle r<100}$ and ${\displaystyle n<10^{10}}$,[3] and for ${\displaystyle r=5,n<10^{11}}$.[4]

However, a heuristic argument by Carl Pomerance and Hendrik W. Lenstra suggests there are infinitely many counterexamples.[5] 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}}}$.[6]

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