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.
Read more about this topic: AKS Primality Test
Famous quotes containing the words history and, history, running and/or time:
“History and experience tell us that moral progress comes not in comfortable and complacent times, but out of trial and confusion.”
—Gerald R. Ford (b. 1913)
“It’s not the sentiments of men which make history but their actions.”
—Norman Mailer (b. 1923)
“Sense is a line, the mind is a circle. Sense is like a line which is the flux of a point running out from itself, but intellect like a circle that keeps within itself.”
—Ralph J. Cudworth (1617–1688)
“A genius can never expect to have a good time anywhere, if he is a genuine article, but America is about the last place in which life will be endurable at all for an inspired writer of any kind.”
—Samuel Butler (1835–1902)