Editing AKS primality test (section)

==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 <math>\tilde{O}(\log(n)^{12})</math> (using [[Big O notation#Extensions to the Bachmann–Landau notations|Õ]] from [[big O notation]])—the twelfth power of the number of digits in ''n'' times a factor that is polylogarithmic in the number of digits. However, this upper bound was rather loose; a widely-held conjecture about the distribution of the [[Sophie Germain prime]]s would, if true, immediately cut the worst case down to <math>\tilde{O}(\log(n)^6)</math>.

In the months following the discovery, new variants appeared (Lenstra 2002, Pomerance 2002, Berrizbeitia 2002, Cheng 2003, Bernstein 2003a/b, Lenstra and Pomerance 2003), which improved the speed of computation greatly. Owing 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. The new proof relied almost exclusively on the behavior of [[cyclotomic polynomial]]s over [[finite fields]]. The new upper bound on time complexity was <math>\tilde{O}(\log(n)^{10.5})</math>, later reduced using additional results from [[sieve theory]] to <math>\tilde{O}(\log(n)^{7.5})</math>.

In 2005, [[Carl Pomerance|Pomerance]] and [[Hendrik Lenstra|Lenstra]] demonstrated a variant of AKS that runs in <math>\tilde{O}(\log(n)^{6})</math> operations,<ref name="lenstra_pomerance_2005">H. W. Lenstra Jr. and Carl Pomerance, "[http://www.math.dartmouth.edu/~carlp/PDF/complexity12.pdf Primality testing with Gaussian periods]", preliminary version July 20, 2005.</ref> leading to another updated version of the paper.<ref name="lenstra_pomerance_2011">H. W. Lenstra Jr. and Carl Pomerance, "[http://www.math.dartmouth.edu/~carlp/aks041411.pdf Primality testing with Gaussian periods] {{Webarchive|url=https://web.archive.org/web/20120225052810/http://www.math.dartmouth.edu/~carlp/aks041411.pdf |date=2012-02-25 }}", version of April 12, 2011.</ref> Agrawal, Kayal and Saxena proposed a variant which would run in <math>\tilde{O}(\log(n)^{3})</math> if [[Agrawal's conjecture]] were true; however, a heuristic argument by Pomerance and Lenstra suggested that it is probably false.