The 2006 Gödel Prize for outstanding papers in the area of theoretical computer science is awarded to Manindra Agrawal, Neeraj Kayal, and Nitin Saxena for their paper:
PRIMES is in P. Annals of Mathematics 160(2), 781-793, 2004.
In August 2002 one of the most ancient computational problems was finally solved. Agrawal, Kayal, and Saxena presented an unconditional deterministic polynomial time algorithm that determines whether an input number is prime or composite. Due to the Internet, the preprint of their paper circulated within hours in the scientific community and found an immediate enthusiastic response. All previously known polynomial time primality tests were based on probabilistic methods or they relied on an unproven assumption, known as the generalized Riemann Hypothesis.
The result obtained by Agrawal, Kayal, and Saxena can be seen as a crowning achievement of a long algorithmic and mathematical quest.
A remarkable aspect of the article is that the final exposition itself turns out to be rather simple. The text as published in Annals of Mathematics is a masterpiece in mathematical reasoning. It has a high density of tricks and techniques, but the arguments come in a brilliantly simple manner; they remain completely elementary. The contents of the paper are therefore accessible to a broad audience.
The performance of the algorithm depends on some number-theoretic assumptions, but an exact unconditional polynomial bound is given in the paper. However, if the number-theoretic assumptions hold, then the algorithm runs in nearly cubic time, which is amazing. The award-winning paper makes use of a new probabilistic algorithm by Agrawal and Somenath Biswas, presented at FOCS 1999, which Agrawal, Kayal, and Saxena were able to derandomize. Thus "PRIMES is in P" is a perfect example for a new trend in derandomization.
We cannot yet foresee the full impact of the paper, but since its appearance many researchers have been inspired by the algebraic techniques in the paper and have continued to work on them. For example, follow-up papers have established new connections between graph-isomorphism, integer-factorization, and ring-isomorphism. Primality testing and integer-factorization remain in the focus of current research: The intractability of finding the prime factors of very large numbers has been a cornerstone of cryptography and data security.