The first article in this series claimed that a quantum computer running Shor's algorithm would break RSA. The second showed you how to find RSA in the wild. This one shows you exactly how the break works, no hand-waving, no "quantum tries all answers at once." By the end you will be able to trace the full attack: from a public key, through period-finding and quantum interference, to the private key.
The short version
Shorʼs algorithm and RSA were first introduced in their respective articles. While the second article elaborated on the essence of RSA, this article describes the breaking mechanism of RSA without the need of vague descriptions or magical phenomena, where quantum computers “try all the possible answers at the same time.” After studying this article, you will be able to comprehend and outline the entire process of the attack from the quantum public key to the quantum private key achieved through interference and period finding.
The concise description
Shor’s algorithm does not employ the mechanism of “guessing the keys at an incredible speed.” What is done is far more precise, as it converts the RSA resting on the hard problem of factoring, which is, more or less, impossible to solve, into period finding, which, as a matter of fact, quantum computers do in an astonishing manner. Everything else in the process of breaking RSA is simple mathematics and does not require a quantum computer to be performed.
The anatomy of “breaking RSA”
As a quick reminder, the public RSA key is constructed of n and e, where n is the product of the two secret prime numbers p and q. The equation defining the private key exponent d is as follows:
e · d ≡ 1 (mod φ(n)), where φ(n) = (p − 1)(q − 1)
Once an attacker discovers the values of the secret primes p and q, φ(n) can be computed, and subsequently, d can also be calculated. Therefore, breaking RSA is completely equivalent to factoring n. Shor’s attack targets this particular problem.
Step 1. Convert factoring into period finding (classical phase of the attack)
Here is the pivot that makes the whole algorithm possible, and it involves no quantum anything. Pick any random number a less than n that shares no factor with n. Now look at this sequence:
a¹, a², a³, a⁴, … (mod n)
Because we are working mod n, this sequence must eventually repeat. The period r is the smallest positive exponent where:
aʳ ≡ 1 (mod n)
Once you know r, and if r is even, you can compute:
gcd(a^(r/2) − 1, n) and gcd(a^(r/2) + 1, n)
and — with good probability — those two gcd computations hand you p and q. That is not obvious, so let me show it on a real (tiny) number.
Worked example: factoring 15
Let n = 15, pick a = 7. Compute powers mod 15:
7¹ = 7
7² = 49 ≡ 4
7³ = 343 ≡ 13
7⁴ = 2401 ≡ 1 ← back to 1
The period is r = 4. It is even, so compute a^(r/2) = 7² = 49 ≡ 4 (mod 15). Then:
gcd(4 − 1, 15) = gcd(3, 15) = 3
gcd(4 + 1, 15) = gcd(5, 15) = 5
And 3 × 5 = 15. We just factored n by finding a period. No factoring algorithm was used, only "how long until this sequence loops?"
What you just learned: factoring is secretly a question about the period of a repeating sequence. The entire difficulty of RSA has been re-expressed as "find r." A classical computer finds r by grinding through the powers one at a time, hopeless when r is astronomically large (as it is for a 2048-bit n). This is where the quantum machine enters.
Step 2: Why a classical computer can't find r and a quantum one can
For a real RSA modulus, the period r can be on the order of n itself, a number hundreds of digits long. You cannot list that many powers before the heat death of the sun. So the problem is not "compute a period," it's "find the period of a function without evaluating it a catastrophic number of times."
A quantum computer sidesteps this using the machinery — amplitudes, superposition, and interference. Here is the honest mechanism, in four moves.
Move 1: Prepare every input at once (superposition)
Load a register of qubits into an equal superposition of all integers x from 0 up to some large Q. Using the amplitude language from before, the state is a sum over every x with equal amplitude:
(1/√Q) · Σ |x⟩
This is not magic "parallel universes." It is one arrow in a very high-dimensional space that happens to lean equally toward every basis direction |x⟩.
Move 2: Compute the sequence into a second register
Apply the function f(x) = aˣ mod n to a second register. The registers are now entangled: each input x is paired with its output aˣ mod n. Crucially, we never read this yet.
Move 3: The heart — the Quantum Fourier Transform
Now measure the output register. Because f is periodic with period r, many different inputs x produce the same output. The input register collapses to a superposition of only those x-values that map to the measured output and those surviving values are spaced exactly r apart:
|x₀⟩ + |x₀ + r⟩ + |x₀ + 2r⟩ + |x₀ + 3r⟩ + …
We now have a superposition whose structure is the period but we can't read it directly, because that random offset x₀ scrambles the answer. This is where the Quantum Fourier Transform (QFT) does the decisive work.
The QFT is an interference machine. It rotates the state so that amplitudes reinforce (crest meets crest) only at values related to Q/r, and cancel (crest meets trough) everywhere else, exactly the constructive/destructive interference, applied on purpose. The offset x₀ only affects phases that wash out. When you now measure, you get, with high probability, an integer close to a multiple of Q/r.
Move 4: Extract r classically
From that measured value c ≈ k·(Q/r), a classical technique called continued fractions recovers r. Then you're back in Step 1's worked example: even r → two gcds → the factors. Verify p × q = n on a normal computer. Done.
What you just learned: the quantum computer's only job is Move 3 — using interference to read off a period that is invisible to classical machines. Superposition sets up the interference; the QFT performs it; everything before and after is textbook number theory. "Quantum breaks RSA" precisely means "the QFT finds the period."
Step 3: Walking the full attack chain
Put the whole series together. Here is the complete path from public data to private key:
public n → [quantum: period-finding via QFT] → r
r → gcd(a^(r/2) ± 1, n) → p, q
p, q → φ(n) = (p−1)(q−1) → φ(n)
φ(n), e → solve e·d ≡ 1 (mod φ(n)) → d (the private key)
Notice something important: only the first arrow is quantum. The attacker literally re-runs RSA's own key-generation procedure in reverse. This is why the threat is so total, it doesn't exploit a bug or a weak implementation; it dissolves the foundational assumption itself.
How hard is this in practice?
If it's just one quantum step, why isn't RSA already dead? Because that one step is brutally demanding on real hardware.
Factoring a 2048-bit RSA key needs roughly 4000+ logical qubits running a coherent computation involving on the order of billions of gates.
A logical qubit is not a physical qubit. Today's physical qubits are noisy; you need quantum error correction, which may cost 1000 or more physical qubits per logical qubit. That pushes real estimates into the millions of physical qubits.
The computation must stay coherent, interference is fragile; a stray interaction with the environment (decoherence) collapses the delicate amplitude pattern before the QFT can finish.
Current devices have on the order of hundreds to low-thousands of physical, noisy qubits with no full error correction. That's the gap. Most public estimates put a cryptographically relevant machine a decade or more out which is exactly the reasoning behind "Harvest Now, Decrypt Later" from the first article. The machine isn't here, but the math is certain, so the migration starts now.
Grover, briefly — why symmetric survives
The first article promised symmetric encryption mostly survives. Now you can see why in one line: Grover's algorithm searches an unstructured space of N keys in about √N steps instead of N. That turns AES-128's 2¹²⁸ effort into ~2⁶⁴ — uncomfortable — but AES-256 into ~2¹²⁸, which remains infeasible. Double the key, restore the margin. There is no period to exploit in AES, so Shor simply does not apply; the best quantum attack is the far weaker Grover speedup.
Key takeaways
Shor doesn't brute-force keys. It reduces factoring to period-finding, a problem quantum interference solves efficiently.
The reduction (Step 1) and the extraction (continued fractions, gcd) are classical. The only quantum part is the QFT finding the period.
Once you have the period → the factors → φ(n) → the private key d. The attacker runs key generation in reverse.
The obstacle is error-corrected scale: thousands of logical qubits, likely millions of physical ones, held coherent. That's the runway we're migrating across.
Top comments (0)