Inside the Shor demo: what it takes to break an RSA key

We built an interactive Shor estimator to answer one deceptively simple question: when does your RSA key break? Type in a key size, or paste a real public key, and the tool prints the quantum resources Shor’s algorithm needs to factor it, along with the year public hardware roadmaps are projected to get there. This note opens the hood. Every number the demo prints rests on a published resource estimate and a short scaling law, and understanding those laws is the difference between a scary headline and an engineering forecast.

If you have not tried it yet, do that first — the rest of this piece is a guided tour of what you will see.

What the tool asks, and what it answers

The left side of the demo takes three inputs. A key size — one of the presets (1024, 2048, 3072, 4096) or any value from 256 to 16,384 bits. Optionally, a real public key pasted into the box: an OpenSSH ssh-rsa AAAA… line, a PEM -----BEGIN PUBLIC KEY----- block, or a raw hexadecimal modulus. And an error-correction scheme: surface code or quantum LDPC. Press Run estimate and the terminal on the right fills in.

For RSA-2048 with the surface-code assumption, the output reads like this:

jos@quantum:~$ rsa-break --bits 2048 --ec surface

  target            RSA-2048        (2048-bit modulus)
  algorithm         Shor · Gidney–Ekerå compilation

  logical qubits    ~6,190          (≈ 3n)
  Toffoli gates     ~2.6 × 10ⁿ      (≈ 0.3 n³ · 10ⁿ–10¹⁰ ops)
  physical qubits   ~20,000,000     (surface code · 2019)
  runtime           ~8 hours

  ▶ projected breakable:  2039 – 2041
    when best-of-breed roadmaps (IBM · Quantinuum · IonQ)
    reach ~20,000,000 physical qubits

  ⓘ toggle "Quantum LDPC · 2026" for the optimistic estimate.

Four numbers, then a year. The four numbers are a chain — each one is derived from the one above it, and the chain is where all the physics lives. Let us walk down it.

Logical qubits: the ~3n line

A logical qubit is an idealised, error-free qubit — the kind the algorithm is written for, before any hardware imperfection is accounted for. Shor’s factoring circuit, compiled the way Gidney and Ekerå describe it, needs roughly three logical qubits per bit of the modulus. For a 2048-bit key that is about 6,000; the demo prints ~6,190.

Why 3n and not n? Factoring an n-bit number by Shor’s method comes down to computing a modular exponentiation in superposition. You need a register to hold numbers the size of the modulus (n qubits), plus workspace for the reversible arithmetic that adds, multiplies and reduces them. Naive schoolbook arithmetic would need far more; the modern compilations use windowed and coset-representation tricks to keep the total near 3n rather than 5n or 10n. The coefficient is an engineering result, not a law of nature — and it has been shrinking (a 2025 revision pushes the leading term toward (0.5 + ε)n at the cost of a longer runtime).

The key thing to hold onto: this is a logical count. It is small, and it is tempting to read it as “RSA falls at 6,000 qubits.” It does not. The gap between this number and a real machine is the next two rows.

Toffoli gates: the ~0.3 n³ workload

The second row measures work, not size. The dominant cost in Shor’s circuit is reversible arithmetic, and its natural unit is the Toffoli gate (a controlled-controlled-NOT, the reversible AND). The count scales as roughly 0.3 n³: modular exponentiation is O(n) modular multiplications, and each multiplication costs about O(n²) elementary reversible operations. For RSA-2048 that is about 2.6 billion Toffolis; double the key to RSA-4096 and it climbs past 2 × 10¹⁰.

Toffoli count matters far more than it first appears, because a Toffoli is not a cheap fault-tolerant operation. It has to be assembled from the universal gate set, and that pulls in the T-gate and the magic states that make T-gates expensive. In modern estimates the machinery that manufactures those magic states is a large fraction of the whole computer. We unpack that bottleneck in a companion piece, why quantum error correction — not qubit count — decides when RSA and ECC fall. For the demo, the takeaway is simpler: billions of Toffolis cannot run on bare hardware at any qubit count, which forces the jump to the next row.

Physical qubits: the error-correction multiplier

This is the most important control in the demo, and the one whose effect surprises people most. Real qubits are noisy: current devices err on the order of one operation in a thousand, so a circuit of a few thousand gates has essentially no chance of finishing correctly — and Shor needs billions. The fix is quantum error correction: encode each fragile logical qubit into a block of many physical qubits so that errors can be detected and corrected faster than they accumulate. The price is a multiplier, and the multiplier is enormous.

The error-correction toggle chooses that multiplier:

Same algorithm, same key, same ~6,190 logical qubits — and the machine swings from twenty million physical qubits to a hundred thousand purely on the choice of code. That is a ~200× difference decided by the error-correction layer alone. It is the single clearest reason there is no one honest answer to “how many qubits does it take to break RSA?”

Runtime: trading space for time

The fourth row is wall-clock time. The demo anchors it to the Gidney–Ekerå figure of about 8 hours for RSA-2048 and scales it with the Toffoli count, so RSA-4096 lands around 2.7 days. But runtime is not a fixed property of the problem — it is one point on a trade-off. You can build fewer magic-state factories and run the gates more sequentially (fewer qubits, longer runtime), or more factories in parallel (more qubits, shorter runtime). The same key can be quoted as “a million qubits in 100 days” or “a billion qubits in one hour.” The demo reports one reasonable operating point; treat the number as an order of magnitude, not a stopwatch.

The break-year: reading it off the roadmaps

The final line converts a qubit requirement into a calendar year. The method is a log-linear extrapolation: plot the largest processors on the public roadmaps of the leading vendors — IBM’s superconducting line, Quantinuum and IonQ on ion traps — and their physical-qubit counts climb roughly a fixed number of orders of magnitude per decade. Fit a straight line to log₁₀(qubits) vs. year, then invert it: feed in the qubits your key needs, read off the year that line reaches them.

Run RSA-2048 through it both ways and the effect of the error-correction toggle becomes concrete:

An eight-year swing in the projected break date — and not a single hardware assumption changed. It came entirely from the code you picked to encode the logical qubits. That is the demo’s central lesson in one table.

When the lines cross

Scroll past the terminal and the demo plots the whole story on one chart: the falling algorithmic requirement against the rising hardware reality, both on a log scale. The requirement is not a fixed target — it fell from about a billion qubits (2012) to twenty million (2019) to under a million (2025) to a hundred-thousand-scale blueprint (2026), a drop of roughly 200× in six years, driven by algorithm and error-correction advances rather than by hardware. Meanwhile the demonstrated hardware climbs from tens to hundreds to a thousand-plus physical qubits.

Where the falling requirement meets the rising hardware is the plausible window for a cryptographically relevant quantum computer — and it is a moving target, not a fixed date.

On the current fit that window sits in the early-to-mid 2030s. It is worth stressing what that line is and is not: it is a trend extrapolation over aspirational roadmaps, not a prediction. Roadmaps slip. But the direction of travel — requirement down, hardware up — has been steady enough that the honest question is when, not whether.

Paste your own key — and why nothing leaves the browser

The demo does more than accept a bit count. Paste an actual public key and it parses the modulus in your browser: it understands the OpenSSH wire format (ssh-rsa AAAA…), walks the DER of a PEM key to find the modulus integer, or reads a bare hex modulus. It measures the true bit length and feeds that into the same model. You can generate a real pair locally and analyse it:

$ ssh-keygen -t rsa -b 2048 -f rsa_demo -N ""
# then paste rsa_demo.pub into the demo

All of this runs client-side — the key never leaves your machine and nothing is transmitted. Now try the experiment the tool nudges you toward: bump -b from 2048 to 4096 and watch the break-year. It moves out by only about a year. That is the sobering point buried in the arithmetic: the cost of breaking a key grows polynomially with its size, while hardware grows exponentially with time. Doubling your RSA key does not buy a decade — you cannot out-key Shor.

The fix the demo points to

Shor breaks RSA and elliptic-curve cryptography alike, because both reduce to the same hidden-subgroup problem a quantum computer solves efficiently. The mitigation is already standardised and does not wait on any of the numbers above: post-quantum cryptography built on problems Shor cannot touch — ML-KEM (Kyber, FIPS 203) for key exchange, ML-DSA (Dilithium, FIPS 204) and SLH-DSA (SPHINCS+, FIPS 205) for signatures. Because an adversary can record encrypted traffic today and decrypt it once a machine exists (“harvest now, decrypt later”), the migration deadline is set by how long your data must stay secret, not by the break-year. The demo’s post-quantum section lays out the standards in full.