Agrawal's conjecture

From formulasearchengine
Jump to navigation Jump to 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

Agrawal's conjecture has been computationally verified for and , however a heuristic argument by Carl Pomerance and Hendrik W. Lenstra suggests there is an infinite number of 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, a modified version (the Agrawal–Popovych conjecture[3]) may still be true:

Let and be two coprime positive integers. If


then either is prime or .


  1. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
  2. Template:Cite web
  3. {{#invoke:citation/CS1|citation |CitationClass=citation }}