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.

Sinclair College - Dr. Mike Libassi

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. The example uses tiny numbers so you can check everything by hand.

PUBLIC KEY

N = 15, e = 3. Shared with anyone who wants to send you an encrypted message.

PRIVATE KEY

d = 11, since 3 × 11 = 33 = 4 × 8 + 1. Kept secret. This is what Shor's algorithm exposes.

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.

Periodicity — how often a repeating sequence cycles back to its starting value. Here, it's how many multiplications it takes before aˣ mod N returns to 1.

"mod N" means "the remainder after dividing by N." 17 mod 15 = 2, because 17 divided by 15 leaves a remainder of 2.

Greatest Common Divisor (GCD) — the largest number that divides evenly into two other numbers. 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 (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.

a =

03 · Inside the quantum step

What the quantum computer actually measures

The simulator above lists the sequence one term at a time, which is the slow classical way. The quantum computer instead puts an input register into superposition over every x at once, computes aˣ mod N into a second register, and then applies the quantum Fourier transform (QFT). Interference makes the measurement land on or near a multiple of Q/r, where Q is the size of the input register.

Quantum Fourier transform — the quantum version of the discrete Fourier transform, which picks out repeating frequencies in a signal. Applied to a periodic register, it concentrates the amplitude on outcomes spaced Q/r apart.

1/√Q Σ_x|x⟩|0⟩→1/√Q Σ_x|x⟩|aˣ mod N⟩→ QFT →peaks at k = j·Q/r

Try it: see the peaks, then sample one

Uses the a selected above, with a 4-qubit input register (Q = 16). A real attack uses a register around N² in size. Here r is 2 or 4, which divides 16, so the peaks are exact. That's a lucky special case: usually r doesn't divide Q, the peaks are smeared across neighboring values, and a classical step (continued fractions) recovers r from k/Q.

04 · 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 a^r/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, a^r/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 period finder in section 02.

Run the period finder above to populate this section.

05 · 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.

This demo: N = 15trivial, even by hand

Real-world RSA-2048: a 617-digit Nfar beyond today's hardware

2019 ESTIMATE (GIDNEY & EKERÅ)

~20M qubits

noisy physical qubits, about 8 hours

2025 ESTIMATE (GIDNEY)

< 1M qubits

noisy physical qubits, under a week

The estimate dropped about twentyfold in six years through better algorithms and error-correction techniques, not bigger hardware. 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. These figures are estimates that depend on assumed error rates and speeds, not demonstrations. Shor's algorithm threatens RSA only on a sufficiently large, fault-tolerant quantum computer; today's processors can't break RSA-2048. RSA is still safe for now, but the target keeps getting closer.

06 · 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).

Post-quantum cryptography — cryptography designed to run on today's ordinary (classical) computers, but built on problems believed to resist attack from quantum computers too, unlike factoring or discrete log.

In 2024, NIST finalized its first PQC standards, which are expected to gradually replace RSA and elliptic-curve cryptography across the internet. Page 09 goes deeper into how they work and how organizations migrate.

A different approach, QKD: instead of a new hard math problem, quantum key distribution protocols like BB84 use quantum mechanics itself for security. Measuring a quantum-encoded key disturbs it, so an eavesdropper shows up as extra errors, provided the protocol checks for them and runs over an authenticated channel. Page 07 has the hands-on simulation.