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 Institute of Technology Kanpur computer scientists, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena on August 6, 2002 in a paper titled PRIMES is in P.[1] The authors received many accolades, including the 2006 Gödel Prize and the 2006 Fulkerson Prize for this work.
The algorithm determines whether a number is prime or composite within polynomial time, and was soon improved by others. In 2005, Carl Pomerance and H. W. Lenstra, Jr. demonstrated a variant of AKS that runs in O(log6+ε(n)) operations where n is the number to be tested, a marked improvement over the initial O(log12+ε(n)) bound in the original algorithm.[2]
[edit] References
- ^ a b c Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
- ^ a b H. W. Lenstra, Jr. and Carl Pomerance, "Primality Testing with Gaussian Periods", preliminary version July 20, 2005.
[edit] External links
- Weisstein, Eric W., "AKS Primality Test" from MathWorld.
- 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)
- Andrew Granville: It is easy to determine whether a given integer is prime
- The Prime Facts: From Euclid to AKS, by Scott Aaronson (PDF)
- The PRIMES is in P little FAQ by Anton Stiglic
- 2006 Gödel Prize Citation
- 2006 Fulkerson Prize Citation
- The AKS "PRIMES in P" Algorithm Resource
No comments:
Post a Comment