Cryptography Watch

Peter Shor {W} has published a paper which describes a polynomial time factorization algorithm[1].

Shor, Peter W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SICOMP Volume 26 Issue 5 pp. 1484-1509, 1997.*

Abstract:

A digital computer is generally believed to be an efficient universal computing
device; that is, it is believed able to simulate any physical computing device with an
increase in computation time of at most a polynomial factor. This may not be true
when quantum mechanics is taken into consideration. This paper considers factoring
integers and finding discrete logarithms, two problems which are generally thought
to be hard on a classical computer and have been used as the basis of several
proposed cryptosystems. Efficient randomized algorithms are given for these two
problems on a hypothetical quantum computer. These algorithms take a number
of steps polynomial in the input size, e.g., the number of digits of the integer to
be factored.

* Reference updated to reflect revised draft.

This entry was posted on Sunday, November 20th, 1994 at 3:05 pm and is filed under Factoring, Quantum Computing. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.