Non-graded · offline · explore at your own pace
Why a quantum computer can break RSA
RSA encryption relies on one thing being hard for a classical computer: factoring a very large number N into its two secret primes. Shor's algorithm gives a quantum computer a way to find those primes efficiently — not by guessing, but by finding a hidden repeating pattern in a sequence of numbers.
2¹, 2², 2³, 2⁴ … mod 15 — watch it repeat every 4 steps. That repeat length is the "period," and it's the key to everything below.
01 · Refresher
The RSA pieces Shor's algorithm attacks
Click a term to see how it fits together. This is the same vocabulary from your course notes.
02 · The core idea
Find the period, and the factors fall out
Shor's algorithm doesn't factor N directly. Instead, it picks a random number a and looks at the sequence a¹, a², a³, …, each one reduced mod N. Because there are only a limited number of possible remainders, this sequence always eventually repeats. The length of that repeat is called the period, written r. A quantum computer finds r efficiently using superposition and interference — a step that would take a classical computer an impractically long time for large N.
aˣ mod N returns to 1.17 mod 15 = 2, because 17 divided by 15 leaves a remainder of 2.gcd(12, 18) = 6. The Euclidean algorithm finds it quickly by repeated division.Try it: pick a starting number and watch the period appear
We'll keep N = 15 (the same example from your notes, factors 3 × 5) so you can check the math by hand. Not every choice of a works on the first try — that's part of the real algorithm too.
03 · From period to factors
Turning r into the actual primes
Once the period r is known, ordinary classical math finishes the job. If r is even, compute ar/2 mod N, then take the GCD of that value ±1 with N. Those two GCDs are usually the hidden prime factors.
Three things can send the algorithm back for another try. First, before any quantum work, check gcd(a, N): if it is bigger than 1, you have already found a factor. (The menu above only offers values of a that share no factor with 15, so that never happens here.) Second, r can be odd. Third, ar/2 can equal N − 1, which is −1 mod N; then the two GCDs come out as 1 and N, which tells you nothing. Try a = 14 to see this: its period is 2, but 14¹ = 14 ≡ −1 (mod 15). At least half of the possible choices of a avoid all three, so a few tries are usually enough.
Step-by-step factor extraction
This fills in automatically once you've run the simulator above.
04 · Why this actually matters
From N = 15 to a real RSA key
Factoring 15 is something you could do in your head. RSA in the real world uses numbers that are hundreds of digits long — and that gap in scale is the entire reason quantum computing is a cybersecurity concern rather than a party trick.
A widely cited 2019 estimate (Gidney & Ekerå) put the requirement to break a 2048-bit RSA key at roughly 20 million noisy physical qubits running for about 8 hours. A 2025 estimate (Gidney) lowered that to under a million noisy physical qubits running for under a week. Both are estimates that depend on assumed error rates and speeds, not demonstrations. Today's largest processors have on the order of a thousand physical qubits, and none yet run the error correction Shor's algorithm needs at scale. Shor's algorithm threatens RSA only on a sufficiently large, fault-tolerant quantum computer — which is why RSA is still considered safe for now, but not indefinitely.
05 · The defense
Fighting quantum with quantum-resistant math
If a large enough quantum computer eventually makes Shor's algorithm practical, the fix isn't to abandon math-based security — it's to stop relying on problems that quantum computers happen to be good at. That's the idea behind post-quantum cryptography (PQC): new algorithms built on math problems that stay hard even for a quantum computer.
In 2024, NIST finalized its first PQC standards, expected to gradually replace RSA and elliptic-curve cryptography across the internet over the next decade.