In number theory, Agrawal's conjecture, due to Manindra Agrawal in 2002,[1] forms the basis for the cyclotomic AKS test. Agrawal's conjecture states formally:
Let
n
r
(X-1)n\equivXn-1\pmod{n,Xr-1}
then either
n
n2\equiv1\pmodr
If Agrawal's conjecture were true, it would decrease the runtime complexity of the AKS primality test from
\tildeOd\left(log6n\right)
\tildeOd\left(log3n\right)
The conjecture was formulated by Rajat Bhattacharjee and Prashant Pandey in their 2001 thesis.[2] It has been computationally verified for
r<100
n<1010
r=5,n<1011
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
\tfrac{1}{n\varepsilon
\varepsilon>0
Assuming Agrawal's conjecture is false by the above argument, Roman B. Popovych conjectures a modified version may still be true:
Let
n
r
(X-1)n\equivXn-1\pmod{n,Xr-1}
and
(X+2)n\equivXn+2\pmod{n,Xr-1}
then either
n
n2\equiv1\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
1010<n<1017