If Agrawal's conjecture were true, it would decrease the runtime complexity of the AKS primality test from to .
Truth or falsehood
The conjecture was formulated by Rajat Bhattacharjee and Prashant Pandey in their 2001 thesis.[2] It has been computationally verified for and ,[3] and for .[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 for any .
Assuming Agrawal's conjecture is false by the above argument, Roman B. Popovych conjectures a modified version may still be true:
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 .
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.