Quantum computing and Shor's algorithm in plain words

Entry 010 · 2026-05-21

In 1994 Peter Shor showed that a sufficiently capable quantum computer could factor large integers and compute discrete logarithms in polynomial time. The first half of that statement broke RSA in principle; the second half broke Diffie–Hellman in principle. "In principle" because the quantum computers that would be required don't yet exist — but the result has shaped post-quantum cryptography research for thirty years.

Shor's algorithm has two components. The first is a classical reduction of factoring to order-finding in (Z/nZ)^*. The second is a quantum subroutine that finds the order of a given element by preparing a superposition of all possible exponents, applying the modular exponentiation as a reversible quantum circuit, and reading out the period via the quantum Fourier transform. Each piece on its own is unremarkable; the combination is what made the field reorient.

The cost is enormous. A practical factoring of a 2048-bit RSA key needs roughly 2^32 logical qubits, each one stable for the entire computation. Today's best experimental quantum machines have fewer than a hundred noisy qubits; to convert noisy qubits into logical ones requires error correction overheads in the thousands or more. The gap is still very wide.

The post-quantum movement does not assume the gap will stay wide. NIST's standardization effort selected four schemes in 2024 — three of them based on lattice problems (CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON) and one based on hash trees (SPHINCS+). These are conjectured to be resistant to quantum attacks, on the grounds that the best known quantum algorithms for the underlying problems do not improve much on classical algorithms. The conjecture is being actively stress-tested, and the bounds may move; but the engineering substrate for post-quantum transition is now in place.