Jump to content

AKS primality test

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 83.129.65.202 (talk) at 14:29, 29 October 2004 (de). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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 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(log12n).

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