What Shor's Algorithm Actually Breaks

Shor's algorithm is the reason people say quantum computers will break encryption. The sentence is true and the picture most of us carry with it is wrong, because the algorithm is not a quantum machine that factors numbers. It is ordinary arithmetic with one quantum step bolted into the middle.

We ran the ordinary part exhaustively over sixteen numbers to see how much of the algorithm needs a quantum computer. It comes down to one step; the rest is arithmetic you could do by hand.

The shape of the thing

To factor a number N, Shor's method goes like this. Pick some number a smaller than N. Look at the sequence a, a², a³ and so on, each taken modulo N. That sequence repeats, and the length of the repeat is called the period. Find the period, and a short piece of arithmetic turns it into a factor of N.

Everything in that paragraph is classical except six words: find the period. That is the quantum step, and it is the only one.

So we took the classical scaffolding and tested it to destruction. For each of sixteen semiprimes, we tried every valid starting value of a, computed the period by direct search, and checked whether the arithmetic actually produced a factor — verifying each claimed factor by dividing.

Across all sixteen the worst case was 50.8% and the mean 73.8%. Every number was factored. The textbook guarantee is "at least half the valid starting values work", and our own measurement did not contradict it — the worst case sat just above the line.

Why it can fail, and why that is fine

Roughly a quarter of attempts fail, and they fail for two specific and undramatic reasons. Either the period comes out odd, in which case the arithmetic that turns it into a factor cannot proceed, or it comes out even but lands on a degenerate case that yields only N itself and 1 — factors, technically, and useless.

When that happens you pick a different a and go again. That is the whole recovery procedure. An algorithm that works three times in four and costs nothing to retry is, for practical purposes, an algorithm that works.

There is also a case where you get a factor without the quantum step at all: if your randomly chosen a happens to share a factor with N, an ordinary greatest-common-divisor calculation hands you the answer immediately. For N = 15 that happened for 6 of the 14 candidates. It is a reminder that the hard part of factoring is not "find a factor" but "find a factor of a number specifically constructed to make that difficult", which is what an RSA modulus is.

The step we cheated on

We found each period by walking the sequence until it repeated. That works beautifully for numbers like 119 and not at all for numbers with 617 digits, because the walk gets exponentially longer as the number grows. It is precisely the step a quantum computer would do differently, and doing it by brute force is why this measurement runs on toy numbers and stops there.

So this page has measured the scaffolding and simulated nothing quantum. Which matters, because the interesting claims about Shor are all about the step we skipped.

You can watch the classical difficulty yourself. Our factoring calculator will take the numbers in the table above apart instantly, and will keep doing so for numbers far larger than anything here — because classical factoring is only hard at cryptographic sizes, not at everyday ones. Our prime number checker makes the same point from the other direction: testing whether a number is prime is easy, while splitting it into factors is not, and that asymmetry is the entire foundation of RSA.

What would actually be needed

The published estimates for running Shor against RSA-2048 are large, and we are quoting them rather than measuring them — nothing on this page could establish a hardware figure. The most cited estimate, from Gidney and Ekerå in 2021, is roughly 20 million noisy physical qubits running for about 8 hours.

Publicly reported gate-based machines are on the order of a thousand physical qubits. The gap is not a matter of waiting for the next generation of chip, and the reason is not chip size but error correction: physical qubits are noisy, and the number of them required to build one reliable logical qubit is brutal. We put numbers on that exchange rate in a companion guide, and it is the single most clarifying arithmetic in this subject.

What this means for anything you actually run

Two practical points follow, and they are narrower than "encryption is broken".

First, Shor threatens a specific family: cryptography whose security rests on factoring or on discrete logarithms. That is RSA, Diffie-Hellman and elliptic-curve cryptography — the algorithms that establish a connection. It does not threaten symmetric encryption or hashing in the same way. A hash is not vulnerable to Shor at all, and symmetric ciphers face only the milder, quadratic pressure of Grover's search.

Second, the migration that matters is already happening at the transport layer, and it is measurable today: we found post-quantum key exchange running on our own site, and measured what it costs in bytes.

What none of this changes is password practice. Shor does not read passwords; it attacks the mathematics of key establishment. If you want to improve something concrete this week, a password strength test is a better use of ten minutes than any amount of quantum preparation.

This guide explains a published algorithm using our own simulation of its classical components. It is educational and is not security advice; migration planning should follow current guidance from a standards body.