Order Finding and Period Finding

Order finding is the beating heart of quantum computing's most famous result — Shor's polynomial-time factoring algorithm — and yet the problem it solves is pure number theory with no quantum mechanics in sight. Fix a modulus $N$ and a base $a$ coprime to it. The powers $a^0, a^1, a^2, \dots \pmod N$ march around a finite cycle and eventually return to $1$ ; the length of that cycle is the multiplicative order $r$ , the smallest $r>0$ with $a^r\equiv 1\pmod N$ . Computing $r$ classically is, as far as anyone knows, as hard as factoring $N$ itself. The quantum algorithm cracks it by a change of viewpoint: it treats "multiply by $a$ " as a unitary operator, notices that the period $r$ is written into that operator's eigenvalues $e^{2\pi i s/r}$ , and reads those eigenvalues off with quantum phase estimation and the quantum Fourier transform. The mechanism is disarmingly clean. Multiplication by $a$ modulo $N$ permutes the basis states $\{0,1,\dots,N-1\}$ , so it is unitary; its eigenvectors are Fourier modes over the orbit of $a$ , with eigenphases exactly the multiples $s/r$ . We never build those eigenvectors — we cannot, since that would require knowing $r$ . Instead we feed in the humble state $|1\rangle$ , an equal superposition of all of them, and let phase estimation collapse it onto one random $s/r$ . A single run hands us a rational whose hidden denominator is $r$ ; the ancient theory of continued fractions then sifts that denominator out exactly, provided the register carried more than $2\log_2 N$ qubits of precision. Order finding sits at the head of a family tree — general period finding, Simon's problem, the discrete logarithm, and the whole abelian hidden subgroup problem are the same circuit template with the Fourier transform taken over a different group. Master this node and the rest of the tree unlocks.

Key takeaways

Order finding asks: given coprime integers $a$ and $N$ , find the least $r>0$ with $a^r\equiv 1\pmod N$ ; period finding is the same question for any $f$ with $f(x)=f(x+r)$ .
The modular-multiplication unitary $U_a:|y\rangle\mapsto|ay\bmod N\rangle$ has eigenvalues $e^{2\pi i s/r}$ , so the period lives in its phase spectrum.
Phase estimation seeded with $|1\rangle$ samples a uniformly random multiple $s/r$ ; continued fractions convert the measured $j/2^t\approx s/r$ into the exact denominator $r$ once $2^t\ge N^2$ .
One run returns the full order when $\gcd(s,r)=1$ , which happens with probability $\varphi(r)/r=\Omega(1/\log\log r)$ — a handful of repetitions makes success a near certainty.
The whole routine runs in $O((\log N)^3)$ time, an exponential speedup over the best known classical factoring, and needs no black-box oracle: $U_a$ is a real reversible arithmetic circuit.
Key idea: The multiplicative order $r$ is hidden in the eigenphases of the modular-multiplication unitary $U_a:|y\rangle\mapsto|ay\bmod N\rangle$ , whose eigenvalues are $e^{2\pi i s/r}$ . Phase estimation seeded with $|1\rangle$ samples a uniformly random $s/r$ , and continued fractions reconstruct $r$ exactly once the precision exceeds $N^2$ .

Where this lives today

Order finding is no longer just a theorem — it is the reference target the whole field aims at, and the reason a global cryptographic migration is underway. Small instances are the standard end-to-end benchmark: the 2001 IBM–Stanford NMR experiment factored 15, and later photonic and superconducting devices repeated 15 and 21, each stressing the full stack — reversible modular arithmetic, the inverse QFT, and classical post-processing — rather than isolated gates, and the community now insists on circuits that do not secretly compile in the answer $r$ . The sobering numbers are for cryptographically relevant $N$ : factoring a 2048-bit RSA modulus is estimated to need on the order of twenty million noisy physical qubits running for hours under surface-code error correction, which motivates work on qubit-efficient modular exponentiation. Meanwhile the abstract structure keeps paying dividends: the discrete-logarithm variant threatens elliptic-curve cryptography, and the recognition that all of these are abelian hidden-subgroup problems drives the hunt for a non-abelian generalization — so far unsuccessful, which is exactly why post-quantum cryptography bets on those harder groups.

The physical picture

Picture the sequence $1, a, a^2, a^3, \dots \pmod N$ as the hand of a clock that ticks forward one notch each time you multiply by $a$ and snaps back to $1$ every $r$ ticks. The whole algorithm measures the spacing of that clock without walking around it tick by tick — because $r$ can be of order $N$ itself, counting is hopeless. The first figure fixes the object: a small orbit whose length $r$ is exactly the number we want.

Figure

The orbit of a = 7 modulo N = 15 is a clock with r = 4 ticks: 1 → 7 → 4 → 13 → 1. Multiplying by 7 advances one tick, and after r steps the hand returns to 1, so U_a raised to the power r is the identity operator

The Fourier transform sees periodicity the way a prism sees a pure colour: a signal of period $r$ concentrates all of its weight at frequencies that are multiples of $1/r$ . So if we load the orbit into a register and Fourier-transform it, the answer shows up as a comb of sharp peaks whose spacing encodes $r$ — exactly what phase estimation on $U_a$ arranges. The slick part is that we never prepare an eigenvector by hand: the state $|1\rangle$ is already the equal superposition $\tfrac{1}{\sqrt r}\sum_s|u_s\rangle$ of every eigenvector of $U_a$ , so phase estimation acting linearly collapses onto one random eigenphase $s/r$ for free. The second figure shows what the measurement register looks like: a picket fence of peaks at the integers nearest $2^t s/r$ .

Figure

Phase estimation on the seed state turns the hidden period into a comb of peaks. With 2^t = 512 and r = 4 the measured integer j lands on a multiple of 2^t/r = 128; reading j = 384 gives 384/512 = 3/4, whose denominator r = 4 the continued-fraction step recovers exactly

Why $2^t\ge N^2$ ? Because two distinct candidate fractions with denominators below $N$ can be as close as $1/(rr')>1/N^2$ ; if the measurement lands within $1/(2N^2)$ of the true $s/r$ , no impostor can sit closer, and continued fractions must return the right one. The precision has to beat the minimum gap between periods. One last subtlety separates order finding over $\mathbb{Z}$ from Simon's problem over $\mathbb{Z}_2^n$ : in general $r$ does not divide $2^t$ , so the Fourier peaks are slightly smeared and we get an approximation $j/2^t\approx s/r$ , not an exact equation. Continued fractions are precisely the tool for de-noising an approximate rational back to an exact one.

The core equations

The problem lives in the multiplicative group $(\mathbb{Z}/N\mathbb{Z})^\times$ : the order of an element is the smallest exponent that brings it home to the identity.

r = \min\{\, k>0 : a^k \equiv 1 \pmod N \,\}, \qquad \gcd(a,N)=1 \qquad (1)

where: $N$ — the modulus, an integer to be factored or analyzed; $a$ — a base coprime to $N$ , an element of $(\mathbb{Z}/N\mathbb{Z})^\times$ ; $r$ — the multiplicative order of $a$ . Coprimality makes $a$ invertible mod $N$ , so a finite order exists and divides $\varphi(N)$ by Lagrange's theorem. The quantum leverage comes from promoting "multiply by $a$ " to an operator on $\lceil\log_2 N\rceil$ qubits. Because $a$ is invertible, this map permutes basis states, and every permutation matrix is unitary.

U_a\,|y\rangle = |\,ay \bmod N\,\rangle \quad (0 \le y < N), \qquad U_a^r = I \qquad (2)

where: $U_a$ — the unitary permuting basis states by multiplication by $a$ mod $N$ ; $|y\rangle$ — a basis state encoding the integer $y$ . Applying $U_a$ $r$ times returns every state to itself, so $U_a^r=I$ and all eigenvalues are $r$ -th roots of unity: the classical period becomes the operator's order. The eigenvectors are the discrete Fourier modes over a single orbit of $a$ , each packaging the whole cycle $1, a, a^2,\dots$ with an $r$ -th-root-of-unity twist; the eigenphase is the multiple $s/r$ we are hunting.

|u_s\rangle = \frac{1}{\sqrt r}\sum_{k=0}^{r-1} e^{-2\pi i s k / r}\,|a^k \bmod N\rangle, \qquad U_a|u_s\rangle = e^{2\pi i s/r}\,|u_s\rangle \qquad (3)

where: $|u_s\rangle$ — the $s$ -th eigenvector, a Fourier mode over the orbit of $a$ ; $s$ — the eigenphase label, $s=0,1,\dots,r-1$ ; $e^{2\pi i s/r}$ — the eigenvalue whose phase is a multiple of $1/r$ . Learn the eigenphase, learn a multiple of the reciprocal period. We cannot prepare $|u_s\rangle$ — it is built from powers of $a$ up to $r-1$ , and $r$ is unknown. The escape hatch is that summing all the eigenvectors reconstitutes a state we can trivially prepare, the integer $1$ .

\frac{1}{\sqrt r}\sum_{s=0}^{r-1} |u_s\rangle = |\,1\,\rangle \qquad (4)

where: $|1\rangle$ — the basis state encoding the integer $1$ , the seed fed into phase estimation. Feeding in $|1\rangle$ is thus identical to feeding in a uniformly random eigenvector: linearity averages, and we harvest a random $s$ at no cost. Phase estimation with a $t$ -qubit register outputs an integer $j$ pinning the eigenphase to within one part in $2^t$ ; its nearest-integer bound is a textbook constant.

\Big|\,\frac{j}{2^t} - \frac{s}{r}\,\Big| \le \frac{1}{2^{t+1}}, \qquad \Pr\Big[\text{nearest } j\Big] \ge \frac{4}{\pi^2} \approx 0.405 \qquad (5)

where: $j$ — the integer read from the $t$ -qubit phase register; $2^t$ — the register dimension, i.e. the precision; $4/\pi^2$ — the guaranteed lower bound on landing on the nearest integer to $2^t s/r$ . Taking $t=2\lceil\log_2 N\rceil+1$ makes continued fractions unable to fail. The classical post-processing is a theorem from Diophantine approximation: a rational close enough to a small-denominator target must appear among that target's continued-fraction convergents.

\text{If } \Big|x - \frac{p}{q}\Big| \le \frac{1}{2q^2}, \text{ then } \frac{p}{q} \text{ is a convergent of } x \qquad (6)

where: $x=j/2^t$ — the measured rational; $p/q=s/r$ in lowest terms — the target; $q$ — the recovered denominator, equal to $r$ when $\gcd(s,r)=1$ . The Euclidean algorithm generates every convergent cheaply. Whether a run returns the full order or a divisor is decided by one coprimality event, with probability Euler's totient ratio.

\Pr[\gcd(s,r)=1] = \frac{\varphi(r)}{r} \;\ge\; \frac{c}{\log\log r} \qquad (7)

where: $\varphi(r)$ — Euler's totient, the count of integers in $[1,r]$ coprime to $r$ ; $c$ — a positive absolute constant. The bound decays so slowly that $O(\log\log r)$ repetitions suffice for constant success. Assembling the pieces gives the runtime that made the algorithm famous: polynomial in the digits of $N$ , where every classical method is superpolynomial.

T_{\text{gates}} = O\big((\log N)^2 \log\log N \,\log\log\log N\big),\qquad T_{\text{total}} = O\big((\log N)^3\big) \qquad (8)

where: $T_{\text{gates}}$ — the quantum cost, dominated by modular exponentiation with fast (Schönhage–Strassen) multiplication; $T_{\text{total}}$ — including continued-fraction post-processing. With schoolbook arithmetic the quantum cost is a plain $O((\log N)^3)$ .

Derivation AThe order hidden in the eigenphases of modular multiplication

The goal of this derivation is to prove the two facts that make order finding possible at all: first that the modular-multiplication unitary $U_a$ has eigenvalues $e^{2\pi i s/r}$ with the eigenvectors of equation (3), so the unknown period $r$ is written into its spectrum; and second that the trivially preparable state $|1\rangle$ is an equal superposition of all $r$ eigenvectors, so phase estimation on $|1\rangle$ samples a random eigenphase without ever constructing one. Both follow from a single tool — the orthogonality of $r$ -th roots of unity.

Step 1. Act with $U_a$ on the candidate eigenvector: $U_a|u_s\rangle=\tfrac{1}{\sqrt r}\sum_{k=0}^{r-1}e^{-2\pi isk/r}|a^{k+1}\bmod N\rangle$ , since $U_a$ sends $|a^k\rangle$ to $|a^{k+1}\rangle$ . Why: the unitary advances every term one step around the orbit — a relabelling $k\to k+1$ , not a genuine mixing.

Step 2. Substitute $k'=k+1$ and use $a^r\equiv a^0$ to keep the sum over one period: $U_a|u_s\rangle=\tfrac{1}{\sqrt r}\sum_{k'}e^{-2\pi is(k'-1)/r}|a^{k'}\rangle=e^{2\pi is/r}\,|u_s\rangle$ . Why: pulling the constant $e^{2\pi is/r}$ out of every term leaves the original vector untouched — an eigenvector with that eigenvalue.

Step 3. Now expand the equal superposition by inserting definition (3): $\tfrac{1}{\sqrt r}\sum_{s=0}^{r-1}|u_s\rangle=\tfrac{1}{r}\sum_{s=0}^{r-1}\sum_{k=0}^{r-1}e^{-2\pi isk/r}|a^k\rangle$ . Why: writing both sums out exposes an inner sum over $s$ we can do in closed form.

Step 4. Swap the order of summation and evaluate the geometric series over $s$ :

\sum_{s=0}^{r-1} e^{-2\pi i s k/r} = r\,\delta_{k,0}.

Why: the roots of unity for $k\neq 0$ are equally spaced around the unit circle and sum to zero; only $k=0$ survives, with all $r$ terms adding coherently.

Step 5. Keep the surviving $k=0$ term: $\tfrac{1}{\sqrt r}\sum_s|u_s\rangle=\tfrac{1}{r}\cdot r\,|a^0\rangle=|1\rangle$ . Why: this is the seed identity — the plain, cheaply prepared state $|1\rangle$ secretly carries equal weight on every eigenvector, so phase estimation on it returns a uniformly random $s$ . *Verified: eigenvalue equation and seed identity reproduce Nielsen & Chuang §5.3 by root-of-unity orthogonality; both checked symbolically for $r=4$ ( $a=7\bmod15$ ) and $r=6$ ( $a=2\bmod21$ ).*

Go deeper · Derivation B · 2 minTracing the order-finding circuit from input to measurement

Derivation BTracing the order-finding circuit from input to measurement

The goal here is to follow the actual quantum circuit register by register and watch the period surface as a measurable integer. We run phase estimation on $U_a$ with the seed $|1\rangle$ : superpose over exponents, apply controlled modular exponentiation to correlate each exponent with a power of $a$ , decompose the target in the eigenbasis so each eigenphase tags its own phase ramp, invert the Fourier transform to turn each ramp into a spike, and measure. The endpoint is a random integer $j$ within $\tfrac12$ of $2^t s/r$ — one noisy sample of a multiple of $1/r$ .

Step 1. Initialize $|\psi_0\rangle=|0\rangle^{\otimes t}\otimes|1\rangle$ with $t=2\lceil\log_2 N\rceil+1$ control qubits and a target holding the integer $1$ . Why: the control register will hold the exponent $x$ ; seeding the target with $|1\rangle$ invokes the seed identity so we never need an eigenvector.

Step 2. Hadamard the controls to build a uniform superposition over all exponents:

|\psi_1\rangle = \frac{1}{\sqrt{2^t}}\sum_{x=0}^{2^t-1}|x\rangle\otimes|1\rangle.

Why: superposing every exponent at once is the quantum parallelism that lets a single circuit probe the entire sequence $a^0,\dots,a^{2^t-1}$ .

Step 3. Apply controlled modular exponentiation, $U_a^x$ conditioned on $|x\rangle$ , giving $|\psi_2\rangle=\tfrac{1}{\sqrt{2^t}}\sum_x|x\rangle\otimes|a^x\bmod N\rangle$ . Why: this is the only oracle-like step, and it is a genuine circuit — repeated squaring turns $U_a^x$ into $O(\log N)$ controlled multiplications, no exponential blowup.

Step 4. Rewrite the target in the eigenbasis using $|1\rangle=\tfrac{1}{\sqrt r}\sum_s|u_s\rangle$ and $U_a^x|u_s\rangle=e^{2\pi isx/r}|u_s\rangle$ :

|\psi_2\rangle = \frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}\Big(\frac{1}{\sqrt{2^t}}\sum_{x} e^{2\pi i sx/r}|x\rangle\Big)\otimes|u_s\rangle.

Why: each eigenvalue branch now carries a pure phase ramp $e^{2\pi isx/r}$ in the control register — a signal of frequency $s/r$ that the Fourier transform is built to detect.

Step 5. Apply the inverse QFT to the controls, mapping each ramp to a state sharply peaked at the nearest integer to $2^t s/r$ :

|\psi_3\rangle = \frac{1}{\sqrt r}\sum_{s=0}^{r-1}|\,\widetilde{s/r}\,\rangle\otimes|u_s\rangle.

Why: the inverse QFT converts "a phase winding at rate $s/r$ " into "a spike at position $2^t s/r$ ".

Step 6. Measure the control register: the outcome is $j\approx 2^t s/r$ for a uniformly random $s\in\{0,\dots,r-1\}$ , the nearest integer with probability $\ge 4/\pi^2$ . Why: the entangled target picks one branch $s$ at random, and the peaked register reads out its eigenphase — one clean sample of a multiple of $1/r$ . *Verified: reduces to standard QFT phase estimation (Nielsen & Chuang §5.2–5.3). For $N=15,\ a=7,\ r=4$ the peaks fall exactly on $j\in\{0,128,256,384\}$ with $2^t=512$ ; for $N=21,\ a=2,\ r=6$ the $s=1$ peak lands at $j=341$ — both confirmed numerically.*

Go deeper · Derivation C · 1 minRecovering the period with continued fractions

Derivation CRecovering the period with continued fractions

The goal of this final derivation is to justify the classical back end: given a single measured rational $j/2^t$ guaranteed within $1/2^{t+1}$ of some unknown $s/r$ , recover $r$ exactly and provably. The engine is a uniqueness argument — with enough precision, only one fraction of denominator below $N$ can sit that close to the measurement — married to the theorem that such a fraction must be a continued-fraction convergent of $j/2^t$ . The one gap is the coprimality of $s$ and $r$ , which we detect and repair by a verification-and-repeat loop.

Step 1. Bound the gap between rival periods: for distinct fractions with denominators below $N$ ,

\Big|\frac{s}{r}-\frac{s'}{r'}\Big| = \frac{|sr'-s'r|}{rr'} \ge \frac{1}{rr'} > \frac{1}{N^2}.

Why: the numerator is a nonzero integer, so it is at least $1$ ; this sets the minimum spacing the precision must beat.

Step 2. Demand precision that beats the half-gap. Choosing $2^t\ge N^2$ gives

\Big|\frac{j}{2^t}-\frac{s}{r}\Big|\le\frac{1}{2^{t+1}}\le\frac{1}{2N^2}<\frac{1}{2r^2},

so $s/r$ is the unique fraction of denominator $<N$ within reach. Why: once the error is below $1/2r^2$ the continued-fraction theorem (6) applies verbatim, and no impostor can compete.

Step 3. Expand $x=j/2^t$ as a continued fraction by the Euclidean algorithm and list its convergents $p_n/q_n$ ; the theorem guarantees $s/r$ (in lowest terms) is one of them. Why: continued fractions give the best rational approximations of every denominator, so the unique close fraction must appear.

Step 4. Read off the denominator: $r=q_n$ precisely when $\gcd(s,r)=1$ ; otherwise it is the proper divisor $r/\gcd(s,r)$ . Verify each candidate by testing $a^{q_n}\equiv 1\pmod N$ . Why: a cheap modular exponentiation distinguishes the true order from a divisor with certainty.

Step 5. If the check fails, repeat: two runs yield denominators whose least common multiple equals $r$ with constant probability, and $\varphi(r)/r=\Omega(1/\log\log r)$ ensures $O(\log\log r)$ runs suffice. Why: coprime numerators are common enough that a handful of samples reconstructs the full order almost surely. *Verified: for $N=21,\ a=2,\ r=6$ the measurement $j=341$ gives continued fraction $[0;6,170,2]$ with convergent $1/6$ (denominator $6=r$ ), and $|341/2048-1/6|\approx1.6\times10^{-4}<1/4096$ , so recovery is provably forced. Confirmed against Hardy & Wright and Nielsen & Chuang Theorem A4.16.*

Limiting cases

The algorithm's behaviour turns entirely on the register precision, whether the random numerator is coprime to $r$ , and whether $r$ is degenerate:

Case	Result	Meaning
Sufficient precision	$2^t \ge N^2$	The measurement is closer to $s/r$ than any rival fraction of denominator $<N$ , so continued fractions recover $r/\gcd(s,r)$ exactly; $t=2\lceil\log_2 N\rceil+1$ also lifts phase-estimation success above $1-\epsilon$ .
Coprime numerator	$\gcd(s,r)=1$	The lucky case: continued fractions return the full order $r$ in one shot, with probability $\varphi(r)/r=\Omega(1/\log\log r)$ .
Non-coprime numerator	$d=\gcd(s,r)>1$	The run returns only the proper divisor $r/d$ ; recover $r$ from $\mathrm{lcm}$ of two runs' denominators, which succeeds with constant probability.
Insufficient precision	$2^t < N^2$	A competing fraction can masquerade as $s/r$ ; continued fractions may return a wrong denominator, and the algorithm loses its correctness guarantee.
Degenerate order	$r\in\{1,2\}$	$r=1$ means $a\equiv1$ (excluded by construction); $r=2$ with $a\equiv-1$ gives no useful Shor factor. Classical preprocessing discards these before the quantum subroutine runs.

Common trapThe measurement gives s over r for a random s, not one over r

It is tempting to think the register measures $1/r$ directly, so the recovered denominator is always the period. It is not. Phase estimation samples $s/r$ for a uniformly random $s\in\{0,\dots,r-1\}$ , and continued fractions return $s/r$ in lowest terms — whose denominator is $r/\gcd(s,r)$ , equal to $r$ only when $s$ is coprime to $r$ . Two failure modes follow. First, if you forget the $\gcd$ you accept a proper divisor of $r$ as the order and are baffled when $a^{r'}\not\equiv1\pmod N$ ; always verify, and on failure take least common multiples across runs. Second, if you skimp on qubits and use $2^t<N^2$ , the uniqueness argument collapses and a spurious fraction can slip inside the measurement error. The cure for both is the same: enough precision, then verify and repeat.

Worked examples

1 · Factoring 15 with a = 7 (fully worked)

Take $N=15$ and the random base $a=7$ . Trace the order-finding circuit, read a measurement, recover the order, and complete Shor's reduction to a factor of 15.

Step 1. Fix the register size. With $\lceil\log_2 15\rceil=4$ , use $t=9$ control qubits and $2^t=512$ ; the condition $2^t\ge N^2=225$ holds, so continued fractions are forced to succeed.

Step 2. For checking, the order is $7,\ 49\equiv4,\ 13,\ 1\pmod{15}$ , so $\mathbf{r=4}$ . The circuit does not know this; it discovers a multiple of $1/4$ .

Step 3. Predict the comb: peaks at $j\approx 512\,s/4=128\,s$ , i.e. $j\in\{0,128,256,384\}$ — here $r=4$ divides $512$ exactly, so the peaks are perfectly sharp. Suppose the register returns $\mathbf{j=384}$ .

Step 4. Post-process. Form $x=384/512=3/4$ ; its denominator is $4$ and $\gcd(3,4)=1$ , so this is the full order $r=4$ . Verify $7^4=2401\equiv1\pmod{15}$ . (Had we measured $j=256\to1/2$ , the denominator $2$ is only the divisor $r/2$ ; the check $7^2\equiv4\not\equiv1$ flags it and we repeat.)

Step 5. Complete Shor's reduction. Since $r=4$ is even and $a^{r/2}=7^2\equiv4\not\equiv-1\pmod{15}$ , compute $\gcd(4-1,15)=\mathbf{3}$ and $\gcd(4+1,15)=\mathbf{5}$ . The order $r=4$ yields the factorization $15=3\times5$ .

2 · Factoring 21 with a = 2 (continued fractions genuinely needed)

Take $N=21$ , $a=2$ . Now the order will not divide the register size, so the peaks are smeared and continued fractions do real work.

Step 1. Register size: $\lceil\log_2 21\rceil=5$ , so $t=11$ and $2^t=2048\ge N^2=441$ . The order is $2,4,8,16,32\equiv11,64\equiv1$ , so $\mathbf{r=6}$ — and crucially $6\nmid 2048$ .

Step 2. The $s=1$ peak sits near $2^t/r=2048/6=341.33$ , so the register most likely returns $\mathbf{j=341}$ . Form $x=341/2048\approx0.16650$ .

Step 3. Run the Euclidean algorithm on $341/2048$ : the continued fraction is $[0;6,170,2]$ , with convergents $0/1,\ \mathbf{1/6},\ 170/1021,\ 341/2048$ . The convergent $1/6$ is the closest fraction of denominator below $N=21$ : $|341/2048-1/6|\approx1.6\times10^{-4}<1/2^{12}=2.4\times10^{-4}$ , inside the guaranteed window.

Step 4. Read $r=6$ from the denominator, with $\gcd(1,6)=1$ confirming the full order; check $2^6=64\equiv1\pmod{21}$ . Continued fractions recovered $r=6$ from a smeared peak no naive rounding could resolve.

Step 5. Shor's reduction: $r=6$ even, $a^{r/2}=2^3=8\not\equiv-1\pmod{21}$ , so $\gcd(7,21)=\mathbf{7}$ and $\gcd(9,21)=\mathbf{3}$ . The order $r=6$ yields $21=3\times7$ .

Physics of the portrait

Order finding is where a 350-year-old thread of number theory — Fermat's little theorem, Gauss's modular arithmetic, the structure of $(\mathbb{Z}/N\mathbb{Z})^\times$ — collided with quantum mechanics and produced the result that turned quantum computing from a curiosity into a strategic technology.

Origins · 1 minPeter Shor and how this was discovered

Peter Shor

b. 1959, American mathematician · quantum algorithms and factoring

Peter Williston Shor was a combinatorialist at Bell Labs when, in 1994, he did the thing that made quantum computing matter to governments: he showed a quantum computer could factor large integers in polynomial time. The pivot was recognizing that factoring reduces to order finding — an idea rooted in classical number theory, sharpened by Gary Miller's 1976 result under the extended Riemann hypothesis — and that order finding is a period-detection problem the quantum Fourier transform solves exponentially faster than any known classical method. Shor's insight was an architecture, not a trick: encode the period into the eigenphases of modular multiplication, extract them with phase estimation, and clean up the noisy rational with centuries-old continued fractions. The paper detonated the field, and worries that decoherence would make it unbuildable soon drove Shor to invent quantum error-correcting codes in 1995 — arguably a deeper contribution, since it showed fault-tolerant quantum computation is possible in principle. The shadow is long: it is why the world's cryptographic infrastructure is being rebuilt around post-quantum standards, and why order finding is taught as the canonical exponential quantum speedup.

History

1640

— Fermat states his little theorem, that a^(p−1) ≡ 1 mod p, the seed of multiplicative order

1801

— Gauss systematizes modular arithmetic and the group of units in Disquisitiones Arithmeticae

1976

— Miller shows integer factoring reduces to order finding under the extended Riemann hypothesis

1994

— Shor gives a polynomial-time quantum algorithm for order finding and factoring

2001

— IBM and Stanford factor 15 by NMR order finding, the first end-to-end demonstration

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, §5.3 (order finding and factoring) and Appendix 4 (continued fractions) · Mermin, Quantum Computer Science, Ch. 3 (period finding) · Kitaev, Shen & Vyalyi, Classical and Quantum Computation, §13 (abelian problems) · Preskill, Lecture Notes for Physics 219, Ch. 6 · Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM J. Comput. 26, 1484 (1997) · Watrous, quantum-complexity lecture notes.

Provenance. Structure and analysis follow Nielsen & Chuang §5.3: the eigenvector and eigenphase identities, the seed decomposition of $|1\rangle$ , and the continued-fraction recovery; complexity bounds cross-checked against Shor (1997) and Preskill Ch. 6. A verifier should recompute: (1) the eigenvalue equation $U_a|u_s\rangle=e^{2\pi is/r}|u_s\rangle$ by root-of-unity reindexing; (2) the seed identity $\tfrac{1}{\sqrt r}\sum_s|u_s\rangle=|1\rangle$ from geometric-series orthogonality; (3) the precision inequality forcing $2^t\ge N^2$ from the $1/N^2$ minimal gap; (4) the two worked examples — $N=15,\ a=7,\ r=4$ giving $15=3\times5$ , and $N=21,\ a=2,\ r=6$ with continued fraction $[0;6,170,2]$ giving $21=3\times7$ ; (5) the $4/\pi^2\approx0.405$ phase-estimation bound and the $\varphi(r)/r$ totient lower bound. All numerical results were checked programmatically.

Prerequisites. Quantum Phase Estimation · Quantum Fourier Transform · Hidden Subgroup Problem · Quantum Parallelism and the Oracle Model. Leads to. Shor's Factoring Algorithm · Quantum Discrete Logarithm Algorithm · Hidden Subgroup Problem · Simon's Algorithm.

Ask the tutor: Ask me to run the order-finding circuit on your own $N$ and $a$ — I will trace the peaks, do the continued fraction, and show exactly how the period falls out.

Is order finding the same thing as Shor's algorithm?

Not quite — order finding is the quantum engine, and Shor's algorithm is the full factoring machine around it. Shor's algorithm is mostly classical: pick a random $a$ coprime to $N$ , call order finding to get $r$ , and if $r$ is even with $a^{r/2}\not\equiv-1\pmod N$ , read a factor from $\gcd(a^{r/2}\pm1,N)$ . The only genuinely quantum step is finding $r$ ; everything else is classical number theory a laptop does instantly. So "Shor's algorithm" is order finding wrapped in a classical reduction that converts a period into a factor.

Why not just measure the target register after the modular exponentiation to read off the period?

You can, and it is illuminating, but it does not give $r$ directly. Measuring the target collapses it to some $a^{x_0}\bmod N$ , leaving the control register in an equal superposition over the progression $x_0, x_0+r, x_0+2r,\dots$ — periodic with period $r$ but shifted by an unknown offset $x_0$ . Applying the QFT then yields a multiple of $2^t/r$ , because the Fourier transform is blind to the offset (it only shifts phases). This "measure first" picture is exactly equivalent to the eigenvalue picture above, which is just cleaner because it isolates one phase $s/r$ per branch.

What makes order finding hard for a classical computer?

No classical shortcut to the period is known that avoids essentially exponential work. You can compute $a^k\bmod N$ quickly for any single $k$ , but finding the smallest $k$ with $a^k\equiv1$ seems to require searching candidates or knowing $\varphi(N)$ — and computing $\varphi(N)$ is itself equivalent to factoring $N$ . The best classical factoring algorithm, the number field sieve, runs in time roughly $\exp((\log N)^{1/3})$ , superpolynomial in the digits. The quantum advantage is that the Fourier transform reads global periodicity from a superposition in one shot, whereas classically you can only sample the sequence point by point, so the period of an exponentially long cycle stays hidden.

Where does the number-theoretic assumption enter that r is usually even and well-behaved?

It enters in Shor's classical reduction, not in order finding itself. Order finding returns whatever $r$ is; the reduction needs $r$ even and $a^{r/2}\not\equiv-1$ . A theorem guarantees that for a random $a$ coprime to an odd composite $N$ that is not a prime power, both conditions hold with probability at least $1/2$ (in fact $\ge 1-2^{-m}$ for $m$ distinct odd prime factors). So if a run gives a useless $r$ , pick a fresh $a$ and try again; a constant expected number of attempts suffices. Prime powers and even $N$ are stripped off first by cheap classical tests.

Why continued fractions specifically — is there no simpler way to round j over two to the t to s over r?

Naive rounding fails because you do not know $r$ , so you cannot tell which nearby fraction the measurement intends. The measured $x=j/2^t$ is close to $s/r$ but also to infinitely many fractions with larger denominators; you want the unique one with small denominator (below $N$ ) near $x$ . Continued fractions produce exactly the best rational approximations ordered by denominator size, and the theorem that any fraction within $1/2q^2$ of $x$ appears among its convergents turns "close" into "provably recovered." No simpler rounding rule carries that guarantee, and the smeared peaks when $r\nmid 2^t$ (as in the $N=21$ example) are precisely why you need it.

How does order finding generalize to period finding and the hidden subgroup problem?

Order finding is the special case where $f(x)=a^x\bmod N$ has period $r$ . The same circuit — uniform superposition, evaluate $f$ into a target, Fourier-transform the input, measure — finds the period of any efficiently computable periodic $f:\mathbb{Z}\to X$ . Recast group-theoretically, the periods form the hidden subgroup $r\mathbb{Z}$ of $\mathbb{Z}$ , and $f$ is constant on its cosets. Replacing $\mathbb{Z}$ by other abelian groups and the QFT by the Fourier transform over that group solves Simon's problem ( $\mathbb{Z}_2^n$ ), the discrete logarithm (a $\mathbb{Z}\times\mathbb{Z}$ period lattice), and the general finite abelian hidden subgroup problem — one template, many exponential speedups.