European quantum technologiesSign inCreate accountContact & information
QUANTUM
EUROPE

Shor's algorithm: factoring and discrete logarithms

Algorithms and benchmarks / Factoring and cryptanalysis

Finds the prime factors of a large integer, or a discrete logarithm, in time that grows only polynomially with the number of digits. A large enough error-corrected quantum computer running it would break RSA and elliptic-curve public-key cryptography, which is why post-quantum cryptography is being deployed now.

Era
Fault-tolerant
Problem class
Factoring and cryptanalysis
Speedup
Superpolynomial over the best known classical factoring methods, whose running time grows faster than any polynomial in the number of digits (Shor 1997).

How it works

The problem is turned into finding the period of a modular function. A quantum register holds a superposition of inputs, the function is computed in superposition with reversible modular arithmetic, and the quantum Fourier transform reveals the period; ordinary computers finish the job.

Typical use cases

  • Assessing when public-key cryptography (RSA, elliptic curves) could be broken, which sets the pace of the move to post-quantum cryptography.

Related pages

Resource estimates

Figures exactly as stated by their authors, with their assumptions. They are estimates under those assumptions, not forecasts, and they tend to fall as methods improve.

Factoring a 2048-bit RSA integer (2021, peer-reviewed)
QuantityValue as stated
Noisy physical qubits20 million
Runtime8 hours
Logical qubits (formula for an n-bit integer)3n + 0.002 n lg n

Assumptions: Physical gate error rate 10^-3, surface code cycle time 1 microsecond, control reaction time 10 microseconds, planar grid of qubits with nearest-neighbour connectivity.

Source: C. Gidney et al. 2021, Quantum 5, 433 (2021); arXiv:1905.09749

Factoring a 2048-bit RSA integer (2025, preprint)
QuantityValue as stated
Noisy physical qubitsfewer than one million
Runtimeless than a week

Assumptions: The same hardware assumptions as Gidney and Ekerå (2021): uniform gate error rate 0.1%, surface code cycle time 1 microsecond, control system reaction time 10 microseconds, square grid with nearest-neighbour connections. The longer runtime comes mainly from more Toffoli gates and fewer magic state factories.

Source: C. Gidney 2025, arXiv:2505.15917 (preprint, May 2025)

Factoring a 2048-bit RSA integer with a multimode memory (2021, peer-reviewed)
QuantityValue as stated
Physical qubits in the processor13,436
Memory28 million spatial modes and 45 temporal modes
Runtime177 days

Assumptions: Physical gate error rate 10^-3, processor cycle time 1 microsecond, 3D gauge colour codes with a 0.75% threshold, superconducting processor linked by a microwave interface to a photon-echo memory in rare-earth-ion-doped solids with a 2-hour storage time (a 1-second storage time adds about 23% to the runtime).

Source: É. Gouzien et al. 2021, Phys. Rev. Lett. 127, 140503 (2021); arXiv:2103.06159

256-bit elliptic curve discrete logarithm with cat qubits (2023, peer-reviewed)
QuantityValue as stated
Cat qubits126,133
Runtime9 hours

Assumptions: Ratio between single- and two-photon losses of 10^-5, cycle time 500 ns, about 19 photons per cat state on average, 2D grid with nearest-neighbour connectivity, repetition code against phase errors, lattice surgery and off-line magic states for Toffoli gates.

Source: É. Gouzien et al. 2023, Phys. Rev. Lett. 131, 040602 (2023); arXiv:2302.06639

256-bit elliptic curve discrete logarithm (NIST P-256), logical level (2017, peer-reviewed)
QuantityValue as stated
Logical qubits (upper bound)2,330
Toffoli gates (upper bound)about 1.29 × 10^11

Assumptions: Logical-level counts with no error-correction overhead. The portal evaluated the formulas stated in the abstract, 9n + 2⌈log2 n⌉ + 10 qubits and 448 n^3 log2 n + 4090 n^3 Toffoli gates, at n = 256.

Source: M. Roetteler et al. 2017, ASIACRYPT 2017; arXiv:1706.06752

256-bit elliptic curve private key, logical level (2023, preprint)
QuantityValue as stated
Toffoli gates per keyabout 50 million

Assumptions: Logical Toffoli count from the title of the paper; its hardware figures assume a fault-tolerant surface-code machine in an active-volume architecture with non-local connections between modules and a 10 microsecond code cycle.

Source: D. Litinski 2023, arXiv:2306.08585 (preprint, June 2023)

Demonstrations

  • 2016: The number 15 was factored with a scalable Shor circuit on seven trapped-ion qubits plus four cache qubits, with a success probability above 90%. (T. Monz et al. 2016)
  • 2025: The KPI booklet of the Quantum Flagship gives 15 as the largest reliable instance of Shor’s algorithm on an EU computing system for 2023 and 2024 (KPI Comp 2c). (Quantum Flagship Strategic Advisory Board 2025)

Hardware platforms that fit

  • Superconducting qubits: The RSA-2048 estimates of Gidney and Ekerå (2021) and Gidney (2025) assume a square or planar grid of qubits with nearest-neighbour connections and a 1 microsecond surface code cycle, the layout of superconducting chips; the cat-qubit estimate of Gouzien et al. (2023) also uses a superconducting-circuit architecture.
  • Trapped ions: Fifteen was factored with a scalable version of the algorithm on an ion-trap computer (Monz et al. 2016).
  • Photonic qubits: Litinski (2023) sets out the elliptic-curve estimate for a fault-tolerant machine in a silicon-photonics-inspired 'active-volume' architecture.

What you need to run it

Classical simulation
Only toy instances: factoring 15 needs a few qubits and simulates on a laptop. Cryptographic sizes need thousands of logical qubits, far beyond any classical simulation.
Noisy hardware (NISQ)
Not applicable for this family.
Fault-tolerant machine
Thousands of logical qubits, Toffoli counts from tens of millions upwards and magic state factories; under the cited assumptions, from under a million to 20 million physical qubits for RSA-2048, or about 126,000 cat qubits for a 256-bit elliptic curve.
Annealer or analogue simulator
Not applicable for this family.

Calculate the memory of a simulation

Where to run it in Europe

Superconducting qubits

Trapped ions

Photonic qubits

The full infrastructure catalogue · The infrastructure deployment tracker

Software

European tools in the software directory

A listing is not an endorsement; check each tool for the features you need.

Limitations and open questions

  • Every cited estimate for cryptographically relevant sizes assumes error-corrected hardware far larger than any machine built so far.
  • Estimates fall as methods improve: under the same hardware assumptions the RSA-2048 figure went from 20 million noisy qubits (Gidney and Ekerå, arXiv 2019, published 2021) to fewer than one million (2025 preprint).
  • Demonstrations so far factor numbers that ordinary computers factor instantly; they test hardware and compilers, not cryptographic risk.

In the Quantum Algorithm Zoo

Index: the Quantum Algorithm Zoo by Stephen P. Jordan, last updated 2026-09-10, checked 2026-10-23. The portal links to it and copies no description from it. Browse the full Quantum Algorithm Zoo

Named in European procurements

None of the procurement documents read for this release names it.

Sources

  1. P. W. Shor (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing 26, 1484 (1997); arXiv:quant-ph/9508027. Read: abstract page, retrieved 2026-10-23.
  2. C. Gidney, M. Ekerå (2021). How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum 5, 433 (2021); arXiv:1905.09749. Read: abstract page, retrieved 2026-10-23.
  3. C. Gidney (2025). How to factor 2048 bit RSA integers with less than a million noisy qubits. arXiv:2505.15917 (preprint, May 2025). Read: abstract page, retrieved 2026-10-23.
  4. É. Gouzien, D. Ruiz, F.-M. Le Régent, J. Guillaud, N. Sangouard (2023). Performance Analysis of a Repetition Cat Code Architecture: Computing 256-bit Elliptic Curve Logarithm in 9 Hours with 126133 Cat Qubits. Phys. Rev. Lett. 131, 040602 (2023); arXiv:2302.06639. Read: abstract page, retrieved 2026-10-23.
  5. D. Litinski (2023). How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates. arXiv:2306.08585 (preprint, June 2023). Read: abstract page, retrieved 2026-10-23.
  6. T. Monz, D. Nigg, E. A. Martinez, M. F. Brandl, P. Schindler, R. Rines, S. X. Wang, I. L. Chuang, R. Blatt (2016). Realization of a scalable Shor algorithm. Science (2016), DOI 10.1126/science.aad9480; arXiv:1507.08852. Read: abstract page, retrieved 2026-10-23.
  7. É. Gouzien, N. Sangouard (2021). Factoring 2048-bit RSA Integers in 177 Days with 13436 Qubits and a Multimode Memory. Phys. Rev. Lett. 127, 140503 (2021); arXiv:2103.06159. Read: abstract page, retrieved 2026-10-23.
  8. M. Roetteler, M. Naehrig, K. M. Svore, K. Lauter (2017). Quantum resource estimates for computing elliptic curve discrete logarithms. ASIACRYPT 2017; arXiv:1706.06752. Read: abstract page, retrieved 2026-10-23.
  9. Quantum Flagship Strategic Advisory Board (2025). Quantum Flagship Strategic Advisory Board: KPI booklet (March 2025). Booklet read for the KPI observatory. Read: booklet (see the KPI observatory), retrieved 2026-10-23.

Contact & information · Privacy and cookies · Legal notice · Terms of use · Accessibility

Image credits · All tools and pages