Discrete Algebraic Methods

4 Polynomial time primality test

In August 2002, a message rapidly spread out, reaching all mathematically interested people throughout the world within hours: “PRIMES is in P.” The scientists Manindra Agrawal, Neeraj Kayal, and Nitin Saxena from India had found a polynomial-time primality test. Composed of the initials of their last names, this method is called the AKS test. It is neither based on unproven hypotheses like, for example, the generalized Riemann hypothesis (Georg Friedrich Bernhard Riemann, 1826–1866), nor does it provide any probabilistic claims like the Miller–Rabin test from Section 3.4.3. The problem called PRIMES, that is, “check whether an integer, given in binary, is prime,” is thus in the complexity class P of problems ...