Agrawal's conjecture

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 and be two coprime positive integers. If

then either is prime or


If Agrawal's conjecture were true, it would decrease the runtime complexity of the AKS primality test from to .

Truth or falsehood[edit]

Agrawal's conjecture has been computationally verified for and ; however, a heuristic argument by Carl Pomerance and Hendrik W. Lenstra suggests there are infinitely many counterexamples.[2] 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, Popovych conjectures a modified version may still be true:

Let and be two coprime positive integers. If


then either is prime or .[3]


  1. ^ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES is in P" (PDF). Annals of Mathematics. 160 (2): 781–793. JSTOR 3597229. doi:10.4007/annals.2004.160.781. 
  2. ^ Lenstra, H. W.; Pomerance, Carl. "Remarks on Agrawal’s conjecture." (PDF). American Institute of Mathematics. Retrieved 16 October 2013. 
  3. ^ Popovych, Roman, A note on Agrawal conjecture (PDF)