Shor's algorithm

Shor's algorithm is a quantum algorithm for integer factorization and discrete logarithms, devised by mathematician Peter Shor in 1994. It is the most consequential algorithm in the history of cryptography — not because it has ever been executed at useful scale, but because its mere existence restructured the entire field of public-key security around a threat that may not materialize for decades, or may already exist in classified form. Shor's algorithm demonstrates that a sufficiently powerful quantum computer can solve the integer factorization problem and the discrete logarithm problem in polynomial time, rendering RSA, Diffie-Hellman, and elliptic curve cryptography insecure simultaneously.

The Algorithm

Shor's algorithm combines two insights that are individually classical and jointly revolutionary: modular exponentiation and the quantum Fourier transform.

The algorithm proceeds in two phases. First, it reduces factorization to order finding: given a composite integer N, pick a random integer a coprime to N, and find the smallest positive integer r such that a^r ≡ 1 (mod N). If r is even and a^(r/2) ≢ −1 (mod N), then gcd(a^(r/2) ± 1, N) yields a nontrivial factor of N. This reduction is entirely classical and dates to the 1970s.

The second phase is quantum. Order finding is equivalent to finding the period of the function f(x) = a^x mod N. Classically, this requires evaluating f at exponentially many points. Quantumly, the quantum Fourier transform extracts the period from a superposition of states in polynomial time. The quantum computer prepares a superposition of all possible exponents, computes the modular exponentiation in parallel via quantum interference, and measures the resulting state to obtain period information with high probability. The quantum speedup is exponential: what takes sub-exponential time on the best classical algorithms (the General Number Field Sieve) takes polynomial time on a quantum computer.

Why It Has Never Been Run

As of 2026, Shor's algorithm has been demonstrated only at toy scale — factoring 21, 15, and similarly small integers. The obstacle is not algorithmic but engineering: quantum error correction. Factoring a 2048-bit RSA modulus requires approximately 20 million physical qubits operating with fault-tolerant error correction, or roughly 4,000 logical qubits with highly optimized surface-code architectures. The largest quantum computers today contain roughly 1,000 physical qubits with error rates too high for useful factorization.

Yet the algorithm's practical irrelevance is itself historically significant. The field of post-quantum cryptography was born from the threat of Shor's algorithm, and the NIST post-quantum standardization process (2016–2024) selected lattice-based, code-based, and hash-based schemes that resist both classical and quantum attack. The algorithm has already done its damage without ever being executed: it forced the retirement of RSA and Diffie-Hellman as long-term trust anchors, triggered a multi-billion-dollar infrastructure migration, and established quantum computing as an existential threat to digital security — all while remaining a purely theoretical construct.

The Hidden Assumption

Shor's algorithm relies on the quantum Fourier transform, which in turn requires a quantum circuit model of computation with coherent superposition and entanglement. This is not the only model of quantum computation. Adiabatic quantum computation, topological quantum computation, and measurement-based quantum computation are alternative frameworks whose computational power relative to the circuit model is not fully resolved. Shor's algorithm is a circuit-model algorithm. Whether it can be adapted to other quantum computational paradigms, and whether those paradigms can be built more easily, remains genuinely open.

The deeper assumption is that the quantum circuit model is physically realizable at scale. This is a statement about the universe, not merely about engineering. If quantum mechanics is exactly correct and decoherence can be controlled, Shor's algorithm is a blueprint. If quantum mechanics requires modification at large scales — as some theories of quantum gravity suggest — then the algorithm may be physically unrealizable regardless of engineering prowess.

The algorithm thus sits at an unusual intersection: it is a mathematical proof that certain cryptographic systems are insecure in principle, and a physical conjecture that the principle can be instantiated. The first is settled. The second is not.

The field's obsession with Shor's algorithm has, I suspect, distracted from a more pressing question: even if quantum computers never factor large integers, what other classes of computational problem — in simulation, optimization, and learning — will they transform? Shor's algorithm is the poster child, but it may not be the revolution.