Factoring 15 Step by Step

The full Shor pipeline is assembled in ch. 77. This chapter takes the smallest honest test case and walks through it arithmetically, so every step of the algorithm shows up as a number you can verify on paper. N = 15 is special: it is the smallest odd composite that is not a prime power, and r = 4 — the order of 7 modulo 15 — happens to be a clean power of 2, which means the quantum phase estimate lands exactly on a representable binary fraction. Every later Shor worked example is a variation on this theme; every textbook example of a quantum circuit for factoring uses N = 15. Learn this one, and you have the shape of the whole algorithm.

You will see two things in this chapter. First, the complete forward trace — what happens when you run the quantum circuit and get lucky — with arithmetic you can check by hand. Second, why N = 15 was the first composite factored experimentally, what the 2001 IBM NMR result did and did not demonstrate, and why most "demonstrations" of Shor's on numbers larger than 15 have to cheat. The first part teaches you the algorithm; the second part teaches you how to read experimental-quantum-computing claims without being taken in.

The setup — a = 7 and the orbit it generates

Start with N = 15. The first classical step of Shor is: pick an integer a in \{2, 3, \ldots, N - 1\} at random and compute \gcd(a, N). Random choice for this chapter: a = 7.

Compute \gcd(7, 15) by Euclid's algorithm:

Why this is Euclid: each line replaces the larger of the two numbers with the remainder when divided by the smaller. The remainder is strictly smaller, so the process terminates. The last non-zero remainder is the gcd. Here the remainder after the first line is 1, and the gcd is 1.

\gcd(7, 15) = 1, so 7 and 15 are coprime. You cannot read off a factor of 15 directly from a — you need the order r.

Before invoking the quantum computer, check classically what the order is. The powers of 7 modulo 15:

Why the order stops at the first 1: once 7^r \equiv 1, all higher powers repeat the cycle: 7^{r+1} = 7 \cdot 7^r = 7 \cdot 1 = 7, and so on. The orbit is a closed cycle.

So the orbit of 7 is \{1, 7, 4, 13\}, the order is r = 4, and the cycle is 1 \to 7 \to 4 \to 13 \to 1. This is the answer the quantum computer is about to return. For N = 15 you can compute this in four lines of arithmetic — which is the whole reason N = 15 is a pedagogical toy, not a cryptographic threat. Shor's speedup kicks in only when N is large enough that classical order-finding becomes infeasible (hundreds of digits), but the mechanism is exactly the same.

The quantum circuit for N = 15

Here is the circuit the quantum computer runs. It is the order-finding circuit from ch. 76, specialised to a = 7 and N = 15.

Registers. You need two quantum registers:

• Ancilla register: t = 8 qubits, all initialised to |0\rangle. The choice t = 2n = 8 (with n = \lceil \log_2 15 \rceil = 4) gives enough precision to read off r = 4 unambiguously from the phase estimate, with noise tolerance to spare.
• Target register: n = 4 qubits, initialised to |1\rangle = |0001\rangle (the 4-bit binary encoding of the integer 1). The target register will hold intermediate values |a^k \bmod N\rangle during the computation.

Why t = 2n ancillas: phase estimation with t ancillas returns a phase estimate with precision 2^{-t}. To distinguish the possible phases s/r = s/4 for s \in \{0, 1, 2, 3\}, you need precision better than 1/(2r^2) = 1/32. t = 8 gives precision 1/256 — comfortable overkill for r = 4, but standard for fault-tolerant Shor where you cannot assume r is small.

The gates. Four stages, in order:

1. Hadamard the ancillas: H^{\otimes 8} on the top register. This creates a uniform superposition \tfrac{1}{16}\sum_{y = 0}^{255} |y\rangle over all 2^8 = 256 ancilla basis states.
2. Controlled modular exponentiation: for each ancilla qubit k \in \{0, 1, \ldots, 7\}, apply the controlled unitary U_7^{2^k} to the target register. The full operator U_7^{2^k}\,|z\rangle = |7^{2^k} z \bmod 15\rangle can be precomputed:

After 7^2 = 4 we get 7^4 = 1 \pmod{15}, and all higher 7^{2^k} are 1 — the cycle of length r = 4 collapses higher powers trivially. Why this precomputation is legal: Shor's circuit construction uses the precomputed constant a^{2^k} \bmod N as a fixed multiplier in each controlled gate. This is not cheating — it is an ordinary classical preprocessing step that any implementation of Shor does, because the a^{2^k} values depend only on a and N, not on the quantum state. 3. Inverse QFT on the ancillas: \text{QFT}^{-1} rotates the ancilla register from the Fourier basis back to the computational basis. This is the "measure the phase" step of phase estimation. 4. Measure the ancillas in the computational basis. You get an 8-bit integer y \in \{0, 1, \ldots, 255\}, and \widetilde\varphi = y / 256 is the phase estimate.

The circuit is 13 qubits total and, after decomposing each U_7^{2^k} into its basic reversible-arithmetic constituents, costs O(n^3) \approx 64 Toffoli gates — small enough to simulate on any laptop and small enough to have been run (at various levels of faithfulness) on real hardware.

The measurement distribution — four peaks at multiples of 64

Before the measurement happens, think about what the ancilla register looks like after the inverse QFT. The math from ch. 77 says: phase estimation with target |1\rangle on U_7 returns an 8-bit integer y with probability concentrated on values y such that y / 2^8 \approx s / r for some s \in \{0, 1, 2, 3\}.

With r = 4 and t = 8, the phases s / r = s / 4 are exactly representable in 8 binary bits: 0/4, 1/4, 2/4, 3/4 = 0, 0.25, 0.5, 0.75, and y / 256 hits these exactly at y = 0, 64, 128, 192. So the measurement distribution is four sharp peaks, each with probability 1/4:

All other values of y have probability exactly zero — because the phases s/r are perfectly representable in the 8-bit ancilla register, destructive interference cancels every off-peak amplitude. This is the best-case scenario for phase estimation, and it is why N = 15 is the cleanest possible demonstration.

You measure and get one of the four values. The outcome y = 0 gives \widetilde\varphi = 0, which yields no information about r — you must retry. The other three outcomes all lead to r = 4 after continued fractions. So the algorithm succeeds on any single run with probability 3/4, and after two independent runs the failure probability drops to (1/4)^2 = 1/16.

Continued fractions — from a phase estimate to r

Suppose the measurement returns y = 192. Compute:

You now have a rational number. The quantum computer has done its job. Everything that follows is classical post-processing.

The continued-fractions algorithm (see ch. 79) writes a rational as a sequence of integer "quotients." For 3/4:

The convergents — successive best rational approximations — are:

Why convergents are the right candidates for r: a theorem of continued fractions says that if |\widetilde\varphi - s/r| < 1/(2r^2), then s/r must be one of the convergents of \widetilde\varphi. So the denominators of the convergents are the only plausible candidates for the order.

The candidates for r are therefore 1, 4. Check each: 7^1 = 7 \not\equiv 1 \pmod{15}, so r \neq 1. 7^4 = 2401 \equiv 1 \pmod{15}, so r = 4. Confirmed.

For the other non-trivial outcomes:

• y = 64: \widetilde\varphi = 1/4 = [0;\, 4]. Convergents 0/1, 1/4. Candidate r = 4. Correct.
• y = 128: \widetilde\varphi = 1/2 = [0;\, 2]. Convergents 0/1, 1/2. Candidate r = 2. Check: 7^2 = 4 \not\equiv 1 \pmod{15}, so r \neq 2. But r = 4 is a multiple of 2 — the algorithm returned a divisor of r, not r itself. Retry, or handle via the standard Shor post-processing step (multiply the candidate by the smallest k for which a^{kr_{\text{cand}}} \equiv 1). For the pedagogical example, it is simpler to assume you measured y = 192 or y = 64, each of which gives r directly.

Why the outcome y = 128 loses information: \widetilde\varphi = 1/2 = 2/4, which is an equivalent fraction but reduces to 1/2. The denominator r is there in the unreduced form but gets lost when you reduce. Mathematically: s = 2, r = 4 share a factor of 2, so the reduced fraction has denominator r / \gcd(s, r) = 2, not r. The probability of this loss is the probability that the random s shares a factor with r — for r = 4, that is s \in \{0, 2\}, or 2/4 = 1/2 of runs. In practice, Shor handles this by running the quantum circuit multiple times and taking the least common multiple of the candidate r values across runs.

Extracting the factors — a handful of gcds

With r = 4 confirmed, the classical reduction from ch. 75 takes over. Check the two conditions:

• r even? r = 4. Yes.
• a^{r/2} \not\equiv -1 \pmod N? Compute x = 7^{r/2} = 7^2 = 49 = 4 \pmod{15}. Is 4 \equiv -1 \pmod{15}? No: -1 \equiv 14, and 4 \neq 14. Yes, the condition holds.

Both conditions pass. Compute the two gcds:

Why these gcds factor N: you know a^r - 1 \equiv 0 \pmod N, so N divides a^r - 1 = (a^{r/2} - 1)(a^{r/2} + 1) = (x - 1)(x + 1). The condition x \not\equiv \pm 1 says N does not divide either factor individually — so N's prime factors must split between them. \gcd(x - 1, N) extracts whichever prime of N divides x - 1; \gcd(x + 1, N) extracts whichever divides x + 1.

Verify: 3 \times 5 = 15. Done. Both 3 and 5 are prime, so you have the complete factorisation.

The complete trace — on one page

A second base — a = 2 also works for N = 15

To see that the algorithm is not a one-off coincidence at a = 7, try a different base. This time the fading-scaffolds rule says: write out the steps, but trust the reader with the arithmetic this time.

Common confusions

• "N = 15 is a real test of Shor's algorithm." It is the smallest non-trivial test. But there are two features that make it a lucky test — r = 4 is a power of 2 (so the phase estimate is exact in any binary ancilla register) and r is small enough that continued fractions is trivial. A harder example like N = 21 (ch. 81) has r = 6, which is not a power of 2, and the measurement distribution smears over many bins.

• "The IBM 2001 experiment proved quantum computers can factor numbers." It demonstrated a specific circuit for N = 15 on a 7-qubit NMR system (Vandersypen, Steffen, Breyta, Yannoni, Sherwood, Chuang — IBM Almaden and Stanford). But the experiment used a precompiled circuit that hard-coded the fact that r = 4 — the controlled-U_7^{2^k} gates were simplified using classical knowledge of the answer. This was honest in 2001 (the authors explicitly said so), and it established that coherent quantum control at the scale of Shor was physically realisable. It did not demonstrate that the circuit would work if you did not know r in advance. Later ion-trap and photonic experiments on N = 15 have progressively closed the "cheating" gap.

• "The circuit scales with the same form for any N." The abstract circuit does — t ancillas, n data qubits, controlled-U_a^{2^k} ladder, inverse QFT — but the implementation of U_a^{2^k} as a reversible-arithmetic subcircuit depends on a and N. For N = 15, the subcircuit has a handful of Toffoli gates. For N = 2048-bit RSA, it is \sim 10^9 Toffolis. "Same circuit form, vastly different resource cost" is the general rule for Shor at different scales.

• "Picking a = 7 is special." Nothing is special about a = 7 for N = 15. Any a coprime to 15 works; the orders are r(1) = 1, r(2) = 4, r(4) = 2, r(7) = 4, r(8) = 4, r(11) = 2, r(13) = 4, r(14) = 2. Four of the seven coprime bases give r = 4 directly; two give r = 2, which happens to fail the condition a^{r/2} \not\equiv -1 or yields a trivial factor. Only a = 1 is useless (r = 1). So the algorithm succeeds with probability \approx 4/7 = 57\% on a random choice — high enough that a handful of retries suffices.

• "If Shor works on N = 15, the next step is N = 100-digit RSA." There is a gap of roughly 10^4 between what has been run experimentally and what is needed for cryptographic relevance. Every order-of-magnitude is an engineering programme. See ch. 77 for the full resource estimate.

Going deeper

The 2001 IBM NMR experiment

Lieven Vandersypen, Matthias Steffen, Gregory Breyta, Costantino Yannoni, Mark Sherwood, and Isaac Chuang — working across IBM Almaden Research Center and Stanford University — reported the first experimental demonstration of Shor's algorithm in a 2001 Nature paper (Vandersypen et al. 2001). The hardware was a 7-qubit nuclear magnetic resonance (NMR) system: the seven "qubits" were nuclear spins in a specifically synthesised perfluorobutadienyl iron complex molecule, addressed by radio-frequency pulses tuned to the individual nuclear resonances. Each NMR experiment was run on an ensemble of \sim 10^{18} copies of the molecule, not a single quantum system — the "quantum state" was read out as the bulk magnetisation signal averaged over the ensemble.

The circuit factored N = 15 with a = 7. The result: measurement outcomes concentrated at y = 0, 64, 128, 192, matching the expected distribution, and continued-fractions post-processing recovered r = 4.

Two caveats. First, the circuit was precompiled: the implementers knew the orbit structure of 7 \bmod 15 and simplified the controlled-U_7^{2^k} gates using that knowledge. Specifically, U_7^4 = I is identity, so the gates for k \geq 2 were replaced by identity — a genuine classical simplification, but one that exploits knowledge of r = 4 that the algorithm is supposed to output. Second, NMR ensemble computing is "pseudo-pure" — the initial state is not a genuine single-copy pure state but an ensemble average that mimics one. Whether this counts as "real" quantum computing has been debated ever since. The consensus: NMR Shor was a valuable proof of concept for coherent multi-qubit control, but not a cryptographic threat demonstration.

Later demonstrations and the honest-vs-cheated spectrum

Since 2001, N = 15 has been factored on several platforms:

• Photonic qubits — Lu et al. 2007, Lanyon et al. 2007 (University of Queensland).
• Superconducting qubits — Lucero et al. 2012 (UCSB), using a compiled circuit.
• Ion traps — Monz et al. 2016 (Innsbruck), with the most "honest" implementation to date: a single scalable quantum system, no ensemble averaging, explicit demonstration that the circuit works without knowing r in advance for the ion-trap architecture.

The spectrum from "fully cheated" to "fully honest" demonstrations has progressed steadily, but even the 2016 Innsbruck experiment used N = 15 — the structurally simplest non-trivial case. No fault-tolerant, error-corrected, fully generic Shor has ever been run on real hardware, on any N.

Why N = 15 is uniquely easy

Three reasons make N = 15 the pedagogical and experimental favourite:

1. r = 4 is a power of 2. The phase estimates s/r land exactly on 8-bit binary fractions, producing sharp delta-function peaks in the measurement distribution. No binary-truncation error.
2. The orbit length is small. The modular-exponentiation circuit for U_7^{2^k} has a closed-form structure because U_7^4 = I, so higher powers collapse to identity. This reduces the circuit to just four controlled gates that are non-trivial.
3. N - 1 = 14 has small multiplicative order structure. The group (\mathbb{Z}/15)^\times has order \phi(15) = 8, and every element's order divides 8 (so is 1, 2, 4, or 8). Shor's success probability is high, and retries are cheap.

For N = 21, none of these hold. r = 6 is not a power of 2. The orbit-length cycle of modular exponentiation is longer. And (\mathbb{Z}/21)^\times has order \phi(21) = 12, with a richer structure. See ch. 81.

The scaling gap to 2048-bit RSA

The quantum circuit you just simulated for N = 15 uses 13 qubits and \sim 64 Toffoli gates. For a 2048-bit RSA modulus (the actual cryptographic threat), the corresponding resource estimate (Gidney-Ekerå 2021, arXiv:1905.09749) is:

The ratios — \sim 500\times more logical qubits, \sim 10^7\times more Toffoli gates — are a measure of why "Shor works on N = 15" is a very different statement from "Shor breaks RSA today." Scaling up the circuit is polynomial in the bit-size of N; scaling up the hardware to run it is the open engineering problem of the field.

Indian hardware efforts

India's quantum-computing hardware programme is scaling from small research prototypes toward NISQ-class machines. As of 2025–2026: TIFR Mumbai runs small superconducting-qubit experiments; IISc Bangalore and IIT Madras have active academic groups; the National Quantum Mission (2023, ₹6000 crore over 8 years) funds a national network of quantum testbeds. An Indian-hardware-native demonstration of Shor on N = 15 has been a stated medium-term goal of the NQM quantum-computing pillar; as of the date of this article, the demonstration remains at the planning stage. The international ion-trap and superconducting-qubit community has already run N = 15 multiple times; catching up to the 2016 Innsbruck-class honest demonstration is a natural benchmark for Indian hardware.

Where this leads next

• Factoring 21 — why it's harder — the next composite, where r = 6 breaks the power-of-2 structure and the honest-vs-cheated distinction becomes central.
• The Shor circuit end to end — the full algorithm at arbitrary N, with the 2048-bit RSA resource estimate.
• Continued fractions — the classical post-processing that converted 3/4 to r = 4 in step 3.
• Order finding — the quantum idea — the derivation of why phase estimation on U_a returns a sample of s/r.
• Factoring reduces to order finding — the classical argument that order gives a factor of N.

References

1. Vandersypen, Steffen, Breyta, Yannoni, Sherwood, Chuang — Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance (2001) — arXiv:quant-ph/0112176. The IBM NMR demonstration of N = 15.
2. Peter Shor — Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer (1994/1995) — arXiv:quant-ph/9508027. The original algorithm.
3. Nielsen and Chuang — Quantum Computation and Quantum Information §5.3 — Cambridge University Press.
4. John Preskill — Lecture Notes on Quantum Computation Chapter 7 — theory.caltech.edu/~preskill/ph229.
5. Wikipedia — Shor's algorithm.
6. Qiskit Textbook — Shor's algorithm tutorial, with a worked example for N = 15.