AKS primality test
The AKS primality test (also known as Agrawal - Kayal - Saxena primality test ) is a deterministic algorithm that finds a natural number in polynomial runtime whether it is prime or not. It was developed by three Indian scientists Manindra Agrawal, Neeraj Kayal and Nitin Saxena and 2002 in a paper titled PRIMES is in P ( German sense: The primality problem belongs to the complexity class P) published.
The later of other improved algorithm is substantially different from all previously known polynomial-time primality proof algorithms: He builds for the detection of - in relation to the length of the input values - polynomial running time on any unproved hypotheses ( such as the generalized Riemann hypothesis ) on. The asymptotic duration of the original algorithm ( Landau - symbol ), where n is the number to be tested.
Genesis
1999 Manindra Agrawal worked with his doctor father Somenath Biswas on a probabilistic method to show the equality of polynomials. The two worked out a method from a probabilistic primality test. The idea behind it and which later turned out to be useful is the following lemma:
This is not a concrete number, but a free variable. The coefficients of the powers of are to be compared.
For the primality test thus created was that he could not keep up with the current. At worst, you had to calculate all the coefficients, which could be quite costly. Therefore, the idea was not pursued.
2001, the student Rajat Bhattarcharjee and Prashant Pandey the idea resumed in its Bachelor thesis Primality Testing. They extended the idea to calculate the polynomials modulo not only but also for a modulo r on the order of. This has the advantage that one can compute in polynomial time. Now applies to a prime number that it meets this congruence, but they meet now numbers that are not primes.
The two studied at this congruence for certain and to provide conditions and to ensure that these congruence is valid only for primes. They asked for a series of experiments the following conjecture on:
Is not a divisor of and, then is either prime or.
2002, the two students Neeraj Kayal and Nitin Saxena working on their dissertation. They led the considerations of its forerunner on. Under the assumption that the Riemann hypothesis is correct, they could prove to the sentence above. In a slight premonition they then called their Bachelor thesis: Towards a deterministic polynomial -time Primality Test.
Then they brought the algorithm with Manindra Agrawal in its final form. The then published writing enjoyed great popularity fairly quickly. Thus, the correctness was confirmed within a week and the website had over two million visitors in the first week.
The algorithm
The following are natural numbers. The input is the number.
1 if n is a pure potentiality:
2 return COMPOSED
3 find the smallest r with O_R ( n)> log (n) 2
4 if 1 < gcd ( a, n)
In the following months after the discovery appeared new variants ( Lenstra 2002, Pomerance 2002 Berrizbeitia 2003, Cheng 2003, Bernstein 2003a / b, Lenstra and Pomerance 2003), which improved the AKS- speed by orders of magnitude.
Because of the large number of variants Crandall and Papadopoulos said in his essay On the implementation of AKS -class primality tests ( via the implementation of primality tests of AKS- class) from March 2003 by the class of the AKS algorithm, instead of the AKS algorithm.
The algorithm of Lenstra and Pomerance terminated in.
However, the duration of the AKS algorithm moves in the practice in similar orders of magnitude, since most of the parameters r little above can be found.
Agrawal, Kayal and Saxena have set up with the above conjecture a similar algorithm:
Man seeking first one with ( so r is in the interval).
With this algorithm, we obtain a term of.
Lenstra and Pomerance have given to this supposition in " Remarks on Agrawal 's Conjecture " a heuristic for finding possible counterexamples.
Whether it is adopted as the presumption in their numbers, but it is not yet known.
According to Agrawal, Kayal and Saxena