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].
Contents |
|
