Skip to content

CHAPTER 13

# Period finding and Shor’s factoring algorithm

Learning goals. Work modular arithmetic and continued fractions, connect periodicity to Fourier peaks, and distinguish a small demonstration from cryptographic-scale factoring.

## 13.1 Number theory needed for the reduction

The greatest common divisor gcd(a,N)\gcd(a,N) is computed efficiently by Euclid’s algorithm. Repeatedly replace (a,N)(a,N) by (N,a mod N)(N,a\bmod N) until the remainder is zero. Modular exponentiation also has an efficient repeated-squaring algorithm: represent the exponent in binary and multiply only the required powers.

For gcd(a,N)=1\gcd(a,N)=1, the order r is the smallest positive integer with a r≡1(mod N)a^r\equiv1\pmod N. Then a x mod N a^x\bmod N repeats with period r.

If r is even, set t=a r/2 mod N t=a^{r/2}\bmod N. Since t 2≡1(mod N)t^2\equiv1\pmod N,

(t−1)(t+1)≡0(mod N).(t-1)(t+1)\equiv0\pmod N.

If t≢±1(mod N)t\not\equiv\pm1\pmod N, the gcd values gcd(t−1,N)\gcd(t-1,N) and gcd(t+1,N)\gcd(t+1,N) provide nontrivial factors. If r is odd or t≡−1 t\equiv-1, choose another base. A found gcd greater than one before quantum order finding is already a classical success.

Worked factorization. For N=15,a=2, powers are 1,2,4,8,1, so r=4. Then t=2 2=4 t=2^2=4, and

gcd(4−1,15)=3,gcd(4+1,15)=5.\gcd(4-1,15)=3,\qquad \gcd(4+1,15)=5.

This arithmetic is the end of the algorithm, not its quantum component.

## 13.2 The quantum state before the Fourier transform

Choose a control range Q=2 m Q=2^m, conventionally N 2≤Q<2 N 2 N^2\le Q<2N^2 for the elementary reconstruction guarantee. Compute modular exponentiation reversibly:

1 Q∑x=0 Q−1|x⟩|0⟩↦1 Q∑x|x⟩|a x mod N⟩.\frac1{\sqrt Q}\sum_{x=0}^{Q-1}|x\rangle|0\rangle \longmapsto \frac1{\sqrt Q}\sum_x|x\rangle|a^x\bmod N\rangle.

The operation must be a reversible circuit on all allowed basis inputs; computing into a clean work register is a shorthand for a reversible implementation with workspace. Efficient modular arithmetic is essential to Shor’s polynomial complexity [20].

Condition on a work-register value. Its compatible x values form a progression x 0,x 0+r,…,x 0+(L−1)r x_0,x_0+r,\ldots,x_0+(L-1)r, truncated at Q. The control state is

1 L∑k=0 L−1|x 0+k r⟩.\frac1{\sqrt L}\sum_{k=0}^{L-1}|x_0+kr\rangle.

After inverse QFT, the amplitude at y is

A y=e−2 π i x 0 y/Q L Q∑k=0 L−1 e−2 π i k r y/Q.A_y=\frac{e^{-2\pi ix_0y/Q}}{\sqrt{LQ}} \sum_{k=0}^{L-1}e^{-2\pi ikry/Q}.

The sum is large when ry/Q is near an integer. Therefore measured y tends to satisfy y/Q≈j/r. The offset contributes a phase but does not move the peaks. Summing probabilities over all possible work-register outcomes gives the unconditional control distribution.

If r divides Q exactly, peaks occur at y=j Q/r y=jQ/r. For N=15,a=2,Q=256,r=4, these are 0,64,128,192, each with probability 1/4 1/4. This unusually clean example should not be mistaken for the shape of every instance.

## 13.3 Continued fractions recover a candidate denominator

A rational approximation to y/Q can reveal j/r. Continued fractions successively extract an integer part and invert the remainder. Their convergents supply good rational approximations.

Suppose y/Q=171/512. Euclidean divisions begin

512=2(171)+170,171=1(170)+1,170=170(1).512=2(171)+170,\quad171=1(170)+1,\quad170=170(1).

Thus 171/512=[0;2,1,170]171/512=[0;2,1,170], with convergents 0/1,1/2,1/3,171/512 0/1,1/2,1/3,171/512. The small denominator three is a candidate period divisor if the observed ratio approximated j/r with reduced denominator three.

A candidate denominator must be checked by modular exponentiation. If j and r share a factor, the reduced denominator can be smaller than r; several samples or tested multiples may be needed. The outcome y=0 supplies no useful denominator. Neither a sharp Fourier peak nor a plausible fraction eliminates the verification step.

Worked nontrivial reconstruction. For N=21,a=2, the true order is six. A peak near y/Q≈1/6 can suggest r=6; one near 1/3 may suggest only a divisor. With verified r=6, t=2 3=8 t=2^3=8, so gcd(7,21)=7\gcd(7,21)=7 and gcd(9,21)=3\gcd(9,21)=3.

## 13.4 The complete classical–quantum loop

First handle even N, prime powers, and easy gcd cases using classical preprocessing. Select a coprime base, perform order finding, reconstruct and verify candidate orders, and apply the gcd reduction. Repeat when an uninformative sample or unsuitable order occurs. Efficient primality and perfect-power tests are classical; they are not quantum speedups.

The algorithm runs in time polynomial in log N\log N with suitable fault-tolerant logical arithmetic and precision accounting. That asymptotic theorem is not a claim about today’s available machines. Physical feasibility depends on error rates, logical operations, workspace, factories, decoding, and time.

Laboratory L18 — Small-instance order finding. Choose N=15 or 21 and a base. The simulator computes modular exponentiation groups and the exact Fourier marginal, samples y, and shows continued-fraction candidates and gcd checks. A control register too small for the textbook guarantee is explicitly identified.

The laboratory is a classical simulation of the mathematical order-finding experiment. It is not a hardware benchmark or a full gate decomposition of cryptographic modular arithmetic. Unlike a canned “factor 15” animation, its outcome distribution is recomputed from a,N,Q, and a bad sample can fail.

## 13.5 Modern resource claims

A resource estimate is conditional on an architecture and error model. Gidney’s 2025 analysis estimates RSA-2048 factoring with fewer than a million noisy qubits and under a week under its specified superconducting-style assumptions [52]. A March 2026 preprint by Cain and colleagues explores much smaller reconfigurable-atom counts using different coding and architecture assumptions [53]. Neither describes a completed RSA-2048 factorization on a quantum machine. Chapter 20 explains how to read these estimates, and Chapter 24 records their evidence status.

## 13.6 Exercises

13.1. Find the order of 4 modulo 15 and complete the factorization.

Show solution / guidance

4 1=4 4^1=4, 4 2≡1 4^2\equiv1, so r=2. Then t=4 and gcd values are 3 and 5.

13.2. Why is a=14 unsuitable in the final reduction for N=15?

Show solution / guidance

Its order is two, but 14 1≡−1(mod 15)14^{1}\equiv-1\pmod{15}. The gcd values are 1 and 15, so the reduction gives no nontrivial factor.

13.3. In the clean N=15,a=2,Q=256 experiment, what does y=128 reveal?

Show solution / guidance

y/Q=1/2 y/Q=1/2 suggests denominator two, a divisor of the actual order four. Testing 2 2 mod 15=4 2^2\bmod15=4 rejects it as a full order; testing the multiple four succeeds.

13.4. What minimum power-of-two Q satisfies Q≥21 2 Q\ge21^2?

Show solution / guidance

21 2=441 21^2=441 and the next power of two is 512, requiring nine control qubits. Work and arithmetic ancillas are additional.

13.5. Why does knowing factors in advance risk invalidating a hardware demonstration of Shor’s general algorithm?

Show solution / guidance

A circuit can be compiled using the known period or answer, eliminating the hard modular arithmetic. Such a demonstration may test selected gates and interference, but it does not validate general scalable factoring.

IN THIS CHAPTER