Skip to content

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

Peter W. Shor

SIAM Journal on Computing · 1997 · 9,399 citationsOpen access

No retraction on record in OpenAlex.Check Crossref now

Cite this paper

Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484–1509. https://doi.org/10.1137/s0097539795293172

In text: (Shor, 1997)

Ask a question about this research

One question, free, no account. Anchorcite finds the papers, checks each against Crossref and links every sentence of the answer to the passage it comes from.

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 by 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 which 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.

  1. A method for obtaining digital signatures and public-key cryptosystems1978
  2. A method for obtaining digital signatures and public-key cryptosystems1983
  3. Elliptic Curve Cryptosystems1987

Metadata from OpenAlex (CC0). Citations are generated from the published record.