AKS primality test

The AKS primality test (also known as Agrawal-Kayal-Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm discovered and published by three Indian scientists named Manindra Agrawal, Neeraj Kayal and Nitin Saxena in August 6, 2002 in a scientific paper titled Primes in P.

The algorithm, which was improved by others later, determines whether a number is prime or composite and runs in polynomial time.

AKS has a key difference with all previous general primality-proving algorithms: It does not require any unproven hypothesis (such as Riemann hypothesis) to be true in order to have provable polynomial time on all inputs.

The asymptotic time complexity of the original algorithm is Õ(log¹²n) (log is base 2).

In the following months after the discovery new variants appeared (Lenstra 2002, Pomerance 2002, Berrizbeitia 2003, Cheng 2003, Bernstein 2003a/b, Lenstra and Pomerance 2003) which improved AKS' speed by orders of magnitude. Because of the many variants, Crandall and Papadopoulos refer to the "AKS-class" of algorithms in their scientific paper On the implementation of AKS-class primality tests published in March 2003.

See also

• Prime numbers
• Mathematics

External links

• Information from MathWorld.wolfram.com
• Primes in P: The original scientific paper describing AKS primality test (PDF)
• R. Crandall, Apple ACG, and J. Papadopoulos (March 18, 2003): On the implementation of AKS-class primality tests (PDF)
• Article by Borneman, containing photos and information about the three Indian scientists (PDF)