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 created and published by three Indian scientists named Manindra Agrawal, Neeraj Kayal and Nitin Saxena in August 6, 2002 in a scientific paper titled "PRIMES is 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 the Riemann hypothesis) to be true in order to have provable polynomial time on all inputs.
The asymptotic time complexity of the original algorithm is O(log12+εn), where ε is a small number. In other words, the algorithm takes less time than a constant times the twelfth (plus ε) power of the number of digits in n.
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
External links
- MathWorld: AKS Primality Test (http://mathworld.wolfram.com/AKSPrimalityTest.html)
- PRIMES is in P: The original scientific paper describing AKS primality test (http://www.cse.iitk.ac.in/primality.pdf) (PDF)
- R. Crandall, Apple ACG, and J. Papadopoulos (March 18, 2003): On the implementation of AKS-class primality tests (http://developer.apple.com/hardware/ve/pdf/aks3.pdf) (PDF)
- Article by Borneman, containing photos and information about the three Indian scientists (http://www.ams.org/notices/200305/fea-bornemann.pdf) (PDF)
- Andrew Granville: It is easy to determine whether a given integer is prime (http://www.ams.org/bull/2005-42-01/S0273-0979-04-01037-7/home.html)
- The Prime Facts: From Euclid to AKS, by Scott Aaronson (http://www.scottaaronson.com/writings/prime.pdf) (PDF)de:AKS-Primzahltest