114
Part Three · B · Algorithms

Shor's algorithm: factoring and discrete log

The security of most internet traffic rests on a simple asymmetry: multiplying two large primes is easy, and recovering them from their product is, as far as anyone knows, practically impossible for an ordinary computer. In 1994 Peter Shor found a quantum algorithm that factors in polynomial time. The algorithm is certain. What is uncertain is when a machine big and reliable enough to run it against real keys will exist. This chapter runs Shor’s algorithm end to end for 15, then gives you an honest account of the distance to 2048-bit RSA.

On the plate: the output of the quantum period-finding step for 15.

From factoring to a period

Pick aa coprime to NN. The sequence ax mod Na^x \bmod N repeats with some period rr, the order of aa. If rr is even and ar/2≢−1a^{r/2}\not\equiv -1, then (ar/2−1)(ar/2+1)(a^{r/2} - 1)(a^{r/2} + 1) is a multiple of NN without either factor being one, so gcd⁡(ar/2±1,N)\gcd(a^{r/2}\pm1, N) gives nontrivial factors. For a random aa this works with probability at least one half. Finding rr classically is as hard as factoring. Quantumly, it is phase estimation (Chapter 113) on the unitary ∣y⟩→∣ay mod N⟩|y\rangle\to|ay \bmod N\rangle, whose eigenphases are k/rk/r. Established

Run it for 15

Choose aa: . With eight counting qubits, the outcomes are multiples of 256/r256/r. For a=7a = 7, r=4r = 4: peaks at 0, 64, 128 and 192. Measure 192: 192/256=3/4192/256 = 3/4, and the denominator gives r=4r = 4. Then 72=497^2 = 49, and gcd⁡(48,15)=3\gcd(48, 15) = 3, gcd⁡(50,15)=5\gcd(50, 15) = 5. For a=14a = 14, r=2r = 2 but 14≡−114 \equiv -1: a failure, so pick another aa.

When rr does not divide 2t2^t, peaks blur, and the continued-fraction expansion of the measured fraction finds the closest fraction with a small denominator, which is k/rk/r.

The expensive part

The quantum Fourier transform is cheap. The cost is modular exponentiation, computing ax mod Na^x \bmod N reversibly for a superposition of xx: thousands of qubits of arithmetic with uncomputation (Chapter 94). The same structure breaks discrete logarithms, including the elliptic-curve cryptography in most web connections, with fewer qubits than RSA of equivalent strength. Beware of “record” factorings: John Smolin, Graeme Smith and Alexander Vargo showed in 2013 that most published demonstrations used the known answer to simplify the circuit, which proves nothing. Established

How far from RSA-2048

Estimates assume surface-code error correction (Chapter 139) on hardware with about 0.1% gate error and a 1 µs cycle. Craig Gidney and Martin Ekerå’s 2019 estimate: about 20 million physical qubits for 8 hours. Gidney’s 2025 estimate: under one million physical qubits for under a week, by trading time for space with better arithmetic and storage. Choose: or . Oded Regev’s 2023 algorithm, published in 2025, uses fewer gates per run, about n1.5n^{1.5}, at the cost of more runs and a number-theoretic assumption.

Today’s largest machines have hundreds to a few thousand physical qubits with error rates near that 0.1% threshold. When a machine of a million good qubits will exist, if ever, is genuinely uncertain. Because encrypted data can be stored now and decrypted later, standards bodies are already moving to post-quantum cryptography (Chapter 133). Debated on timing.

What you now have

The reduction from factoring to order finding, the quantum period-finding step as phase estimation, Shor’s algorithm run for 15, continued fractions, why modular exponentiation dominates, the extension to discrete logarithms, and the current resource estimates for RSA-2048.

· · ·

Three questions to carry with you.

What does the quantum computer actually find?tap
The order r of a modulo N, by phase estimation.
Why does a = 14 fail for N = 15?tap
r = 2 and 14 ≡ −1 mod 15, so gcd gives only 1 and 15.
What is the 2025 estimate for RSA-2048?tap
Under a million noisy qubits running for under a week, under stated hardware assumptions.

And one to work out. For N=15N = 15, a=7a = 7, r=4r = 4: what is gcd⁡(72−1,15)\gcd(7^2 - 1, 15)?

gcd =

Sources: P. W. Shor, SIAM J. Comput. 26, 1484 (1997) (FOCS 1994). C. Gidney and M. Ekerå, Quantum 5, 433 (2021) (arXiv 2019). C. Gidney, arXiv:2505.15917 (2025). O. Regev, J. ACM (2025), arXiv:2308.06572. J. A. Smolin, G. Smith and A. Vargo, Nature 499, 163 (2013). Checked by code: orders mod 15 (a = 2, 7, 8, 13 → 4; 4, 11, 14 → 2), peaks k·256/r, factors 3 and 5, and the a = 14 failure.

Next · Chapter 115
Grover's search, amplitude amplification, and its optimality

Searching a million entries takes about 800 looks. Why that matters less than it sounds.

Turn the page