AKS Primality Test - History and Running Time

History and Running Time

In the first version of the above-cited paper, the authors proved the asymptotic time complexity of the algorithm to be Õ. In other words, the algorithm takes less time than the twelfth power of the number of digits in n times a polylogarithmic (in the number of digits) factor. However, the upper bound proved in the paper was rather loose; indeed, a widely held conjecture about the distribution of the Sophie Germain primes would, if true, immediately cut the worst case down to Õ.

In the months following the discovery, new variants appeared (Lenstra 2002, Pomerance 2002, Berrizbeitia 2003, Cheng 2003, Bernstein 2003a/b, Lenstra and Pomerance 2003), which improved the speed of computation by orders of magnitude. Due to the existence 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.

In response to some of these variants, and to other feedback, the paper "PRIMES is in P" was updated with a new formulation of the AKS algorithm and of its proof of correctness. (This version was eventually published in Annals of Mathematics.) While the basic idea remained the same, r was chosen in a new manner, and the proof of correctness was more coherently organized. While the previous proof had relied on many different methods, the new version relied almost exclusively on the behavior of cyclotomic polynomials over finite fields. The new version also allowed for an improved bound on the time complexity, which can now be shown by simple methods to be Õ. Using additional results from sieve theory, this can be further reduced to Õ.

In 2005, Carl Pomerance and H. W. Lenstra, Jr. demonstrated a variant of AKS that runs in Õ(log6(n)) operations, where n is the number to be tested – a marked improvement over the initial Õ(log12(n)) bound in the original algorithm. An updated version of the paper is also available.

Agrawal, Kayal and Saxena suggest a variant of their algorithm which would run in Õ if a certain conjecture made by Bhattacharjee and Pandey in 2001 is true (Agrawal's conjecture); however, a heuristic argument by Hendrik Lenstra and Carl Pomerance suggests that it is probably false.