AKS Primality Test

In August 2002, M. Agrawal and colleagues announced a deterministic algorithm for determining if a number is prime that runs in polynomial time (Agrawal et al. 2004). While this had long been believed possible (Wagon 1991), no one had previously been able to produce an explicit polynomial time deterministic algorithm (although probabilistic algorithms were known that seem to run in polynomial time). This test is now known as the Agrawal-Kayal-Saxena primality test, cyclotomic AKS test, or AKS primality test.

Commenting on the impact of this discovery, P. Leyland noted, "One reason for the excitement within the mathematical community is not only does this algorithm settle a long-standing problem, it also does so in a brilliantly simple manner. Everyone is now wondering what else has been similarly overlooked" (quoted by Crandall and Papadopoulos 2003).

The complexity of the original algorithm of Agrawal et al. (2004) was , but has since been considerably reduced to for general integers (Lenstra and Pomerance 2019), or for certain integers or with an infinitesimal chance that the algorithm might return an ambiguous result (Crandall and Papadopoulos 2003).