Wiki / Quantum

Shor's algorithm and public-key cryptography

Type
Read-up
Steward
Chris War
Facts as of
2026-10-18
Next review
2027-10-18
Status
draft

Shor’s algorithm and public-key cryptography

In one sentence: Shor’s algorithm is a quantum algorithm, published by Peter W. Shor, that factors integers and computes discrete logarithms in a number of steps polynomial in the input size. These two problems underpin widely used public-key cryptosystems.1

What it is

Factoring large integers and computing discrete logarithms are “generally thought to be hard on a classical computer”, and both “have been used as the basis of several proposed cryptosystems”.1 Shor gave efficient randomised algorithms for both problems on a hypothetical quantum computer. They take a number of steps polynomial in the input size, for example the number of digits of the integer to be factored.1

The paper was first circulated in 1994. The arXiv version was submitted on 30 Aug 1995, and the journal version appeared in the SIAM Journal on Computing (DOI 10.1137/S0097539795293172).1

Why it matters for security

  • Affected: RSA depends on factoring, and finite-field Diffie–Hellman and DSA depend on discrete logarithms. Elliptic-curve variants (ECDH, ECDSA) depend on the elliptic-curve discrete logarithm problem, which Shor’s method also addresses.23 NIST states that large-scale quantum computers “will be able to break many of the public-key cryptosystems currently in use”.2

  • Not addressed by Shor: symmetric ciphers and hash functions. Their quantum risk comes from other algorithms; see grovers-algorithm.

  • The gap between theory and practice: running Shor’s algorithm against real key sizes requires a large, error-corrected quantum computer. Published resource estimates for RSA-2048 have fallen over time:

    • 2019: about 20 million noisy qubits for about 8 hours (peer-reviewed, Quantum 2021).4
    • 2025: fewer than 1 million noisy qubits for less than a week, under the same hardware assumptions (preprint).5

    Both estimates assume a physical gate error rate of 0.1%, a surface-code cycle time of 1 µs and a control reaction time of 10 µs.45 See rsa-resource-estimates.

  • Official response: standards bodies answer this threat with post-quantum cryptography. NIST published its first three PQC standards in August 2024.2 The UK NCSC sets 2035 as the target for completing migration.3

Key facts

  • Problems solved: integer factorisation and discrete logarithms, in polynomial time on a quantum computer.1
  • First public-key schemes affected: RSA, Diffie–Hellman, DSA and their elliptic-curve variants.23
  • Lowest published RSA-2048 estimate as of 2026-10-18: fewer than 1 million noisy qubits, less than one week (preprint, May 2025).5

See also

Changelog

  • 2026-10-18 – created (draft). Open: cite a primary source for Shor’s elliptic-curve extension (e.g. Proos–Zalka 2003) instead of relying on 23.

Sources

  1. P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, arXiv:quant-ph/9508027 (v2, 1996-01-25); SIAM J. Comput., DOI 10.1137/S0097539795293172. https://arxiv.org/abs/quant-ph/9508027 (accessed 2026-10-18) ↩ ↩2 ↩3 ↩4 ↩5

  2. NIST CSRC, “Post-Quantum Cryptography” project page, updated 2026-08-05. https://csrc.nist.gov/projects/post-quantum-cryptography (accessed 2026-10-18) ↩ ↩2 ↩3 ↩4 ↩5

  3. UK NCSC, “Timelines for migration to post-quantum cryptography”, v1.0, 2025-03-20. https://www.ncsc.gov.uk/guidance/pqc-migration-timelines (accessed 2026-10-18) ↩ ↩2 ↩3 ↩4

  4. C. Gidney, M. Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”, arXiv:1905.09749; Quantum 5, 433 (2021). https://arxiv.org/abs/1905.09749 (accessed 2026-10-18) ↩ ↩2

  5. C. Gidney, “How to factor 2048 bit RSA integers with less than a million noisy qubits”, arXiv:2505.15917 (preprint), 2025-05-21. https://arxiv.org/abs/2505.15917 (accessed 2026-10-18) ↩ ↩2 ↩3

Cite as: qbZero Wiki, “Shor's algorithm and public-key cryptography”, as of 2026-10-18. https://qbzero.com/wiki/quantum/shors-algorithm/