Thanks to Lance, Agarwal, Kayal and Saxena, the authors of the famous paper "Primes is in P", won the Goedel Prize for 2006. Goedel Prize is the highest award in Theoretical Computer Science. Here is a list of past winners of the award. Note the names like Hastad, Arora, Sudan, Motwani, Goldwasser, Freund-Schapire, among other modern greats.
According to Suresh's blog, people knew this news earlier, via grapevine.
Here is an introduction to the problem and the algorithm (PDF link). The Wiki Entry, a version of the paper (PDF link) from Agarwal's home page. The paper has been accepted to be published in Annals of Mathematics 160 1-13, 2004.