The 1994 result that put a timer on the internet

In 1994, Peter Shor proved that a quantum computer could factor huge integers in polynomial time. That one paper quietly put an expiry date on RSA, Diffie–Hellman and elliptic-curve cryptography.

Those three schemes protect almost everything: HTTPS, bank transfers, VPNs, messaging, software updates, crypto wallets. Their security rests on one bet — that factoring (or taking discrete logarithms) is brutally hard.

For classical computers, the bet holds. A 2048-bit RSA key is beyond any realistic amount of classical compute. Shor's algorithm doesn't brute-force it. It finds a hidden rhythm in the number and listens for it with quantum interference.

This is the full case study: the number theory, the quantum circuit, a worked example you can check by hand, the complexity math, and where the hardware actually stands right now.

The target: RSA in five lines of math

RSA's entire security story fits on an index card.

1. Pick two huge primes p and q. Publish their product N = p × q.

2. Compute φ(N) = (p − 1)(q − 1). Keep it secret.

3. Choose a public exponent e (usually 65537) with gcd(e, φ(N)) = 1.

4. Compute the private key d so that e × d ≡ 1 (mod φ(N)).

5. Encrypt: c = mᵉ mod N. Decrypt: m = cᵈ mod N.

Anyone can see N and e. Getting d requires φ(N), and φ(N) requires p and q. Factor N and RSA is dead.

The best classical attack is the general number field sieve (GNFS). Its heuristic running time is:

L(N) = exp( (c + o(1)) · (ln N)^(1/3) · (ln ln N)^(2/3) ), with c = (64/9)^(1/3) ≈ 1.923

That's sub-exponential: far better than brute force, but it still explodes as keys get longer.

The real-world numbers make the point. RSA-250 (829 bits) fell in February 2020 after about 2,700 core-years of compute — 2,450 for sieving, 250 for the matrix step (Schneier).

In September 2026, Eric Lu at Cognition broke RSA-260 (862 bits) with a GPU sieve built by the Devin coding agent. It took about 4,900 GPU-days, roughly $400,000 at market rates (PostQuantum).

The same scaling formula puts RSA-2048 at about 91 billion times RSA-260's work — roughly 1.2 trillion GPU-years. No classical fleet closes that gap. That's the wall Shor walks around.

The trick: factoring is secretly a rhythm problem

Shor didn't attack factoring head-on. He used an older number-theory reduction that turns factoring into finding a period.

Pick a random a with 1 < a < N. If gcd(a, N) > 1, you got lucky — that's already a factor. Otherwise, look at the powers of a modulo N:

a⁰, a¹, a², a³, … (mod N)

This sequence must eventually repeat. The smallest r > 0 with aʳ ≡ 1 (mod N) is called the order (or period) of a.

Now the key move. If r is even, rewrite aʳ − 1 ≡ 0 as a difference of squares:

(a^(r/2) − 1) · (a^(r/2) + 1) ≡ 0 (mod N)

So N divides the product of those two numbers. N can't divide the first bracket, or r/2 would be a smaller period. If also a^(r/2) ≢ −1 (mod N), N can't divide the second bracket either.

The only way out: p and q are split across the two brackets. So:

p = gcd(a^(r/2) − 1, N) and q = gcd(a^(r/2) + 1, N)

The gcd is cheap — Euclid's algorithm handles 2048-bit numbers in microseconds.

It fails only if r is odd or a^(r/2) ≡ −1 (mod N). For an odd N with k distinct prime factors, a random a succeeds with probability at least 1 − 1/2^(k−1). For an RSA modulus (k = 2), that's at least 50% per try. A handful of tries and you're done.

The takeaway: every part of factoring is easy except one. Find r, and N falls.

Do it by hand: N = 15 and N = 21

Take N = 15 and a = 7. gcd(7, 15) = 1, so we look for the period.

x

7ˣ mod 15

0

1

1

7

2

4

3

13

4

1 (back to the start)

The period is r = 4. It's even, and a^(r/2) = 7² mod 15 = 4, which isn't −1 (that would be 14). So:

gcd(4 − 1, 15) = gcd(3, 15) = 3

gcd(4 + 1, 15) = gcd(5, 15) = 5

15 = 3 × 5. Done.

Now N = 21 with a = 2. The powers run 1, 2, 4, 8, 16, 11, then 1 again, so r = 6. Then 2³ = 8, and:

gcd(7, 21) = 7 and gcd(9, 21) = 3

21 = 3 × 7.

A failure case, so you see it happen: N = 15, a = 14. The period is r = 2, but 14¹ ≡ −1 (mod 15). Both gcds come out trivial (15 and 1). Throw it away, pick another a.

Why a classical computer can't just do this for RSA-2048. The period r can be nearly as large as N itself. Walking the sequence one power at a time takes up to about N steps — for a 2048-bit N, that's around 2^2048. There are only about 2^266 atoms in the observable universe. No known classical shortcut finds r fast. That's the step Shor hands to a quantum computer.

The quantum part: listening for the period

Here's the core of the algorithm. Let n = number of bits in N. You need two quantum registers:

• Input register: t qubits, holding Q = 2ᵗ values, with N² ≤ Q < 2N² (so t ≈ 2n).

• Output register: n qubits, enough to hold any number mod N.

Step 1 — Superposition. Apply a Hadamard gate to every input qubit. The input register now holds every x from 0 to Q − 1 at once, with equal weight:

|ψ₁⟩ = (1/√Q) · Σₓ |x⟩|0⟩

Step 2 — Modular exponentiation. Run one reversible circuit that computes aˣ mod N into the output register:

|ψ₂⟩ = (1/√Q) · Σₓ |x⟩|aˣ mod N⟩

This is the famous "quantum parallelism" — but it's not "trying every answer at once." Measure now and you get one random pair (x, aˣ mod N). Useless. The power comes from what happens next.

Step 3 — Collapse into a comb. Measure the output register (or just ignore it — the math is identical). You get some value z. Only inputs with aˣ ≡ z survive, and those are spaced exactly r apart:

|ψ₃⟩ = (1/√M) · Σⱼ |x₀ + j·r⟩, j = 0 … M − 1, M ≈ Q/r

The input register is now a comb with teeth every r steps. But it starts at a random offset x₀. Measure it directly and you get one random tooth, which tells you nothing about r.

Step 4 — Quantum Fourier Transform. Apply the QFT to the input register:

QFT: |x⟩ → (1/√Q) · Σₖ e^(2πi·x·k/Q) |k⟩

Applied to the comb, the amplitude of each output k becomes:

A(k) = (1/√(MQ)) · e^(2πi·x₀·k/Q) · Σⱼ e^(2πi·j·r·k/Q)

Two things happen. First, the random offset x₀ is now just a phase — it disappears when you square the amplitude. Second, the inner sum is a geometric series:

P(k) = |A(k)|² = sin²(π·M·r·k/Q) / ( M·Q · sin²(π·r·k/Q) )

When r·k/Q is close to a whole number s, every term in the sum points the same way. The waves add up. Everywhere else, they cancel. So the measurement lands, with high probability, near:

k ≈ s · Q / r, for some s in {0, 1, …, r − 1}

The chance of hitting one of these peaks is at least 4/π² ≈ 40.5% per run. Think of the QFT as a spectrum analyzer: a signal that repeats every r steps shows up as sharp lines spaced Q/r apart.

Step 5 — Continued fractions (classical). You measured some k. You know k/Q ≈ s/r, within 1/(2Q). Because Q ≥ N² and r < N, only one fraction with denominator below N is that close. The continued-fraction expansion of k/Q finds it in polynomial time.

If s and r share no common factor, the denominator is r. Check that aʳ ≡ 1 (mod N). If not, run again, or combine denominators from a few runs. Then hand r to the gcd step from the previous section.

That's the whole algorithm: classical setup, one quantum subroutine, classical cleanup.

The quantum run for N = 15, amplitude by amplitude

Same example, a = 7, now on a simulated quantum computer. To keep it writable, use a 4-qubit input register (Q = 16). The textbook rule asks for Q = 256, but since r = 4 divides both, the peaks land in exactly the same places.

After Steps 1–2, the state pairs every x with 7ˣ mod 15. Grouped by output value:

|ψ₂⟩ = ¼ · [ (|0⟩+|4⟩+|8⟩+|12⟩)|1⟩ + (|1⟩+|5⟩+|9⟩+|13⟩)|7⟩ + (|2⟩+|6⟩+|10⟩+|14⟩)|4⟩ + (|3⟩+|7⟩+|11⟩+|15⟩)|13⟩ ]

The period is already visible: every group is spaced 4 apart.

Step 3. Say the output register reads 4. The input collapses to:

|ψ₃⟩ = ½ · ( |2⟩ + |6⟩ + |10⟩ + |14⟩ )

Offset x₀ = 2, spacing r = 4, M = 4 teeth.

Step 4. Apply the 16-point QFT:

A(k) = ⅛ · e^(2πi·2k/16) · Σⱼ e^(2πi·j·k/4), j = 0 … 3

That inner sum is 4 when k is a multiple of 4, and exactly 0 otherwise. So |A(k)| = ½ for k ∈ {0, 4, 8, 12} and zero everywhere else. Twelve of the sixteen outcomes are wiped out by interference.

Step 5. Read off k/Q:

• k = 0 → 0/16. No information. Run again.

• k = 4 → 4/16 = 1/4. Denominator r = 4. Works: factors 3 and 5.

• k = 8 → 8/16 = 1/2. Candidate r = 2, but 7² mod 15 = 4 ≠ 1. Fails (here s = 2 shares a factor with r). Run again.

• k = 12 → 12/16 = 3/4. Denominator r = 4. Works.

Two of four equally likely outcomes give the answer directly: a 50% success rate per run. Two runs give you 75%, three give you 87.5%.

The complexity: polynomial vs. sub-exponential

Let n = log₂ N, the key length in bits. Almost all the cost sits in Step 2, modular exponentiation. It's built from repeated squaring: about 2n controlled modular multiplications of n-bit numbers.

• Schoolbook multiplication: O(n²) per multiply → O(n³) gates total.

• Fast (Schönhage–Strassen) multiplication: O(n² · log n · log log n).

• Harvey–van der Hoeven multiplication (2019): O(n² · log n).

The QFT is cheap by comparison: O(n²) gates exactly, or about O(n log n) if you drop rotations too small to matter. Classical post-processing is polynomial too.

Qubits: the textbook layout uses about 3n. Beauregard's 2003 circuit needs only 2n + 3 — that's 4,099 logical qubits for RSA-2048. Recent tricks cut the logical count further, at the price of more gates.

This is why factoring sits in the complexity class BQP: problems a quantum computer solves in polynomial time with bounded error.

What that means in practice — double the key from 1024 to 2048 bits:

Shor (quantum)

GNFS (classical)

Scaling in key bits n

Polynomial, ~n³ or better

Sub-exponential, exp(~1.92 · (ln N)^(1/3) · (ln ln N)^(2/3))

Cost of going 1024 → 2048 bits

About 8× more gates

About 1 billion× more work

The GNFS figure is Eric Lu's estimate from the RSA-260 write-up (PostQuantum). That asymmetry is the whole threat. Bigger keys, the classic defense, barely slow Shor down.

One honest caveat: nobody has proven factoring is classically hard. Shor's speedup is superpolynomial over the best known classical algorithm, not over every possible one. But decades of serious attempts give the bet a lot of weight.

Beyond RSA: one idea, three kills

The period-finding engine isn't specific to factoring. Shor's same paper broke the discrete logarithm problem, which is the foundation of everything RSA isn't.

Discrete log. Given g and h = gˣ (mod p), find x. Build a function of two inputs:

f(a, b) = gᵃ · h⁻ᵇ = g^(a − x·b) (mod p)

f repeats whenever a − x·b repeats, so its hidden period is the pair (x, 1). Run a two-register QFT and you measure pairs (k, l) with l ≡ −x·k (mod r), where r is the order of g. Solve for x. Diffie–Hellman, DSA and ElGamal are gone.

Elliptic curves. Swap integers mod p for points on a curve: given P and Q = k·P, find k. Same algorithm, different group. That takes out ECDSA, ECDH and Ed25519 — the signatures behind Bitcoin and Ethereum, and the classical key exchange inside TLS.

Elliptic curves are actually the softer target. Their keys are much shorter, so the circuit is smaller. In March 2026, researchers from Google Quantum AI, the Ethereum Foundation and Stanford estimated the 256-bit curve problem at about 1,200–1,450 logical qubits and under 500,000 physical qubits (The Quantum Insider).

The unifying frame. Factoring, discrete log and elliptic-curve log are all instances of the hidden subgroup problem over abelian (commutative) groups. The QFT solves that whole family efficiently. For non-abelian groups, no efficient quantum algorithm is known — and lattice problems connect to that harder side. That's a big part of why lattice-based schemes became the post-quantum bet.

What Shor doesn't touch. Symmetric crypto like AES and hashes like SHA-256. The best quantum attack there is Grover's search, a square-root speedup. Doubling the key length cancels it. AES-256 stays fine.

Reality check, October 2026

Here's the twist: Shor's algorithm has never honestly factored anything bigger than 21 on real quantum hardware. The threat lives in the resource estimates — and those keep falling.

What's actually been run.

• 2001: IBM factored 15 on a 7-qubit NMR machine. First demonstration ever.

• 2012: First run on a superconducting chip (UCSB), factoring 15. It got the right answer about half the time — exactly what theory predicts (R&D World).

• 2012: 21 factored on a photonic setup. Fourteen years later, still the record for a genuine Shor run (PostQuantum).

Watch out for bigger "records." Many demos used compiled circuits, simplified using the known answer. IBM researchers showed in 2013 that with enough of that shortcut you can "factor" any number with a coin flip. Quantum annealing and variational "factoring" results aren't Shor at all.

Meanwhile, a GPU supercomputer at Jülich simulated a full, honest Shor run on 549,755,813,701 = 712,321 × 771,781. The team challenged any real quantum device to beat it (arXiv).

What it would take for RSA-2048. The estimates have dropped 200× in seven years:

Date

Estimate by

Target

Physical qubits

Key assumptions

Mar 2026

Google Quantum AI, Ethereum Foundation, Stanford

256-bit elliptic curve

Under 500,000

1,200–1,450 logical qubits (TQI)

Feb 2026

Iceberg Quantum (Pinnacle)

RSA-2048

Under 100,000

QLDPC codes instead of surface codes; simulation only, not validated at scale (TQI)

May 2025

Craig Gidney (Google)

RSA-2048

Under 1 million, under a week

Same hardware assumptions as 2019; smarter arithmetic and error correction (arXiv)

2019

Gidney & Ekerå

RSA-2048

About 20 million, about 8 hours

0.1% gate error, 1 µs error-correction cycle

Note what drove the 2025 drop: algorithms, not hardware. Same assumed machine, 20× fewer qubits.

What exists. Google's Willow chip has 105 physical qubits. The best 2026 machines run dozens of error-corrected logical qubits — Quantinuum's Helios reports 48 (PostQuantum). A cryptographically relevant machine needs over a thousand logical qubits running billions of gates without failing.

The gap is still huge. But it's now measured in a few orders of magnitude, not in "maybe never."

The response: post-quantum cryptography

The fix isn't a bigger RSA key. It's replacing the math entirely with problems Shor's algorithm can't touch.

The new standards. In August 2024, NIST finalized three post-quantum standards:

• FIPS 203, ML-KEM (from Kyber) — key exchange, lattice-based.

• FIPS 204, ML-DSA (from Dilithium) — signatures, lattice-based.

• FIPS 205, SLH-DSA (from SPHINCS+) — signatures, hash-based, the conservative fallback.

In March 2025, NIST added HQC, a code-based backup in case lattices crack.

The deadlines. NIST's draft IR 8547 deprecates RSA and elliptic-curve crypto at today's common strength after 2030 and disallows it after 2035. The NSA's CNSA 2.0 wants new national security systems quantum-safe by January 2027 (TQI).

Why the rush, if the machine doesn't exist? Harvest now, decrypt later. Anyone can record encrypted traffic today and store it until a quantum computer can read it. Michele Mosca's rule of thumb frames it:

x + y > z → you're already late

Here x is how many years your data must stay secret, y is how long migration takes, and z is how long until a cryptographically relevant quantum computer exists. Medical records, state secrets and long-lived keys fail this test easily.

Who's moving. Cloudflare reported that most human-generated traffic on its network used post-quantum encryption by late 2025. Cloudflare and Google have both set 2029 targets for full post-quantum migration, and Apple's iMessage already runs a post-quantum protocol (TQI).

The catch: new math breaks too. SIKE, a NIST round-4 candidate, fell to a classical attack on a laptop in 2022. In July 2026, a key-recovery attack found with Anthropic's Claude Mythos Preview knocked HAWK out of NIST's extra signature round (PostQuantum). That's why most deployments run hybrids — classical plus post-quantum — and why crypto-agility matters as much as the algorithms.

The bottom line

Shor's algorithm turns factoring into period finding, and period finding into interference. That math has been settled since 1994.

What's unsettled is engineering: about a thousand-plus logical qubits running billions of gates for days without falling apart. Nobody has that machine. But the estimate of what it takes fell 20× in 2025 alone — and algorithms are improving faster than hardware.

The date that matters isn't Q-Day. It's 2030, when the migration is supposed to be done. Anything encrypted with RSA or elliptic curves before then should be assumed readable someday.