AUTOMOTIVE

In the Internet age, the intractability of decomposing large numbers into their prime factors has been the cornerstone of cryptography and data security. Efficient methods to find large primes are needed to create cryptographic keys, which are large numbers that are difficult to factor. Until the AKS algorithm, there was no known method to solve the problem of testing the primality of a given number both in a timely and efficient way, and without the use of random coin flips. All previously known polynomial time primality tests were based on probabilistic methods or they relied on an unproven assumption. Due to the Internet, the preprint of the award-winning paper that introduced this advance in 2002 circulated within hours in the scientific community, and found an immediate enthusiastic response. Of limited practical application in its original form, this discovery marked an important breakthrough in understanding number theory. Although the full impact of the discovery is not yet known, its appearance has inspired many researchers to work on the algebraic techniques presented. Manindra Agrawal is professor of computer science, with a Ph.D. degree in Computer science and Engineering from the Indian Institute of Technology in Kanpur. He collaborated with Nitin Saxena and Neeraj Kayal, also from the Indian Institute. Their results are seen as a crowning achievement of a long algorithmic mathematical quest. The Gödel Prize for outstanding papers in theoretical computer science is named in honor of Kurt Gödel , who was born in Austria-Hungary (now the Czech Republic) in 1906. Gödel's work has had immense impact upon scientific and philosophical thinking in the 20 th century. The award recognizes his major contributions to mathematical logic and the foundations of computer science.