Feb 13, 2010

AKS primality test - Wikipedia, the free encyclopedia


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

  1. ^ a b c Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
  2. ^ a b H. W. Lenstra, Jr. and Carl Pomerance, "Primality Testing with Gaussian Periods", preliminary version July 20, 2005.

[edit] External links

No comments: