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
2003), or
for certain integers or with an infinitesimal chance that the algorithm might return
an ambiguous result (Crandall and Papadopoulos 2003).
, but has since been
considerably reduced to 
for general integers (Lenstra and Pomerance
2003), or 
for certain integers or with an infinitesimal chance that the algorithm might return
an ambiguous result (Crandall and Papadopoulos 2003).
Germundsson, R.; Lichtblau, D.; and Terr, D.
"The Agarwal-Kayal-Saxena Primality Test." 