HackerPapers

arXiv:quant-ph/9508027quant-ph

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

Peter W. Shor

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.

arXiv comments
28 pages, LaTeX. This is an expanded version of a paper that appeared in the Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, Nov. 20--22, 1994. Minor revisions made January, 1996
Journal reference
SIAM J.Sci.Statist.Comput. 26 (1997) 1484
DOI
doi:10.1137/S0097539795293172
Subjects
quant-phQuantum Physics

On Hacker News

Linked by 3 identifiable commenters in 3 comments across 3 threads, from Aug 2016 to Jan 2023.

Comments linking this paper, per year.

Discussed in comments3 threads

  1. Breaking RSA with a quantum computer? 1 comment

    • I want to contrast this paper with Shor's factoring paper [1]. One of the things that stands out to me about Shor's paper is how meticulous he is. He is considering the various ways the algorithm might fail, and proving it doesn't fail in that way. For example, the algorithm…

      StrilancView on HNParent context

  2. An Argument Against Quantum Computers 1 comment

    • Shor's original paper discusses the fundamental need for several runs and gives the time complexity. https://arxiv.org/pdf/quant-ph/9508027.pdf The paper you linked to is just saying that the need for several runs and 2006 readout error rates together led to awful scaling…

      kirrentView on HNParent context

  3. Factoring may be easier than we think 1 comment

    • @tptacek > I believe you to be wrong about the idea that tenably factoring 1024 or 2048 bit moduli implies a solution to the elliptic curve discrete modulus problem Probably. This mathy stuff is way over my head. I'm just repeating what I read in Polynomial-Time Algorithms for…

      CieplakView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.