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)$ is computed efficiently by Euclid’s algorithm. Repeatedly replace $(a,N)$ by $(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$, the order r is the smallest positive integer with $a^r\equiv1\pmod N$. Then $a^x\bmod N$ repeats with period r.

If r is even, set $t=a^{r/2}\bmod N$. Since $t^2\equiv1\pmod N$,

$$(t-1)(t+1)\equiv0\pmod N.$$

If $t\not\equiv\pm1\pmod N$, the gcd values $\gcd(t-1,N)$ and $\gcd(t+1,N)$ provide nontrivial factors. If r is odd or $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$, and

$$\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$, conventionally $N^2\le Q<2N^2$ for the elementary reconstruction guarantee. Compute modular exponentiation reversibly:

$$\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,\ldots,x_0+(L-1)r$, truncated at Q. The control state is

$$\frac1{\sqrt L}\sum_{k=0}^{L-1}|x_0+kr\rangle.$$

After inverse QFT, the amplitude at y is

$$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=jQ/r$. For N=15,a=2,Q=256,r=4, these are 0,64,128,192, each with probability $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,\quad171=1(170)+1,\quad170=170(1).$$

Thus $171/512=[0;2,1,170]$, with convergents $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$, so $\gcd(7,21)=7$ and $\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$ 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.

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