# Period finding and Shor's factoring algorithm {#shor}

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

## 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.

## 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 [@shor].

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.

## 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$.

## 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.

::: {.lab #lab-shor}
**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.

## 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 [@gidney2025]. A March 2026 preprint by Cain and colleagues explores much smaller reconfigurable-atom counts using different coding and architecture assumptions [@cain2026]. 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.

## Exercises

:::: {.exercise #ex13-1}
**13.1.** Find the order of 4 modulo 15 and complete the factorization.

::: {.solution}

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

::::

:::: {.exercise #ex13-2}
**13.2.** Why is a=14 unsuitable in the final reduction for N=15?

::: {.solution}

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

::::

:::: {.exercise #ex13-3}
**13.3.** In the clean N=15,a=2,Q=256 experiment, what does y=128 reveal?

::: {.solution}

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

::::

:::: {.exercise #ex13-4}
**13.4.** What minimum power-of-two Q satisfies $Q\ge21^2$?

::: {.solution}

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

::::

:::: {.exercise #ex13-5}
**13.5.** Why does knowing factors in advance risk invalidating a hardware demonstration of Shor's general algorithm?

::: {.solution}

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.
:::

::::

