Inside Shor's Algorithm, Without The Maths

Shor’s algorithm is often described as “trying every answer at once”. That description is wrong, and it hides the interesting part. Most of the algorithm is ordinary number theory that runs on a normal computer. The quantum computer does one specific job: it finds the length of a repeating pattern far faster than any known classical method.

This article walks through the steps for factoring an RSA modulus, uses a tiny worked example, and then explains why building a machine that can run it on a 2048-bit key is mostly an engineering problem about errors. It assumes you have read Shor, Grover And What Quantum Computers Actually Break.

Factoring Is Really Pattern Finding

The key idea predates Shor. If you can find a quantity called the order of a number, you can usually factor. Pick a number x smaller than the modulus n that shares no factor with it. Now compute x, x squared, x cubed and so on, each time keeping only the remainder after dividing by n. The remainders eventually repeat in a cycle. The length of that cycle, the smallest r for which x to the power r leaves remainder 1, is the order.

Shor’s paper notes that factoring reduces to order finding by a randomised method published by Miller in 1976.¹ Once r is known, and if it is even, the greatest common divisor of n and x to the power r/2 minus 1 often reveals a factor. Greatest common divisors are cheap to compute with Euclid’s algorithm. The only hard part is finding r, because for a 2048-bit n the cycle is astronomically long.

The Steps, Classical And Quantum

The phrase “trying every answer at once” misleads because measurement returns only one result. The quantum Fourier transform matters because it arranges the computation so that wrong answers cancel and answers related to the period reinforce each other. Shor’s paper describes an efficient circuit for this transform and the continued fraction step that follows.¹ For discrete logarithms, which underpin Diffie-Hellman and elliptic curve cryptography, the same paper gives a variant that uses two Fourier transforms over two registers.¹

Why The Hard Part Is Errors

Every step above assumes the quantum computer is perfect. Real qubits are not. They lose their state through noise, and every gate adds a little error. A 2048-bit factoring circuit needs billions of operations, so even a tiny error rate per operation would ruin the result without correction.

The fix is quantum error correction. Many noisy physical qubits are combined to act as one reliable logical qubit, with constant checks that detect and undo errors faster than they build up. The algorithm runs on logical qubits; the hardware has to supply physical ones.

The overhead is large. Craig Gidney’s May 2025 estimate for RSA-2048 needs 1,399 logical qubits and about 6.5 billion Toffoli gates.² A Toffoli gate is an operation on three qubits that is expensive to carry out with error correction, so estimates count them as a measure of total work.

The physical layout shows where the qubits go. At the busiest point of the run the paper counts 1,409 logical qubits in use. The 1,280 that hold the input sit idle in a dense storage scheme at about 430 physical qubits each, while the qubits doing the work use standard surface code patches of 1,352 physical qubits each. Counting the spare patches in the area where computation happens, the layout holds 1,537 logical qubits, which the paper describes as fewer than 1,600, and about 900,000 physical qubits, which it rounds up to one million for safety. All of this assumes a 0.1 percent physical error rate and a one microsecond correction cycle.²

For comparison, a 2012 introduction to surface code computing by Fowler and colleagues estimated that factoring a 2000-bit number would need about a billion physical qubits running for about a day, at the same 0.1 percent error rate.³ Most of the improvement since then has come from smarter circuits and error correction, not from a new version of Shor’s idea.

Where Hardware Stands

Error correction only helps when physical errors are below a threshold; otherwise adding qubits makes things worse. In December 2024 Google reported that its 105-qubit Willow chip had crossed that threshold, with logical error rates halving each time the code grew from a 3 by 3 to a 5 by 5 to a 7 by 7 grid.⁴ That is an important step, but it involves around a hundred physical qubits against the tens of thousands to about a million that current estimates require, depending on the design. How those estimates have fallen is the subject of How Many Qubits To Break RSA.