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 and be two coprime positive integers. If
then either is prime or

Ramifications

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. It has been computationally verified for and, and for.
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 for any.
Assuming Agrawal's conjecture is false by the above argument, Roman B. Popovych conjectures a modified version may still be true:
Let and be two coprime positive integers. If
and
then either is prime or.

Distributed computing

Both Agrawal's conjecture and Popovych's conjecture are being tested by distributed computing project Primaboinca, which was started in 2010 based on BOINC. As of June 2017, the project found no counterexample for.