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 coprime to . The sequence repeats with some period , the order of . If is even and , then is a multiple of without either factor being one, so gives nontrivial factors. For a random this works with probability at least one half. Finding classically is as hard as factoring. Quantumly, it is phase estimation (Chapter 113) on the unitary , whose eigenphases are . Established
Run it for 15
Choose : . With eight counting qubits, the outcomes are multiples of . For , : peaks at 0, 64, 128 and 192. Measure 192: , and the denominator gives . Then , and , . For , but : a failure, so pick another .
When does not divide , peaks blur, and the continued-fraction expansion of the measured fraction finds the closest fraction with a small denominator, which is .
The expensive part
The quantum Fourier transform is cheap. The cost is modular exponentiation, computing reversibly for a superposition of : 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 , 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.
And one to work out. For , , : what is ?
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.