Polynomial Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

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