Chapter 11: Shor's Algorithm

In 1994, mathematician Peter Shor showed that a quantum computer could factor large integers in polynomial time - an exponential speedup over the best known classical methods. This single result transformed quantum computing from a theoretical curiosity into a looming threat to the cryptographic infrastructure that secures the modern internet. In this chapter we will build Shor's algorithm from the ground up, starting with the factoring problem itself, working through the elegant reduction to period finding, and assembling the full quantum circuit. We will run small examples on a simulator and conclude by examining the far-reaching implications for cryptography and the ongoing transition to post-quantum standards.

This chapter builds directly on Chapter 10, where we developed the Quantum Fourier Transform (QFT) and quantum phase estimation (QPE). Shor's algorithm is, at its core, an application of QPE to the problem of finding the period of a modular exponentiation function. It also connects to Chapter 8, where we introduced the RSA cryptosystem and its dependence on the presumed difficulty of factoring.

11.1 The Factoring Problem and Its Importance

The integer factorization problem is deceptively simple to state: given a composite integer $N$, find two non-trivial factors $p$ and $q$ such that $N = p \times q$. For small numbers this is trivial - you can see that $15 = 3 \times 5$ at a glance. But as numbers grow to hundreds or thousands of digits, the problem becomes extraordinarily difficult for classical computers.

Why Factoring Is Believed to Be Hard

Multiplication is easy: given two 1000-digit primes $p$ and $q$, any laptop can compute their product $N = pq$ in a fraction of a second. Factoring is the reverse operation, and it appears to be fundamentally harder. This asymmetry - easy to multiply, hard to factor - is an example of a one-way function, and it is the cornerstone of modern public-key cryptography.

The best known classical factoring algorithm is the general number field sieve (GNFS), which runs in time:

$$O\!\left(\exp\!\left(c \cdot n^{1/3} (\log n)^{2/3}\right)\right)$$

where $n$ is the number of bits in $N$ and $c \approx 1.9$. This is sub-exponential but still super-polynomial - it grows faster than any polynomial but slower than a full exponential like $2^n$. For concreteness: factoring a 2048-bit RSA modulus with the GNFS on current classical hardware would take longer than the age of the universe.

Note.

Factoring occupies a curious place in computational complexity. It is in NP (given candidate factors, verification is a single multiplication) and also in co-NP (you can prove a number is prime). But it is not known to be NP-complete, so it may be easier than the hardest NP problems. This intermediate status is precisely what makes quantum speedup possible - Shor's algorithm does not solve NP-complete problems efficiently, but it does exploit the special algebraic structure of factoring.

RSA Depends on Factoring Being Hard

The RSA cryptosystem, introduced by Rivest, Shamir, and Adleman in 1977, works as follows. A user generates two large primes $p$ and $q$, computes $N = pq$, and publishes $N$ as part of their public key. Anyone can encrypt a message using $N$, but decryption requires knowing the prime factors $p$ and $q$. The security of RSA therefore rests on the assumption that factoring $N$ is computationally infeasible when $p$ and $q$ are large enough (typically 1024 bits each, making $N$ a 2048-bit number).

Today, RSA and closely related schemes protect banking transactions, secure web browsing (TLS), email encryption (PGP), software updates, and much more. If factoring became easy, all of these systems would be broken. Shor's algorithm makes factoring easy - for a sufficiently powerful quantum computer.

The Factoring Landscape

Algorithm	Type	Complexity
Trial division	Classical	$O(\sqrt{N})$ - exponential in $n$
Pollard's rho	Classical	$O(N^{1/4})$ - exponential in $n$
Quadratic sieve	Classical	$O(\exp(c \cdot \sqrt{n \log n}))$
General number field sieve	Classical	$O(\exp(c \cdot n^{1/3}(\log n)^{2/3}))$
Shor's algorithm	Quantum	$O(n^3)$ - polynomial

The jump from sub-exponential to polynomial is dramatic. For a 2048-bit number, the GNFS requires on the order of $2^{112}$ operations. Shor's algorithm requires roughly $2048^3 \approx 8.6 \times 10^9$ quantum gate operations - a number that is large but entirely feasible for a fault-tolerant quantum computer.

11.2 From Factoring to Period Finding

The key insight of Shor's algorithm is that factoring can be reduced to a different problem - order finding (also called period finding) - which a quantum computer can solve efficiently. This section develops that reduction step by step.

Modular Arithmetic Review

We write $a \equiv b \pmod{N}$ to mean that $N$ divides $(a - b)$. Equivalently, $a$ and $b$ have the same remainder when divided by $N$. For example:

$17 \equiv 2 \pmod{5}$ because $17 - 2 = 15$ is divisible by 5
$7^2 = 49 \equiv 4 \pmod{15}$ because $49 - 4 = 45$ is divisible by 15

The function $f(x) = a^x \bmod N$ is central to Shor's algorithm. It is computed by repeated squaring: to compute $a^x \bmod N$, we express $x$ in binary and repeatedly square and reduce modulo $N$, requiring only $O(\log x)$ multiplications.

The Order of an Integer

Given an integer $a$ with $1 < a < N$ and $\gcd(a, N) = 1$ (that is, $a$ and $N$ share no common factors), the order of $a$ modulo $N$ is the smallest positive integer $r$ such that:

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

For example, consider $a = 7$ and $N = 15$:

$7^1 \bmod 15 = 7$
$7^2 \bmod 15 = 49 \bmod 15 = 4$
$7^3 \bmod 15 = 7 \cdot 4 \bmod 15 = 28 \bmod 15 = 13$
$7^4 \bmod 15 = 7 \cdot 13 \bmod 15 = 91 \bmod 15 = 1$

So the order of 7 modulo 15 is $r = 4$. Notice the sequence repeats with period $r$: the function $f(x) = 7^x \bmod 15$ cycles through $7, 4, 13, 1, 7, 4, 13, 1, \ldots$

The Reduction: Order Finding Gives Factors

Here is the central theorem that makes Shor's algorithm work:

Key Concept - The Factoring Reduction.

Suppose we know the order $r$ of a randomly chosen $a$ modulo $N$. If $r$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$, then at least one of the following is a non-trivial factor of $N$:

$$\gcd(a^{r/2} - 1,\; N) \quad \text{or} \quad \gcd(a^{r/2} + 1,\; N)$$

Why does this work? Since $a^r \equiv 1 \pmod{N}$, we can write:

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

If $r$ is even, this factors as:

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

This means $N$ divides the product $(a^{r/2} - 1)(a^{r/2} + 1)$. If neither factor is divisible by $N$ itself (which is guaranteed when $a^{r/2} \not\equiv \pm 1 \pmod{N}$), then $N$ must share a non-trivial common factor with at least one of them. The Euclidean algorithm computes $\gcd$ in $O(n^2)$ time, so extracting the factors is classically efficient.

Worked Example: Factoring 15

Let us factor $N = 15$ using this reduction. Choose $a = 7$ (we already know the choice must satisfy $\gcd(a, N) = 1$; since $\gcd(7, 15) = 1$, this is valid).

Find the order: $r = 4$ (as computed above, since $7^4 \equiv 1 \pmod{15}$).
Check: $r = 4$ is even. Good.
Compute $a^{r/2} = 7^2 = 49 \equiv 4 \pmod{15}$. Since $4 \not\equiv -1 \pmod{15}$, we can proceed.
Compute the GCDs:
- $\gcd(a^{r/2} - 1, N) = \gcd(48, 15) = \gcd(3, 15) = 3$
- $\gcd(a^{r/2} + 1, N) = \gcd(50, 15) = \gcd(5, 15) = 5$
We have found the factors: $15 = 3 \times 5$.

Success Probability

Not every choice of $a$ works. The reduction can fail in two ways: $r$ might be odd, or $a^{r/2} \equiv -1 \pmod{N}$. However, a theorem from number theory guarantees that for a randomly chosen $a$, the probability that the reduction succeeds is at least $1 - 1/2^{k-1}$, where $k$ is the number of distinct prime factors of $N$. For $N = pq$ (the RSA case, $k = 2$), this gives a success probability of at least $1/2$. After a few random choices of $a$, the probability of not yet having found a factor becomes negligibly small.

The Complete Classical-Quantum Split

Shor's algorithm neatly separates into classical and quantum parts:

Classical preprocessing: Pick a random $a$, check $\gcd(a, N) = 1$.
Quantum subroutine: Find the order $r$ of $a$ modulo $N$.
Classical postprocessing: If $r$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$, compute $\gcd(a^{r/2} \pm 1, N)$. Otherwise, pick a new $a$ and repeat.

The quantum speedup comes entirely from step 2. Everything else is classical and efficient. The next section shows how a quantum computer finds $r$.

Interactive: Modular Exponentiation Explorer

11.3 Quantum Period Finding with the QFT

The order-finding problem asks us to determine the smallest $r$ such that $a^r \equiv 1 \pmod{N}$. The function $f(x) = a^x \bmod N$ is periodic with period $r$, and a quantum computer can extract this period using the quantum Fourier transform. The technique is a direct application of quantum phase estimation from Chapter 10.

The Quantum Circuit

The quantum order-finding circuit uses two registers:

Top register (counting register): $t$ qubits, where $t \approx 2n$ for an $n$-bit number $N$. This register is where we will read out information about the period.
Bottom register (work register): $n$ qubits, initialized to $|1\rangle$ (the value 1 in binary). This register holds the values of $a^x \bmod N$.

The circuit has four stages:

Prepare uniform superposition. Apply Hadamard gates to all $t$ qubits in the top register, creating: $$\frac{1}{\sqrt{2^t}} \sum_{x=0}^{2^t - 1} |x\rangle |1\rangle$$
Apply controlled modular exponentiation. For each qubit $j$ in the top register (from most significant to least), apply a controlled operation that multiplies the bottom register by $a^{2^j} \bmod N$, conditioned on qubit $j$ being $|1\rangle$. This transforms the state to: $$\frac{1}{\sqrt{2^t}} \sum_{x=0}^{2^t - 1} |x\rangle |a^x \bmod N\rangle$$
Apply the inverse QFT to the top register. The QFT extracts the frequency information - that is, the period - from the superposition.
Measure the top register. The result is a value $y$ that is close to a multiple of $2^t / r$.

Why the QFT Reveals the Period

After stage 2, the top and bottom registers are entangled. If we were to measure the bottom register and obtained some value $f_0 = a^{x_0} \bmod N$, the top register would collapse to a superposition of all $x$ values that map to $f_0$:

$$|x_0\rangle + |x_0 + r\rangle + |x_0 + 2r\rangle + \cdots$$

This is a state with a periodic structure - the non-zero amplitudes are evenly spaced with spacing $r$. When we apply the inverse QFT to a periodic state with period $r$, the result is a state concentrated on multiples of $2^t / r$. Specifically, measuring the top register yields a value $y$ that satisfies:

$$y \approx k \cdot \frac{2^t}{r} \quad \text{for some integer } k \in \{0, 1, \ldots, r-1\}$$

The key fact is that we do not need to measure the bottom register first. Because the QFT operates only on the top register, the analysis works out the same whether or not we measure the bottom register. The interference pattern produced by the QFT ensures that the measurement outcome $y$ carries information about $r$.

Extracting the Period with Continued Fractions

After measuring $y$ from the top register, we have the ratio $y / 2^t$, which is close to some fraction $k/r$. To extract $r$, we use the continued fractions algorithm.

A continued fraction expansion of a real number $\alpha$ has the form:

$$\alpha = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cdots}}}$$

We write this compactly as $[a_0; a_1, a_2, a_3, \ldots]$. The convergents are the rational approximations obtained by truncating the expansion: $a_0$, $a_0 + 1/a_1$, $a_0 + 1/(a_1 + 1/a_2)$, and so on.

Key Concept - Continued Fractions in Shor's Algorithm.

Given the measured value $y$ and the known value $2^t$, compute the continued fraction expansion of $y / 2^t$. The convergent whose denominator is less than $N$ and best approximates $y / 2^t$ gives a candidate for $k/r$. The denominator of this convergent is our candidate for the period $r$ (or a divisor of $r$).

Worked Example: Continued Fractions for Factoring 15

Suppose we are factoring $N = 15$ with $a = 7$, using $t = 8$ qubits in the top register (so $2^t = 256$). The true period is $r = 4$, so the QFT peaks occur near multiples of $256 / 4 = 64$. Suppose we measure $y = 192$.

We compute the continued fraction expansion of $192/256 = 3/4$:

$$\frac{192}{256} = \frac{3}{4} = 0 + \cfrac{1}{1 + \cfrac{1}{3}} = [0; 1, 3]$$

The convergents are:

$[0] = 0/1$
$[0; 1] = 1/1$
$[0; 1, 3] = 3/4$

The last convergent with denominator less than $N = 15$ is $3/4$. The denominator is $4$, which is our candidate for $r$. We check: $7^4 \bmod 15 = 2401 \bmod 15 = 1$. Indeed, $r = 4$.

What if we had measured $y = 64$ instead? Then $64/256 = 1/4 = [0; 4]$, and the convergent gives denominator $4$ directly. If we measured $y = 128$, then $128/256 = 1/2 = [0; 2]$, giving denominator $2$. Since $2$ divides the true period $4$, we would check $r = 2$: $7^2 \bmod 15 = 4 \neq 1$, so $r = 2$ fails and we know the true period must be a multiple of $2$. We could try $r = 4$ next, or simply re-run the quantum circuit.

Simulation: QFT Peak Pattern

Adjust the phase parameter to see how the inverse QFT creates measurement peaks. When the phase corresponds to a rational fraction $k/r$, sharp peaks appear at multiples of $2^t/r$.

Phase (phi): 0.25

Sandbox: Period Finding for $a = 7, N = 15$

The sandbox below demonstrates the quantum part of period finding for factoring 15 with $a = 7$. We use a simplified 4-qubit counting register and implement the controlled modular multiplications as custom gates. The QFT is applied via controlled phase rotations and swaps. Run the circuit and observe that the measurement outcomes cluster near multiples of $16/4 = 4$ (that is, near $0$, $4$, $8$, and $12$ in the 4-bit counting register).

You should see four peaks in the histogram, corresponding to the values $0000$, $0100$, $1000$, and $1100$ (that is, $0$, $4$, $8$, and $12$ in decimal). These are the multiples of $2^4 / r = 16/4 = 4$. Each of these outcomes, when processed through the continued fractions algorithm, yields $r = 4$ (except for $y = 0$, which is uninformative).

Simulation: QFT Peaks Reveal the Period

The simulation below lets you explore how the inverse QFT creates peaks at multiples of $2^t / r$. Use the slider to set a phase value $\varphi$. The circuit prepares a state where the phase encodes information about the period, and the inverse QFT converts this into a measurement pattern. When $\varphi = k/r$ for integer $k$ and $r$, the peaks are sharp and well-defined. Try $\varphi = 0.25$ (corresponding to $r = 4$, $k = 1$), $\varphi = 0.50$ ($r = 2$), and $\varphi = 0.75$ ($r = 4$, $k = 3$) to see how different periods produce different peak patterns.

11.4 Putting It All Together: Shor's Complete Algorithm

We now have all the pieces. Let us assemble the complete algorithm and walk through the full process of factoring $N = 15$.

The Algorithm, Step by Step

Shor's Factoring Algorithm.

Given a composite integer $N$ to factor:

If $N$ is even, return the factor $2$.
Check if $N = a^b$ for some integers $a \geq 2$, $b \geq 2$. If so, return $a$. (This can be done classically in $O(n^3)$ time.)
Choose a random integer $a$ with $2 \leq a \leq N - 1$.
Compute $d = \gcd(a, N)$. If $d > 1$, return $d$ (we got lucky).
[Quantum] Use the quantum order-finding subroutine to find the order $r$ of $a$ modulo $N$.
If $r$ is odd, go to step 3.
If $a^{r/2} \equiv -1 \pmod{N}$, go to step 3.
Compute $\gcd(a^{r/2} - 1, N)$ and $\gcd(a^{r/2} + 1, N)$. At least one of these is a non-trivial factor of $N$. Return it.

End-to-End Walkthrough: Factoring 15

Let us trace through the algorithm with $N = 15$:

Step 1: $N = 15$ is odd - no free factor of 2.

Step 2: $15$ is not a perfect power ($\sqrt{15} \approx 3.87$, $15^{1/3} \approx 2.47$ - neither is an integer).

Step 3: Choose $a = 7$.

Step 4: $\gcd(7, 15) = 1$, so no free factor.

Step 5 (Quantum): Run the quantum order-finding circuit. We prepare the superposition over the counting register, apply the controlled modular exponentiation by $a = 7$, apply the inverse QFT, and measure. Suppose we measure $y = 192$ from an 8-bit counting register ($2^t = 256$).

Classical post-processing: Compute the continued fraction expansion of $192/256 = 3/4$. The convergent with the largest denominator less than $N = 15$ has denominator $r = 4$.

Step 6: $r = 4$ is even. Good.

Step 7: $7^{4/2} = 7^2 = 49 \equiv 4 \pmod{15}$, and $4 \neq -1 \equiv 14 \pmod{15}$. Good.

Step 8: Compute:

$\gcd(7^2 - 1, 15) = \gcd(48, 15) = 3$
$\gcd(7^2 + 1, 15) = \gcd(50, 15) = 5$

The factors of 15 are 3 and 5.

Complexity Analysis

For factoring an $n$-bit number $N$, the quantum order-finding circuit requires:

Qubits: $O(n)$ qubits - approximately $2n$ for the counting register and $n$ for the work register, plus ancilla qubits for the modular arithmetic.
Controlled modular exponentiation: This is the most expensive part. Each controlled multiplication modulo $N$ requires $O(n^2)$ elementary gates (using schoolbook multiplication), and we need $O(n)$ such multiplications - one for each bit of the counting register. Total: $O(n^3)$ gates.
Inverse QFT: $O(n^2)$ gates (as we saw in Chapter 10), which is dominated by the modular exponentiation cost.
Classical post-processing: The continued fractions algorithm and GCD computation each run in $O(n^2)$ time.

The overall gate complexity is $O(n^3)$, which is polynomial in the number of bits. This is an exponential improvement over the best classical algorithm.

Comparison with Classical Algorithms

Bits ($n$)	GNFS (classical)	Shor (quantum)
512	$\sim 2^{63}$ operations	$\sim 1.3 \times 10^8$ gates
1024	$\sim 2^{86}$ operations	$\sim 1.1 \times 10^9$ gates
2048	$\sim 2^{112}$ operations	$\sim 8.6 \times 10^9$ gates
4096	$\sim 2^{142}$ operations	$\sim 6.9 \times 10^{10}$ gates

At 2048 bits, the classical cost is astronomically beyond reach, while the quantum cost is within the capability of a future fault-tolerant quantum computer with thousands of logical qubits.

11.5 Predict, Observe, Explain: Measurement After the QFT

Before running the QFT in the period-finding circuit, predict what the measurement histogram will look like. How many peaks will there be, and where?

Predict

Observe

Explain

Predict

For $a = 7$ and $N = 15$, the period is $r = 4$. With a 4-qubit counting register ($2^t = 16$), where should the QFT measurement peaks appear? How many distinct peaks do you expect?

Observe

Run the QPE circuit and observe the histogram peaks:

OPENQASM 3.0;
qubit[5] q; bit[4] c;
x q[4];
h q[0]; h q[1]; h q[2]; h q[3];
swap q[0], q[3]; swap q[1], q[2];
h q[0]; cp(-pi/2) q[1], q[0]; cp(-pi/4) q[2], q[0]; cp(-pi/8) q[3], q[0];
h q[1]; cp(-pi/2) q[2], q[1]; cp(-pi/4) q[3], q[1];
h q[2]; cp(-pi/2) q[3], q[2]; h q[3];
c[0] = measure q[0]; c[1] = measure q[1]; c[2] = measure q[2]; c[3] = measure q[3];

Explain

The peaks appear at multiples of $2^t / r = 16/4 = 4$, giving outcomes $\{0, 4, 8, 12\}$ - exactly $r = 4$ evenly spaced peaks. Each peak has probability $\approx 1/4$. The spacing between peaks (4 in this case) reveals the period: $r = 2^t / \text{spacing} = 16/4 = 4$. The continued fractions algorithm formalizes this extraction for non-integer cases.

11.6 Running Shor's Algorithm on a Simulator

Let us now implement and run Shor's algorithm for the simplest non-trivial case: factoring $N = 15$. Even this "easy" example reveals the structure and subtlety of the algorithm.

The Modular Exponentiation Oracle

The most complex part of Shor's circuit is the controlled modular exponentiation. For general $N$, this requires a full modular multiplier circuit, which is built from modular adders, comparators, and controlled swaps. For the specific case of $N = 15$, the small size allows us to construct optimized oracles for each value of $a$.

For $a = 7$ and $N = 15$, the controlled modular multiplications are:

Controlled multiply by $7^1 \bmod 15 = 7$: The permutation $|x\rangle \to |7x \bmod 15\rangle$ on the 4-bit work register can be decomposed into a sequence of controlled swaps and NOT gates.
Controlled multiply by $7^2 \bmod 15 = 4$: Similarly decomposed.
Controlled multiply by $7^4 \bmod 15 = 1$: This is the identity - no gates needed.
Controlled multiply by $7^8 \bmod 15 = 1$: Also the identity.

Note.

For the case $N = 15$, many of the controlled multiplications reduce to the identity because $7^4 \equiv 1 \pmod{15}$. This is a coincidence of the small example size. For larger $N$, every controlled multiplication would be a non-trivial circuit requiring $O(n^2)$ gates.

Sandbox: Factor 15 with $a = 7$

The circuit below implements the full quantum order-finding subroutine for $a = 7$, $N = 15$. Run it multiple times and record the outcomes. Each non-zero outcome from the counting register can be processed through the continued fractions algorithm to yield the period $r = 4$, and from there the factors $3$ and $5$.

OPENQASM 3.0;
qubit[8] q; bit[4] c;
// Shor's algorithm: a=7, N=15
// Counting register: q[0..3], Work register: q[4..7]
// Initialize work register to |1>
x q[7];
// Hadamards on counting register
h q[0]; h q[1]; h q[2]; h q[3];
// Controlled modular multiplications (optimized for N=15)
// Controlled multiply by 7^8 mod 15 = 1: identity
// Controlled multiply by 7^4 mod 15 = 1: identity
// Controlled multiply by 7^2 mod 15 = 4
ctrl @ swap q[2], q[5], q[7];
ctrl @ swap q[2], q[6], q[5];
// Controlled multiply by 7^1 mod 15 = 7
ctrl @ swap q[3], q[5], q[7];
ctrl @ swap q[3], q[6], q[5];
ctrl @ x q[3], q[4]; ctrl @ x q[3], q[5]; ctrl @ x q[3], q[6]; ctrl @ x q[3], q[7];
// Inverse QFT on counting register
swap q[0], q[3]; swap q[1], q[2];
h q[0]; cp(-pi/2) q[1], q[0]; cp(-pi/4) q[2], q[0]; cp(-pi/8) q[3], q[0];
h q[1]; cp(-pi/2) q[2], q[1]; cp(-pi/4) q[3], q[1];
h q[2]; cp(-pi/2) q[3], q[2]; h q[3];
c[0] = measure q[0]; c[1] = measure q[1]; c[2] = measure q[2]; c[3] = measure q[3];

Interpreting the Results

After running the circuit, you should see four outcomes with roughly equal probability. Here is how each measurement maps to the period:

Measured bits	Decimal $y$	$y/2^t$	Continued fraction	Candidate $r$
$0000$	$0$	$0/16 = 0$	$[0] = 0/1$	Uninformative
$0100$	$4$	$4/16 = 1/4$	$[0; 4] = 1/4$	$r = 4$
$1000$	$8$	$8/16 = 1/2$	$[0; 2] = 1/2$	$r = 2$ (try multiples)
$1100$	$12$	$12/16 = 3/4$	$[0; 1, 3] = 3/4$	$r = 4$

Three of the four outcomes directly or indirectly yield $r = 4$. The outcome $y = 8$ gives $r = 2$; checking $7^2 = 49 \equiv 4 \not\equiv 1 \pmod{15}$ reveals this is not the true order, so we try $2r = 4$. Alternatively, we simply re-run the circuit for another sample.

Sandbox: Factor 15 with $a = 11$

To see that the algorithm works for different choices of $a$, try $a = 11$. Since $11^2 = 121 \equiv 1 \pmod{15}$, the order is $r = 2$. This means the QFT should produce peaks at multiples of $16/2 = 8$, giving outcomes near $0$ and $8$.

With $r = 2$ and $a = 11$: $a^{r/2} = 11^1 = 11 \equiv 11 \pmod{15}$. Since $11 \not\equiv -1 \pmod{15}$ (because $-1 \equiv 14$), we compute: $\gcd(11 - 1, 15) = \gcd(10, 15) = 5$ and $\gcd(11 + 1, 15) = \gcd(12, 15) = 3$. We recover the factors $3$ and $5$.

Interactive: Shor's Algorithm Walkthrough

Walk through Shor's algorithm end-to-end for factoring $N = 15$.

Step 1: Choose Random Base

Pick $a = 7$. Check: $\gcd(7, 15) = 1$, so $a$ is coprime to $N$. No free factor found.

Step 2: Quantum Order Finding

Prepare the superposition $\frac{1}{\sqrt{2^t}}\sum_x |x\rangle|1\rangle$, apply controlled modular exponentiation to get $\frac{1}{\sqrt{2^t}}\sum_x |x\rangle|7^x \bmod 15\rangle$, then apply the inverse QFT to the counting register.

Step 3: Continued Fractions

Measurement yields peaks at $y \in \{0, 4, 8, 12\}$. For $y=12$: $12/16 = 3/4$, giving candidate period $r = 4$. Check: $7^4 \bmod 15 = 1$. Confirmed.

Step 4: Extract Factors

$r = 4$ is even. Compute $a^{r/2} = 7^2 = 49 \equiv 4 \pmod{15}$. Since $4 \not\equiv -1$, compute: $\gcd(48, 15) = \mathbf{3}$ and $\gcd(50, 15) = \mathbf{5}$. Factors found: $15 = 3 \times 5$.

The Gap Between Textbook and Reality

The circuits above are heavily simplified. For the general case of factoring an $n$-bit number, the modular exponentiation oracle alone requires:

$O(n)$ controlled modular multiplications
Each multiplication decomposes into $O(n)$ modular additions
Each addition requires $O(n)$ elementary gates (Toffoli gates, CNOTs)
Total: $O(n^3)$ elementary gates, plus $O(n)$ ancilla qubits

For $N = 15$ (4 bits), the optimized circuits above use about 20 gates. For RSA-2048 ($n = 2048$ bits), a general implementation would require billions of gates. Furthermore, in a real quantum computer, each logical gate must be implemented fault-tolerantly using error correction codes, which multiplies the physical gate count by a factor of $10^3$ to $10^6$ depending on the target error rate and the error correction scheme.

Common Misconception.

The simplified circuits for factoring 15 that appear in textbooks (including the sandboxes above) use problem-specific optimizations that eliminate most of the modular arithmetic. These optimizations exploit the specific structure of the number 15 and do not generalize. A "fair" implementation of Shor's algorithm for $N = 15$ using a general-purpose modular exponentiation circuit would require on the order of 10,000 gates - far more than the optimized versions shown here.

11.7 Implications: Post-Quantum Cryptography

Shor's algorithm does not merely factor integers - it solves the more general hidden subgroup problem for abelian groups. This means it breaks not only RSA but also other cryptosystems whose security relies on problems with similar algebraic structure. Let us survey the damage and the defense.

Cryptographic Systems Threatened by Shor's Algorithm

The following widely deployed cryptosystems would be completely broken by a sufficiently powerful quantum computer:

RSA (all key sizes). RSA security depends on the difficulty of factoring the modulus $N = pq$. Shor's algorithm factors $N$ in polynomial time.
Elliptic Curve Cryptography (ECC). ECC security depends on the discrete logarithm problem on elliptic curves. Shor's algorithm, adapted to the elliptic curve group, solves this in polynomial time as well. This includes ECDSA (used in Bitcoin and TLS), ECDH (key exchange), and EdDSA.
Diffie-Hellman key exchange (both classical and elliptic curve variants). The security of Diffie-Hellman depends on the discrete logarithm problem, which Shor's algorithm solves.
DSA (Digital Signature Algorithm). Also relies on discrete logarithms.

Harvest Now, Decrypt Later.

Even before a large-scale quantum computer exists, adversaries can record encrypted traffic today and store it for decryption once quantum computers become available. This "harvest now, decrypt later" strategy means that data with long-term sensitivity (government secrets, medical records, financial data) is already at risk. The transition to quantum-resistant cryptography is therefore urgent, not something that can wait until quantum computers actually arrive.

What Shor's Algorithm Does Not Threaten

Importantly, not all cryptography is broken by quantum computers:

Symmetric-key cryptography (AES, ChaCha20). Grover's algorithm (Chapter 12) provides a quadratic speedup for brute-force key search, effectively halving the key length. This means AES-128 provides only 64 bits of quantum security, but AES-256 still provides 128 bits - considered sufficient. The fix is simply to use longer keys.
Cryptographic hash functions (SHA-256, SHA-3). Grover's algorithm reduces the security of hash functions, but the impact is manageable. SHA-256 provides approximately 128 bits of quantum security against collision attacks, which remains adequate.

NIST Post-Quantum Standards

Recognizing the threat, the U.S. National Institute of Standards and Technology (NIST) began a standardization process for post-quantum cryptographic algorithms in 2016. After eight years of evaluation involving researchers worldwide, NIST published its first three post-quantum standards in August 2024:

Standard	Original Name	Type	Mathematical Basis
FIPS 203 (ML-KEM)	CRYSTALS-Kyber	Key encapsulation	Module lattices (Learning With Errors)
FIPS 204 (ML-DSA)	CRYSTALS-Dilithium	Digital signature	Module lattices (Short Integer Solution)
FIPS 205 (SLH-DSA)	SPHINCS+	Digital signature	Hash functions (stateless hash-based signatures)

Additional algorithms are in the pipeline. FIPS 206, based on the FALCON algorithm (now called FN-DSA), provides a lattice-based signature scheme with smaller signatures. HQC, a code-based key encapsulation mechanism, was selected for standardization in March 2025 as a backup KEM that relies on different mathematical assumptions than ML-KEM, providing defense-in-depth in case lattice-based assumptions are broken.

Note.

The post-quantum standards replace public-key cryptography only. Symmetric ciphers like AES-256 and hash functions like SHA-3 are not being replaced - they just need larger parameters for quantum resistance. The transition primarily affects key exchange (replacing ECDH with ML-KEM), digital signatures (replacing ECDSA/EdDSA with ML-DSA or SLH-DSA), and encryption (replacing RSA-OAEP with ML-KEM-based hybrid schemes).

Timeline: When Will Quantum Computers Break RSA?

This is the multi-trillion-dollar question. The answer depends on the pace of hardware development and algorithmic improvements:

Current state (2026): The largest quantum processors have reached over 1,000 superconducting qubits (IBM), while neutral-atom arrays have exceeded 6,000 physical qubits. These are still noisy devices that cannot run Shor's algorithm for cryptographically meaningful numbers.
Resource estimates: Breaking RSA-2048 requires approximately 4,000 logical qubits running Shor's algorithm. With current error correction overhead, this translates to roughly 1 million physical qubits under conventional architectures. Recent research using quantum low-density parity-check (QLDPC) codes suggests this could be reduced to under 100,000 physical qubits.
Industry roadmaps: Major quantum computing companies project systems with hundreds of logical qubits by 2029-2030, and thousands of logical qubits in the early 2030s.
Expert consensus: Most estimates place a cryptographically relevant quantum computer (CRQC) - one capable of breaking RSA-2048 - in the 2030-2035 timeframe. The U.S. National Security Agency has set 2035 as a deadline for federal systems to transition to post-quantum cryptography.

Whether the timeline is 5 years or 15 years, the cryptographic community has concluded that the transition to post-quantum standards must begin now. Cryptographic migrations are slow - transitioning away from SHA-1 took over a decade after it was broken - and the "harvest now, decrypt later" threat means some data is already at risk.

Summary: The Impact of Shor's Algorithm

Shor's algorithm is arguably the most important result in quantum computing. It demonstrated that quantum computers can solve a specific, practically important problem exponentially faster than any known classical algorithm. Its implications include:

RSA, ECC, and Diffie-Hellman - the pillars of modern public-key cryptography - are vulnerable to quantum attack.
A global transition to post-quantum cryptographic standards is underway, driven by NIST and international counterparts.
Symmetric cryptography survives with increased key sizes.
The algorithm's structure - reducing a number-theoretic problem to period finding, then using the QFT to extract the period - exemplifies the power of quantum algorithms and has inspired numerous other quantum speedups for algebraic problems.

In the next chapter, we will encounter Grover's algorithm, which provides a different kind of quantum speedup - quadratic rather than exponential - but for a much broader class of problems: unstructured search.