AKS prime number test

The AKS prime number test (also known as the Agrawal-Kayal-Saxena prime number test ) is a deterministic algorithm that determines whether a natural number is prime or not in polynomial running time . It was developed by the three Indian scientists Manindra Agrawal , Neeraj Kayal and Nitin Saxena and published in 2002 in a paper entitled PRIMES is in P (German: the prime number problem belongs to complexity class P ). In 2006, the researchers were awarded the Gödel and Fulkerson Prize for their work .

The algorithm, which was later improved by others, differs significantly from all previously known polynomial primality proof algorithms: It does not build on any unproven hypotheses (such as the generalized Riemann hypothesis ) for the proof of the polynomial running time - based on the length of the input values . The asymptotic running time of the original algorithm is , where the number to be tested is, stands for the Landau symbol and for any small positive number. ${\displaystyle {\mathcal {O}}\left((\log n)^{7,5+\varepsilon }\right)}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle \varepsilon }$

History of origin

In 1999 Manindra Agrawal worked with his doctoral supervisor Somenath Biswas on a probabilistic method to show the equality of polynomials. The two then worked out a method for a probabilistic prime number test. The idea behind it and which later turned out to be useful is the following proposition :

Be and . Then is prime if and only if . ${\displaystyle a\in \mathbb {Z} ,n\in \mathbb {N} ,n>1}$ ${\displaystyle \mathrm {ggT} (a,n)=1}$ ${\displaystyle n}$ ${\displaystyle (x+a)^{n}\equiv x^{n}+a{\pmod {n}}}$

There is no concrete number, but a free variable. The coefficients of the powers of are to be compared: is not a prime number if and only if its smallest divisor satisfies; but then is not a whole number and it applies ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle 1<k<n}$ ${\displaystyle \textstyle {{n-1 \choose k-1}/k}}$

${\displaystyle \textstyle {{n \choose k}=n\cdot {n-1 \choose k-1}/k\neq 0{\pmod {n}}}}$.

For the resulting primality test, it was considered that it could not keep up with the current ones. In the worst case, you had to calculate all the coefficients, which could be quite time consuming. Therefore, the idea was initially not pursued further.

In 2001 the students Rajat Bhattarcharjee and Prashant Pandey took up the idea again in their Bachelor thesis Primality Testing . They expanded the idea of ​​computing the polynomials not only modulo , but also modulo for an in the order of magnitude of . This has the advantage that you can calculate in polynomial time. Now it is true for a prime number that it satisfies this congruence, but they now also satisfy numbers that are not prime numbers. ${\displaystyle n}$ ${\displaystyle x^{r}-1}$ ${\displaystyle r}$ ${\displaystyle \log n}$ ${\displaystyle (x+a)^{n}{\bmod {(}}x^{r}-1,n)}$ ${\displaystyle n}$

The two investigated this congruence for certain and in order to set conditions on and on so that this congruence only applies to prime numbers. After a series of tests, they made the following assumption: ${\displaystyle a}$ ${\displaystyle r}$ ${\displaystyle a}$ ${\displaystyle r}$

If and is not a factor , then either is prime or . ${\displaystyle r\in \mathbb {P} }$ ${\displaystyle n}$ ${\displaystyle (x+1)^{n}\equiv x^{n}+1{\pmod {\left(x^{r}-1,n\right)}}}$ ${\displaystyle n}$ ${\displaystyle n^{2}\equiv 1{\pmod {r}}}$

In 2002 the two students Neeraj Kayal and Nitin Saxena worked on their bachelor thesis. They carried on the considerations of their pioneers. Assuming that the Riemann Hypothesis is correct, they were able to prove the above theorem. With a slight premonition, they then called their bachelor thesis Towards a deterministic polynomial-time primality test.

Then they brought the algorithm into its final form with Manindra Agrawal. The font then published quickly became very popular. The correctness was confirmed within a week and the website had over two million visitors in the first week.

The algorithm

In the following are natural numbers. The input is the number . ${\displaystyle n,a,b,r}$ ${\displaystyle n>1}$

 1. if n=ab für ein a und ein b > 1: 
 2.      return ZUSAMMENGESETZT
 3. finde das kleinste r mit ordr(n) > log(n)2
 4. if 1 < ggT(a,n) < n für ein a ≤ r:
 5.      return ZUSAMMENGESETZT
 6. if n ≤ r:
 7.      return PRIM
 8. for a=1 to sqrt(phi(r))*log(n) do
 9.      if (x+a)n ≠ xn+a (mod (xr−1,n)):
10.          return ZUSAMMENGESETZT
11. return PRIM

Explanations:

• ordr(n)is the order of modulo ; that is the smallest number that applies to. ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle k>0}$ ${\displaystyle n^{k}\equiv 1\,({\text{mod }}r)}$
• phi(r)is Euler's Phi function or totient, which is the number of prime numbers in the range from 1 to . ${\displaystyle r}$ ${\displaystyle r}$
• ${\displaystyle x}$ is the basis of the polynomial ring and not a concrete number.

After Agrawal, Kayal and Saxena

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) that improved the AKS speed by orders of magnitude. Because of the large number of variants speak Crandall and Papadopoulos in her essay On the implementation of AKS-class primality tests (dt .: About the implementation of prime tests of AKS-class ) from March 2003 by the class of AKS algorithms instead of AKS -Algorithm.

The Lenstra and Pomerance algorithm terminates in . In practice, however, the runtime of the AKS algorithm is of a similar order of magnitude, since the parameter can usually be found a little above . ${\displaystyle {\mathcal {O}}\left((\log N)^{6+\varepsilon }\right)}$ ${\displaystyle r}$ ${\displaystyle \log ^{2}n}$

Agrawal, Kayal and Saxena came up with a similar algorithm using the above conjecture:

First you look for one with (such a one is in the interval ). With this algorithm one gets a running time of . Lenstra and Pomerance have given a heuristic to find possible counterexamples for this assumption in Remarks on Agrawal's Conjecture . However, it is not yet known whether there are numbers like those assumed in their assumption. ${\displaystyle r\in \mathbb {P} }$ ${\displaystyle r\nmid (N^{2}-1)}$ ${\displaystyle r}$ ${\displaystyle [2,4\log N]}$ ${\displaystyle {\mathcal {O}}\left((\log n)^{3+\varepsilon }\right)}$

literature

• Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: Discrete algebraic methods: arithmetic, cryptography, automata and groups . De Gruyter, Berlin 2013, ISBN 978-3-11-031260-7 .
• Martin Dietzfelbinger: Primality testing in polynomial time. From randomized algorithms to “PRIMES is in P” (=  Lecture Notes in Computer Science . No. 3000 ). Springer, Berlin 2004, ISBN 3-540-40344-2 .

Web links

• Eric W. Weisstein : AKS Primality Test . In: MathWorld (English).
• M. Agrawal, N. Kayal, N. Saxena: PRIMES is in P. (PDF; 195 kB).
• R. Crandall, J. Papadopoulos: On the implementation of AKS-class primality tests. ( Memento of April 3, 2003 in the Internet Archive ). (PDF; 104 kB). March 18, 2003.
• Folkmar Bornemann: A breakthrough for “everyone”. (PDF; 487 kB). Article about the AKS primality test with photos of the three Indian researchers.
• H. Lenstra, C. Pomerance: Remarks on Agrawal's Conjecture.