Shor's algorithm

Shor's algorithm is a quantum algorithm, published by Peter Shor in 1994, that factors large integers and computes discrete logarithms in polynomial time. Because RSA, Diffie-Hellman, and elliptic curve cryptography depend on exactly those problems being infeasible, a sufficiently large quantum computer running Shor's algorithm would break nearly all public-key cryptography deployed today.

#What the algorithm does

Shor's insight was to reduce factoring to period finding (Shor 1994). To factor a number N, the algorithm picks a random base a and looks for the period of the function f(x) = a^x mod N. A quantum computer finds that period efficiently using the quantum Fourier transform, which detects periodicity across a superposition of exponentially many evaluations. Classical post-processing then converts the period into a nontrivial factor of N with high probability. A closely related variant solves the discrete logarithm problem, in both finite fields and elliptic curve groups.

The result is a polynomial-time algorithm, with cost growing roughly as the cube of the bit length of the number, for problems whose best classical algorithms are super-polynomial. The general number field sieve, the best known classical factoring method, is sub-exponential but still utterly impractical at 2048-bit sizes. Shor's algorithm removed the theoretical barrier; only the machine is missing.

#Why it breaks deployed cryptography

Elliptic curve schemes are, counterintuitively, the softer target. Resource estimates indicate that computing a 256-bit elliptic curve discrete logarithm needs fewer logical qubits and gates than factoring RSA-2048, roughly 2330 logical qubits for the curve P-256 (Roetteler et al. 2017). The consequences for signature schemes used in blockchains are covered under quantum threat to ECDSA.

Breaking a key exchange retroactively is the sharpest consequence: recorded traffic whose session keys were agreed with Diffie-Hellman or ECDH can be decrypted after the fact, the scenario known as harvest now, decrypt later.

#Resource estimates for RSA-2048

Running Shor's algorithm against real key sizes requires quantum error correction, so the relevant metric is physical (noisy) qubits, not idealized logical ones (qubit, logical qubit).

The benchmark estimate for years was Gidney and Ekerå's 2019 analysis: factoring a 2048-bit RSA integer in about 8 hours using roughly 20 million noisy qubits, assuming physical gate error rates around 0.1 percent and surface code error correction (Gidney and Ekerå 2019). In 2025 Gidney revised the estimate sharply downward: fewer than 1 million noisy qubits running for under a week, using improved arithmetic, approximate residue representations, and denser error correction (Gidney 2025). The 20-fold reduction in six years came from algorithm and error-correction research, not better hardware, and it is one reason security agencies treat quantum resource estimates as figures that move in only one direction.

For scale, the largest quantum processors as of early 2026 hold on the order of 1000 physical qubits. The gap to a cryptographically relevant machine remains roughly three orders of magnitude in qubit count, along with major unsolved engineering problems; see quantum computer.

#Experimental record

The honest experimental record is short. In 2001 an IBM group factored 15 into 3 x 5 using a 7-qubit nuclear magnetic resonance device (Vandersypen et al. 2001). In 2012 a photonic experiment factored 21 using a qubit-recycling technique (Martin-Lopez et al. 2012). These remain the representative demonstrations of Shor-style factoring.

Even these results carry a caveat: the circuits were compiled using knowledge of the answer, so they demonstrate the algorithm's structure rather than its power (Smolin, Smith, and Vargo 2013). Larger factoring claims that appear periodically rely on adiabatic optimization, variational methods, or numbers with special structure, none of which use Shor's algorithm or scale to cryptographic sizes. As of early 2026, no quantum computer has factored any number that poses the slightest cryptographic challenge.

#Significance

Shor's algorithm is the founding motivation for post-quantum cryptography and the NIST standardization effort. It defines the threat model behind Q-Day planning: the algorithm is public, well analyzed, and waiting for hardware. Replacements such as ML-KEM and ML-DSA are built on lattice problems for which no comparable quantum algorithm is known (lattice-based cryptography).