Part 8: Shor: Cryptanalysis by Physics

The security of RSA rests on a bet: that multiplying two large primes is easy and reversing the product is hopeless. The bet has held for nearly fifty years against the finest classical mathematicians alive, and it still holds against every classical computer on Earth. In 1994, Peter Shor showed the bet was never made against the right opponent. His algorithm does not factor faster than classical methods by brute persistence. It reaches factoring through a side door, period-finding, and that door happens to be exactly the shape of the machine Part 7 built.

This is where the casualty list from Part 1 stops being a table you take on faith and becomes a mechanism you can follow. The four moves are unchanged: prepare, imprint, interfere, measure. Only the target grew, from Deutsch’s one-bit toy to a 617-digit modulus. This part shows how factoring becomes period-finding, how the quantum Fourier transform reads a period the way a tuner reads a pitch, why the same move flattens elliptic curves and Diffie-Hellman even faster than it flattens RSA, and what it honestly takes to run, in physical qubits, as of 2025. No new physics past this point. Only the target.

The number-theory bridge, in one example

Shor’s first move is pure classical mathematics, and it converts a factoring problem into a hunt for a repeating pattern. This part is not quantum at all, which is exactly why it matters: it explains why factoring, of all things, exposes the periodic structure the machine feeds on.

Take a number to factor, and call it $$N$$. Pick any number $$a$$ smaller than $$N$$ that shares no factor with it, and start raising it to powers, reducing modulo $$N$$ at each step: $$a^1, a^2, a^3, \ldots$$, always taking the remainder after dividing by $$N$$. Because there are only finitely many possible remainders, the sequence must eventually repeat, and once it repeats it cycles forever. The length of that cycle (the gap after which the powers of $$a$$ start over, and the only quantity in this whole attack that needs a quantum computer to find) is called the period, written $$r$$. The arithmetic box works a small case by hand.

Here is the bridge, and it is elementary modular arithmetic, not quantum mechanics: the difference of squares $$a^r – 1 = (a^{r/2} – 1)(a^{r/2} + 1)$$. When the period $$r$$ is even and $$a^{r/2} \not\equiv -1 \pmod N$$, at least one of $$a^{r/2} – 1$$ and $$a^{r/2} + 1$$ shares a real factor with $$N$$, which you pull out in seconds by taking $$\gcd(a^{r/2} \pm 1,\ N)$$ with Euclid’s algorithm, the oldest algorithm in the book. When either condition fails you pick a new $$a$$ and rerun; random choices succeed with substantial probability. Factoring, reduced to a single unknown: the period $$r$$. Everything hard about breaking RSA now lives in one question, and it is a question about the length of a repeating cycle.

Classically, that reduction buys nothing, because finding $$r$$ for a cryptographic modulus means marching through a cycle longer than the age of the universe measured in machine cycles. The period is there. It is simply too long to walk. What Shor found is that a quantum computer does not walk it. It listens for it.

Reading a period with interference

The period-finding move is the four-move template of Part 7, and now the abstract description acquires flesh. Watch the amplitudes.

Prepare. Fill a large input register with an equal superposition of the exponents $$1, 2, 3, \ldots$$, far enough to cover many full cycles of the unknown period. Amplitude spreads across every exponent at once, the honest half of parallelism.

Imprint. In one pass, compute $$a^x \bmod N$$ into a second register. This is the expensive step, the modular exponentiation, and it is where nearly all the qubits and nearly all the runtime go; the closing sections are honest about that cost. The two registers are now entangled: each exponent in the first is bound to its power’s remainder in the second. The periodic structure of $$a$$ is now physically imprinted, because exponents exactly one period apart produced identical remainders and are therefore tied to the same value in the second register.

Interfere. Apply the quantum Fourier transform to the input register. Every exponent that shares a remainder, meaning every exponent standing one period apart from its neighbors, sends amplitude into the transform, and those contributions reinforce only at output values that match the period’s rhythm. Every other output receives contributions that point in conflicting directions and cancel. Part 4’s $$+1/2$$ against $$-1/2$$, now playing out across the whole register at once. The wrongness cancels; the period survives.

Measure. The input register is read, and it does not hand you $$r$$ directly. It yields a sample sharply peaked near an integer multiple of the pattern’s fundamental frequency. One more piece of classical arithmetic, the continued-fractions algorithm, turns that reading into a candidate for $$r$$, which may be the period or a divisor of it. You check the candidate by modular exponentiation and rerun the quantum subroutine when it misses. Hand a good $$r$$ to the difference of squares, run Euclid, and RSA is factored.

Why the whole family falls together

The lethal generality of Shor’s method comes from what periodicity is: the mathematical signature of the hidden-subgroup problem, and every classical public-key system in wide deployment today, RSA and the discrete-log family alike, is built on a member of it. Break the pattern-finding and you break all of them, at a stroke, on the same machine. The post-quantum algorithms replacing them are public-key too, built on different hard problems Shor does not touch, which is the entire point of the migration.

RSA hides a period in modular exponentiation, as above. Finite-field Diffie-Hellman and DSA rest on the discrete logarithm problem, which is period-finding wearing a different hat; Shor’s algorithm solves it with the same interference machine, no new ideas required. And elliptic-curve cryptography, ECDH and ECDSA, the long-standing default behind conventional TLS handshakes, device identity, and the key material in your phone’s secure enclave, rests on the elliptic-curve discrete logarithm. Shor breaks that too. Deployments have already begun wrapping ECDH in hybrid post-quantum key exchange, Signal’s PQXDH among them, which is exactly the right response and also proof that the industry is not waiting for the machine. And here is the cruel twist your threat model needs to internalize: where classical ECDH is still in use, elliptic curves fall to smaller quantum computers than RSA does.

That inverts the classical security story completely. Against classical attackers, a 256-bit elliptic-curve key is comfortably stronger than a 3072-bit RSA key while being twelve times shorter, which is precisely why the industry has spent fifteen years migrating to it. Against a quantum attacker, the elliptic-curve group’s tidy mathematical structure, the very compactness that made it the efficient choice, makes it a cheaper target. Elliptic curves’ greatest classical strength is a quantum liability. The migration that hardened you against the last threat model positioned you slightly worse for this one, which is the kind of irony cryptography specializes in and a clean illustration of why “quantum-resistant” is a property no amount of classical key length can buy.

What it actually takes

The gap between “the algorithm exists” and “your keys are readable” is the only thing standing between you and Q-Day, and it is measured in physical qubits.

Shor’s algorithm needs roughly $$2n$$ high-quality logical qubits to factor an $$n$$-bit number: a few thousand flawless logical qubits for RSA-2048. No such machine exists in 2025; the largest processors today carry a few hundred to low-thousands of physical qubits with error rates far too high to run Shor’s thousands of sequential operations, a distinction that is Part 10‘s entire subject and the reason the casualty list comes with a “when” attached to the “whether.” The translation from logical to physical is where the real number lives, because each logical qubit must be woven from many noisy physical ones through error correction.

That translation is a moving target, and reading it correctly means comparing like with like. The clean comparison is the surface-code line. In 2019, Gidney and Ekerå estimated 20 million noisy physical qubits and roughly eight hours. In May 2025, Gidney cut that to under one million physical qubits and under a week, on the same hardware assumptions, from better arithmetic and error correction alone. Nothing about the hardware improved between those two papers. The estimate improved, because people got smarter about the same machine.

By 2026 the frontier had moved again, and this time by changing the architecture rather than the assumptions. The Pinnacle preprint replaces surface codes with quantum LDPC codes and claims RSA-2048 with under 100,000 physical qubits at the same headline error and timing. A separate neutral-atom study from Cain and colleagues argues that cryptographically relevant Shor could run on as few as 10,000 reconfigurable atoms, trading qubit count for much longer runtimes. Both are theoretical preprints on architectures nobody has built, using different codes, connectivity, and time budgets, so they are not directly comparable with Gidney’s surface-code baseline or with each other. What they establish is not a new threshold. It is that architecture and error-correction choices can move the number by another order of magnitude before a single qubit is added to a real machine.

Do not read any of these as a countdown. A fault-tolerant machine of even 100,000 high-quality qubits is a formidable distance from today’s hardware, and I am on record against the quantum panic industry that reads every such paper as proof of imminent doom. Read the trajectory instead, the way a risk officer reads any hostile capability curve: the requirement has fallen by five orders of magnitude in fourteen years while qubit counts climb, and your defensive timeline is not set by when the lines cross. It is set by harvest now, decrypt later, which put your long-lived secrets on the clock the day they were transmitted, and by the migration deadlines regulators and insurers have already written without waiting for the physicists. The math above is why RSA and ECC are on the list. The reason to act is on a different clock entirely.

What to remember

Shor’s algorithm breaks RSA not by factoring faster but by converting factoring into period-finding, a conversion built from elementary modular arithmetic that turns the whole problem into one question: the length of a repeating cycle. That period is found by the four-move template, with modular exponentiation as the imprint and the quantum Fourier transform as the interference step that lets period-matching outputs reinforce while everything else cancels. The same method solves the discrete logarithm, so finite-field Diffie-Hellman, DSA, and all elliptic-curve cryptography fall to the same machine, with elliptic curves falling at smaller sizes than RSA because their compact structure is a quantum liability. Running it against RSA-2048 needs a few thousand logical qubits. On the like-for-like surface-code comparison, the physical qubit requirement dropped twentyfold from 2019 to 2025; architecture-specific 2026 preprints claim further reductions that are not yet commensurable. Read the trajectory rather than any single number. The reason to migrate now is not that the machine is close; it is that harvest-now-decrypt-later and regulatory deadlines already run on a clock that ignores the physicists.

Next, in Part 9, “Grover and the Honest Speedup”: Shor breaks the systems with structure. Part 9 covers the systems without it, where the only quantum attack is a generic search that runs quadratically faster than brute force, buys far less than the hype suggests once error correction is priced in, and explains precisely why your symmetric keys and hashes step into the quantum era with room to spare.