1999 Gödel Prize (original) (raw)

1999 Gödel Prize

Peter W. Shor

The 1999 Gödel Prize for outstanding journal article in the area of theoretical computer science is awarded to Peter W. Shor for his paper "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer",SIAM Journal on Computing 26 (1997), 1484-1509.

In this breakthrough paper, Shor gives polynomial-time quantum algorithms for integer factoring and for finding discrete logarithms. The implication for quantum computers, hypothetical devices first studied by Benioff and Feynmann, is that, if they could really be built and used, their impact on real-world computation would be revolutionary. The assumption that there are no polynomial-time factoring or discrete-log algorithms for classical computers is needed to prove the security of all of today's widely deployed public-key cryptosystems. These two problems have been extensively studied, and indeed the fastest known algorithms that solve them on classical computers require much more than polynomial time. If quantum computers could be built and used, cryptanalysts could use Shor's algorithms to break all of the public-key cryptosystems in wide use today and all of the electronic-commerce applications that depend on them. Moreover, Shor's quantum algorithms for factoring and discrete logarithms have been profoundly influential outside of the study of public-key cryptography and even outside of computer science.

Created byIan Parberry, May 10, 1999.
Last updated Mon May 10 14:57:14 CDT 1999.