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