How do a reduction, an order-finding circuit, a continued fraction and a gcd become a factoring algorithm, and what does it cost?
Every algorithm on this page so far has been a part or a special case. These two are the ones the world has heard of, and they are the two the rest of this site leans on: Grover's quadratic speed-up for unstructured search, which sets how much a symmetric key must grow, and Shor's exponential one for factoring, which is why public-key cryptography is being replaced. Each topic has a problem set with worked solutions, and a notebook that runs the whole thing with nothing but NumPy.
Shor's algorithm does not factor anything directly. It finds the order of a number: pick a, coprime to N, and look at the powers a, a², a³, … modulo N. They repeat, and the number of steps before they return to 1 is the order r. Finding r is hard for a classical computer when N has hundreds of digits, and it is exactly what the Fourier-transform machinery of topic 11, topic 12 and topic 13 does well.
From the order to the factors. Suppose r is even and put h = ar/2 mod N. Then h² ≡ 1 (mod N), which means N divides (h − 1)(h + 1). If h is neither 1 nor −1 modulo N, then neither factor is a multiple of N, so each of gcd(h − 1, N) and gcd(h + 1, N) is a proper divisor of N. For N = 15 and a = 7: the powers of 7 are 7, 4, 13, 1, so r = 4; h = 7² = 4; and gcd(3, 15) = 3, gcd(5, 15) = 5. Done, and a classical computer does every step except finding r.
When it fails, and why that is fine. Two things can go wrong: r may be odd, or h may be −1 (so h + 1 is a multiple of N and tells you nothing). Both are properties of the number a you picked, not of the machine, and the cure is to pick another a. Of the seven values a = 2, 4, 7, 8, 11, 13, 14 that are coprime to 15, six give a factor and only a = 14 (which is −1) fails. For N = 21 the count is 6 of the 11: a = 4 and 16 have odd order 3, and a = 5, 17 and 20 reach −1. For every odd N = pq with p and q distinct primes and N below 2,000 (396 numbers), at least half of the values of a coprime to N work, so a handful of random picks is enough.
The quantum step, in one example. Take N = 15, a = 7 and a counting register of eight qubits, so Q = 256 readings. The period 4 divides 256, so the interference is perfect: the register reads 0, 64, 128 or 192, each with probability exactly ¼, and never anything else. Read the result as the fraction y/256: 64 gives ¼, and the continued fraction (topic 13) returns the denominator 4, which is the order. 192 gives ¾, also denominator 4. 128 gives ½, whose denominator 2 is only a divisor of the true order (7² = 4, not 1), so that run fails. 0 gives nothing. One run therefore succeeds with probability ½, which is φ(4)/4, and two independent runs, combined by taking the least common multiple, succeed with probability ¾.
When the period does not divide Q. For N = 21 and a = 2 the order is 6, which does not divide Q = 512 (the smallest power of two at or above 21² = 441). The probability spreads out around the six ideal readings 0, 85, 171, 256, 341, 427, which carry 79% of it between them, and one run hands back r = 6 directly with probability 33%. That is a worse single-run rate and it is still a perfectly good algorithm, because a failed run costs only another run.
What this does not mean. Factoring 15 on a quantum computer is not evidence that a large number can be factored, and the numbers on this page are small on purpose: they are the only ones where every step can be written out. The difficulty of the real thing is in the size of the circuit, not in the idea.
The circuit. Take two registers. Put t qubits in uniform superposition, so the state is Q−1/2 Σx |x⟩|1⟩ with Q = 2t. Apply the modular-exponentiation unitary |x⟩|y⟩ → |x⟩|y·ax mod N⟩, giving Q−1/2 Σx |x⟩|ax mod N⟩. Measure the second register: the first is left in an even superposition over the x that share one value of ax mod N, that is, over x₀, x₀ + r, x₀ + 2r, …. Apply the quantum Fourier transform (topic 11) and measure. This is phase estimation (topic 12) on the unitary U|y⟩ = |ay mod N⟩, whose eigenvalues are e2πis/r.
What the readings are. If r divides Q the probability is exactly 1/r on each of the multiples sQ/r, s = 0, …, r − 1, as in the N = 15 example above. If it does not, the probability peaks near each sQ/r. For every case checked here (eight pairs (N, a) from N = 15 to N = 77, 92 peaks in all) the reading nearest an integer multiple of Q/r carries at least 4/(π²r) of the probability, with the smallest ratio to that bound 1.135. That is the bound Shor's paper and Nielsen and Chuang use to show that each peak is hit often enough for a few runs to suffice.
Why Q ≥ N². A reading y is within 1/(2Q) of some s/r. By Legendre's theorem (topic 13), s/r is a convergent of y/Q whenever |y/Q − s/r| < 1/(2r²), and since r < N this is guaranteed when Q ≥ N². For N = 15 that is Q ≥ 225, and 27 = 128 is too small while 28 = 256 is the smallest power of two that works. For an n-bit N the counting register is therefore about 2n qubits.
The classical wrapper. Choose a at random; if gcd(a, N) > 1 you have a factor already. Otherwise find r; if r is odd, or ar/2 ≡ −1, choose again. For an odd N with m distinct prime factors the chance that a random a coprime to N has an even order and ar/2 ≢ −1 is at least 1 − 2−(m−1) (Nielsen and Chuang, chapter 5), so at least ½ for a product of two primes; the sweep above finds no counterexample, and the tightest is exactly ½, at N = 21 (counting a = 1 as a failure, as the theorem does). N = 35 gives 18 of 23: the five failures are a = 11 and 16 (odd order 3), a = 19 and 24 (order 6, reaching −1) and a = 34 = −1. All of these are recomputed in orders and gcd steps for N = 15, 21 and 35; every odd semiprime below 2,000; the full N = 15 and N = 21 reading distributions by simulating the registers.
The cost. The modular exponentiation is the expensive part: a sequence of controlled multiplications by a2j mod N, each of which a classical computer can precompute, with O(n³) elementary gates for n-bit numbers by schoolbook arithmetic. Beauregard (Quantum Information and Computation 3, 175, 2003, arXiv quant-ph/0205095) gave a circuit that uses 2n + 3 qubits and O(n³ log n) gates: for RSA-2048 that is 4,099 logical qubits. Logical qubits are not physical ones: with error correction, Gidney and Ekerå (Quantum 5, 433, 2021, arXiv 1905.09749) estimated 2048-bit RSA in 8 hours with 20 million noisy physical qubits (assuming a physical error rate of 10−3 and a 1 microsecond cycle), and Gidney (arXiv 2505.15917, 2025) lowered that to under a million noisy qubits and under a week. These are costings of a machine nobody has built. Shor's original paper is Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26, 1484 (1997), arXiv quant-ph/9508027.
The reason the world is moving to post-quantum cryptography, and the reason demonstrations mislead RSA rests on the difficulty of factoring, and elliptic-curve signatures such as Bitcoin's on a close cousin, the discrete logarithm, which Shor's paper handles with the same period-finding idea. A machine big enough to run this at 2048 bits would break both; the Bitcoin page has a slider-driven estimate of what that takes, and the cryptography course shows what replaces them. It does not break symmetric encryption, where the best known quantum attack is the quadratic one of Grover's algorithm.
The first experiment, Vandersypen and colleagues (Nature 414, 883, 2001), factored 15 with seven nuclear spins in a molecule. Experiments on numbers this size say little about the hard part, and Smolin, Smith and Vargo (Nature 499, 163, 2013, arXiv 1301.7007) showed why: using a compiled version of the algorithm, which depends on knowing the answer in advance, they factored products of two unequal primes above two with only two coherent qubits and in constant time, arguing that what makes Shor's algorithm hard to implement is the length of the period, not the size of the number. A fair demonstration needs the full modular exponentiation for a number whose factors you do not know.
Six problems. Every answer below was recomputed by a program written separately from this page; try each before opening the solution. A notebook that simulates the order-finding step for N = 15 and N = 21 with nothing but NumPy is at shor.ipynb (open it in Jupyter, VS Code or Colab).
Problem 1. N = 15 and a = 2. Find the order of 2 and use it to factor 15.
The powers of 2 mod 15 are 2, 4, 8, 1, so r = 4. Then h = 2² = 4, which is neither 1 nor −1 (= 14). gcd(4 − 1, 15) = gcd(3, 15) = 3 and gcd(4 + 1, 15) = gcd(5, 15) = 5.
Problem 2. N = 21. For each of a = 2, 4, 5 and 8, say whether the method gives a factor, and if not why not.
a = 2: order 6, h = 2³ = 8, gcd(7, 21) = 7 and gcd(9, 21) = 3, so yes. a = 4: order 3, which is odd, so no. a = 5: order 6, but h = 5³ = 125 = 20 = −1 (mod 21), so no. a = 8: order 2, h = 8, gcd(7, 21) = 7 and gcd(9, 21) = 3, so yes.
Problem 3. In the N = 15, a = 7 run with eight counting qubits the register reads 192. Recover the order and check it.
192/256 = 3/4 in lowest terms. The continued fraction of 3/4 has the convergents 0, 1, 3/4, and the denominator 4 is below N = 15. Check: 74 = 2401 = 160 × 15 + 1, so 74 ≡ 1 and r = 4.
Problem 4. The same run reads 128 instead. What does the continued fraction offer, does it work, and how many runs do you need to be 7/8 sure of the order?
128/256 = 1/2, which offers the denominator 2. But 7² = 49 = 4 (mod 15), not 1, so 2 is not the order; it is a divisor of it, as topic 13 explains. A single run gives the order with probability ½ (readings 64 and 192; 0 and 128 fail). After k runs at least one succeeds with probability 1 − (½)k: ¾ for two, 7/8 for three. (Combining a 2 from one run with a 4 from another by the least common multiple also gives 4.)
Problem 5. Why does the counting register for N = 15 need eight qubits, and not seven?
The continued-fraction step is guaranteed to work when Q ≥ N² = 225. With seven qubits Q = 27 = 128 is below that, so a reading could be too far from s/r for the theorem to apply. With eight, Q = 256 ≥ 225. In general the register has about 2n qubits for an n-bit N.
Problem 6. For N = 35, how many of the 23 values a = 2, …, 34 coprime to 35 give a factor, and which ones fail?
18 of the 23. The five failures are a = 11 and 16 (order 3, odd), a = 19 and 24 (order 6, where a3 ≡ −1), and a = 34, which is −1 itself (order 2).
Check yourself
In a run of Shor's algorithm for N = 15 with a = 7 and eight counting qubits, the register reads 128. What does the continued fraction give, and what do you do?
128/256 = 1/2 offers the denominator 2, but 7² = 4 (mod 15), not 1, so 2 is not the order. It is a divisor of it, which is what happens when the numerator shares a factor with the period. One run gives the order with probability 1/2 (readings 64 and 192), so repeating, and combining answers by least common multiple, settles it.
The tempting wrong answers.