Peter Shor shows a quantum computer could factor large numbers quickly

Why it matters

Widely used encryption such as RSA relies on factoring being hard, so Shor's result turned quantum computing from a curiosity into a field with real security stakes.

Related

• Daniel Simon finds an exponential quantum speedup that inspires Shor (Nov 1994)
• David Deutsch describes a universal quantum computer (Jul 8, 1985)
• Peter Shor shows quantum information can be protected from errors (Oct 1, 1995)

Sources (5)

• Proceedings of the 35th Annual Symposium on Foundations of Computer Science (IEEE) Algorithms for quantum computation: discrete logarithms and factoring
  Primary sourceNov 1994

  “This paper gives Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer that take a number of steps which is polynomial in the input size, e.g., the number of digits of the integer to be factored.”

• arXiv (Peter W. Shor) Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
  Primary sourceAug 30, 1995

  “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.”

• arXiv (Peter W. Shor) The Early Days of Quantum Computation
  Independent coverageAug 21, 2022

  “When I solved it, in April 1994, I told a few people I knew and worked with, including my boss David Johnson, and a colleague at Bell Labs, Jeff Lagarias, who verified that my algorithm was correct.”

• arXiv (Seth Lloyd) The Universe as Quantum Computer
  Independent coverageDec 16, 2013

  “The situation changed in 1994, when Peter Shor showed that a relatively modestly sized quantum computer, containing a few thousand logical quantum bits or ‘qubits,’ and capable of performing around a million coherent operations, could be used to factor large numbers and so break public key cryptosystems such as RSA”

• Breakthrough Prize Foundation Winners of the 2023 Breakthrough Prizes in Life Sciences, Mathematics and Fundamental Physics Announced
  Independent coverageSep 22, 2022

  “Peter Shor went on to invent the first quantum computer algorithm that was clearly useful. Shor’s algorithm can find the factors of large numbers exponentially faster than is thought to be possible for any classical algorithm.”