The Algorithm That Broke RSA: Shor's Factoring Algorithm Explained

In 1994, Peter Shor published an algorithm that solved, on a quantum computer, a problem that no classical computer can solve efficiently: factoring the product of two large prime numbers. The practical consequence, understood immediately by every cryptographer who read the paper, was that RSA — the encryption scheme protecting bank transactions, government communications, and essentially all authenticated traffic on the internet — was conditionally broken. Conditionally, because Shor’s algorithm requires a fault-tolerant quantum computer with millions of low-error qubits, and no such machine exists today. But the algorithm does not care about engineering constraints. It is correct, and the world has spent the last thirty years preparing for the day the hardware catches up.

Understanding Shor’s algorithm at depth reveals something surprising: the quantum speedup does not come from trying all possible factors at once. It comes from a specific mathematical reduction that transforms the factoring problem into a period-finding problem, and then from a quantum subroutine — the Quantum Fourier Transform — that finds periods exponentially faster than any classical method.

The Problem: Why Factoring Secures the Internet

RSA encryption was published in 1977 by Rivest, Shamir, and Adleman. Its security rests on a single mathematical asymmetry: multiplying two large prime numbers p and q together is trivially fast, but recovering p and q from their product N = p × q is — as far as anyone knows — computationally hard for large N.

To encrypt a message, the recipient publishes N (typically 2048 bits long for modern RSA) and a public exponent e. Anyone can encrypt by computing ciphertext = messageᵉ mod N. To decrypt, the recipient needs the private key d, which is computed from p and q. Without knowing p and q, computing d requires factoring N — and factoring a 2048-bit semiprime N takes more operations than the estimated number of atoms in the observable universe using the best classical algorithm (the General Number Field Sieve).

The security of RSA, ECC (elliptic curve cryptography), and Diffie-Hellman key exchange all reduce, in different ways, to the hardness of either integer factoring or the discrete logarithm problem. Shor’s algorithm solves both in polynomial time.

The Reduction: From Factoring to Period-Finding

Shor’s algorithm does not directly attempt to divide N by potential factors. Instead, it exploits a classical theorem from number theory to reduce factoring to a different problem.

Step 1 — Choose a random base. Pick a random integer $a$ with $1 < a < N$. Compute $\gcd(a, N)$. If $\gcd(a, N) > 1$, we got lucky — we found a non-trivial factor immediately (this happens rarely for large $N$). Otherwise, continue.

Step 2 — Find the order. Compute $r$, the smallest positive integer such that:

$$a^r \equiv 1 \pmod{N}$$

This $r$ is called the order of $a$ modulo $N$ (or the period, since the sequence $a^x \bmod N$ repeats with period $r$).

Step 3 — Extract factors. If $r$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$, then:

$$(a^{r/2} - 1)(a^{r/2} + 1) \equiv 0 \pmod{N}$$

Since neither factor is $\equiv 0 \bmod N$ (by assumption), they must share a factor with $N$. Computing $\gcd(a^{r/2} - 1, N)$ and $\gcd(a^{r/2} + 1, N)$ yields the prime factors $p$ and $q$.

The probability that a randomly chosen $a$ satisfies the conditions in Step 3 is at least $1/2$ for $N = pq$ with two distinct odd prime factors. In practice, two to three repetitions of the algorithm suffice to find the factors with high probability.

The entire classical number theory is efficient — every step except Step 2. Finding the order $r$ of $a \bmod N$ classically requires evaluating $a^x \bmod N$ for up to $r$ values of $x$, and $r$ can be as large as $N/4 \approx 2^{2046}$ for RSA-2048. This is exponential. This is the one step that a quantum computer does exponentially faster.

The Quantum Subroutine: Period-Finding via QFT

The quantum order-finding algorithm exploits the fact that the function $f(x) = a^x \bmod N$ is periodic — it repeats with period $r$. Finding the period of a periodic function is exactly what a Fourier transform does.

The Algorithm: Step by Step

Walking through each step:

① Initialisation. Prepare an $n$-qubit quantum register in the equal superposition of all $2^n$ computational basis states by applying a Hadamard gate to each qubit. For an $N$-bit number we choose $n = 2\lceil \log_2 N \rceil$ — roughly twice the bit-length of $N$ — to ensure sufficient resolution.

② Modular exponentiation. Apply the unitary $U$ that maps $|x\rangle|0\rangle \to |x\rangle|a^x \bmod N\rangle$. Because the input register is in superposition, this computes $a^x \bmod N$ for every $x$ from $0$ to $2^n - 1$ simultaneously — but not in a way that gives access to all values at once. The joint state is a quantum superposition that encodes all of them. This modular exponentiation circuit is the most expensive part of the algorithm, requiring $O(n^3)$ elementary quantum gates using efficient reversible arithmetic.

③ Collapse. Measure the ancilla (second) register. The outcome is some specific value $c = a^{x_0} \bmod N$. This projects the first register into a superposition of only those $x$ values where $a^x \bmod N = c$ — that is, $\{x_0, x_0+r, x_0+2r, \dots\}$. The register is now a periodic superposition with unknown period $r$ spaced at exact intervals.

④ Quantum Fourier Transform. Apply the QFT to the first register. The QFT maps a periodic superposition in position space to probability peaks in frequency space — exactly at the multiples of $2^n/r$. This is the quantum analogue of how a classical DFT of a periodic signal produces spikes at the signal’s harmonics.

⑤ Measurement. Measure the first register. The result is some integer $m$ close to $k \cdot (2^n/r)$ for a random integer $k$. This gives us an approximate rational representation of $k/r = m/2^n$.

⑥ Classical post-processing. Apply the continued fraction algorithm to $m/2^n$ to find the best rational approximations with denominator $\leq N$. One of these approximations equals $k/r$ exactly; its denominator is $r$ (or a divisor of $r$ — with small probability we may need to repeat). With $r$ in hand, compute $\gcd(a^{r/2}-1, N)$ and $\gcd(a^{r/2}+1, N)$. With probability $\geq 1/2$ over the random choice of $a$, these yield the prime factors $p$ and $q$.

Why the QFT Provides an Exponential Speedup

The Quantum Fourier Transform acts on an n-qubit state as:

$$\mathrm{QFT}\,|j\rangle = \frac{1}{\sqrt{2^n}} \sum_k e^{2\pi i j k / 2^n}\,|k\rangle$$

This is precisely the discrete Fourier transform of the basis vector amplitudes. The classical DFT on $2^n$ points requires $O(n \cdot 2^n)$ operations (with the FFT). The QFT implements it in $O(n^2)$ quantum gates — an exponential improvement.

The catch is that you cannot read out all 2ⁿ amplitudes of the QFT output, since measurement collapses the state to a single value. The power of the QFT in Shor’s algorithm lies not in reading all amplitudes, but in the fact that the measurement outcome is concentrated at the useful values — the multiples of 2ⁿ/r — because the QFT produces constructive interference there and destructive interference everywhere else. You don’t need all the information; you need one sample from a distribution that is almost entirely concentrated on the answer.

This is the precise sense in which quantum computers outperform classical computers on this problem: the QFT exploits quantum interference to make the answer overwhelmingly likely to be sampled after a single measurement, whereas a classical computer must scan through $O(r) \approx O(N)$ possibilities to find the period.

The Numbers: What Breaking RSA Actually Requires

What Has Actually Been Demonstrated

Every experimental demonstration of Shor’s algorithm to date has used special-purpose circuits that exploit prior knowledge of the answer to simplify the computation — rendering them proofs of principle rather than genuine demonstrations of the factoring task. The first demonstration, by IBM’s NMR group in 2001, factored N=15 into 3 × 5 using 7 qubits. Subsequent experiments factored 15 and 21 on photonic, superconducting, and ion trap platforms, always using highly optimised circuits that would not generalise to unknown factors.

No experiment has run a full, general-purpose instance of Shor’s algorithm on any number larger than 21. This is not a criticism of the demonstrations — they were validating quantum gate implementations — but it means the gap between current hardware and a cryptographically relevant quantum computer (CRQC) is enormous: from factoring 21 with 5 logical qubits to factoring RSA-2048 with ~4,000 logical qubits and ~2–4 million physical qubits, executing ~10¹¹ quantum gates at fault-tolerant fidelity.

Most credible estimates from government and academic sources place the first CRQC 10–20 years away, with significant uncertainty in both directions.

The Cryptographic Consequence: What the World Is Doing About It

The response to Shor’s algorithm has been one of the largest coordinated efforts in the history of cryptography. In 2016, NIST launched a competition to standardise post-quantum cryptographic (PQC) algorithms — schemes whose security does not depend on the hardness of factoring or discrete logarithms and therefore cannot be broken by Shor’s algorithm. In 2024, after eight years of evaluation, NIST finalised three standards:

• ML-KEM (Module Lattice Key Encapsulation Mechanism, formerly CRYSTALS-Kyber): for key exchange, based on the hardness of the Learning With Errors (LWE) problem on lattices.
• ML-DSA (Module Lattice Digital Signature Algorithm, formerly CRYSTALS-Dilithium): for digital signatures, same lattice hardness.
• SLH-DSA (Stateless Hash-Based Digital Signature Algorithm, formerly SPHINCS+): for signatures, based only on the security of hash functions.

These algorithms are believed to be secure against both classical and quantum computers, including Shor’s algorithm (which does not apply to lattice or hash-based problems).

The migration is urgent because of “harvest now, decrypt later” (HNDL) attacks: an adversary with sufficient storage can collect encrypted traffic today and decrypt it retroactively once a sufficiently large quantum computer becomes available. Traffic encrypted with RSA in 2025 may be decrypted in 2035 or 2040 — a particular concern for government, intelligence, and financial data with long-term sensitivity. The National Security Agency, CISA, and equivalent agencies in the UK, EU, and Canada have all issued guidance directing a migration to PQC algorithms on specific timelines.

Shor’s algorithm is not a current threat. It is a future threat that must be mitigated now, because the data being encrypted today will still be sensitive when the hardware eventually arrives. That calculation is why a theoretical result from 1994 continues to drive operational security decisions at every major technology company and government agency three decades later.

The Enduring Significance

Shor’s algorithm matters beyond its cryptographic implications. It was the first evidence that quantum computers offer an exponential speedup on a practically important problem — not a contrived mathematical exercise, but the specific computational problem that underpins global financial security. It established that quantum advantage is not merely theoretical. And it forced the classical cryptography community to confront a deadline: the window between “a sufficiently large quantum computer does not exist” and “it does” may be the most consequential engineering transition of the 21st century.

The algorithm itself is a beautiful piece of mathematics: a reduction from number theory to signal processing, from an algebraic group structure to quantum interference, from classical GCDs to quantum measurement. Its key steps — the Fourier transform of a periodic function, the extraction of a period from a single sample — could in principle be explained to anyone who has taken a signal processing course. What is quantum about it is not mysterious; it is precise.

Understanding Shor’s algorithm is not optional for anyone who wants to understand why quantum computing matters, what fault-tolerant hardware must achieve, or why the internet’s cryptographic infrastructure is currently being replaced. It is the reason the field exists in its current form.

Sources & Further Reading

1. Peter W. Shor. Algorithms for Quantum Computation: Discrete Logarithms and Factoring. Proc. 35th Annual Symposium on Foundations of Computer Science (FOCS) (1994)
2. Peter W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, 26(5); arXiv:quant-ph/9508027 (1997)
3. Stéphane Beauregard. Circuit for Shor’s algorithm using 2n+3 qubits. Quantum Information and Computation; arXiv:quant-ph/0205095 (2003)
4. Craig Gidney, Martin Ekerå. How to Factor 2048-bit RSA Integers in 8 Hours Using 20 Million Noisy Qubits. Quantum 5, 433; arXiv:1905.09749 (2021)
5. NIST. Module-Lattice-Based Key-Encapsulation Mechanism Standard (FIPS 203). Federal Information Processing Standards Publication 203 (2024)

Discussion

← All articles