Part IV. Protocols and Algorithms · Chapter 33

Shor as Period Finding

Shor's algorithm factors numbers by finding a period, and holding that one reduction clearly in mind tells you both why the algorithm matters and why it is so hard to build.

Steven GellerPublished July 25, 2026Revised August 14, 2026

Lab

In this chapter 9 sections

Reader question. How does Shor's algorithm reduce factoring to period finding, and where does the quantum speedup enter?

Classical preprocessing chooses a coprime base, quantum phase estimation/Fourier sampling estimates the period of modular exponentiation, and continued fractions plus gcd calculations recover factors when number-theoretic conditions succeed; the quantum advantage is in period finding, with substantial reversible arithmetic and fault-tolerant cost.

Scope and non-goals.

This chapter does not imply every base succeeds, that the quantum circuit outputs factors directly, or that textbook query complexity equals a near-term runtime.
It does not make current cryptographic migration estimates without dated resource assumptions.

Figure 33.1. Notice how small the quantum region is: a single period-finding subroutine, with classical number theory before and after; and a retry loop, because some runs return a period you cannot use.

Factoring becomes an order-finding task

Derive why an even period can expose nontrivial gcds.

Peter Shor published his factoring algorithm in 1994, and the first thing to understand about it is that the quantum computer never factors anything. The algorithm reduces factoring to a different problem: given an integer $N$ and a randomly chosen $a$ , find the period of modular exponentiation; the smallest $r$ such that

a^r\bmod N=1

If $r$ is even and $a^{r/2}$ is not congruent to $− 1$ mod $N$ , then $\gcd(a^{r/2}-1,N)$ and $\gcd(a^{r/2}+1,N)$ reveal nontrivial factors. That reduction is classical number theory. The quantum contribution is finding $r$ efficiently, and there is no known classical method that keeps up.

Evidence boundary. Shor's algorithm factors integers in polynomial time by reducing factoring to quantum order finding. [Peter W. Shor] [Michael A. Nielsen]

N=15 shows every classical branch

Choose a=2, compute powers, and recover factors from r=4.

For N=15 and a=2, modular powers 1,2,4,8 repeat after r=4. Because r is even and 2^(r/2)=4 is not -1 modulo 15, gcd(4-1,15)=3 and gcd(4+1,15)=5. A complete trace also records easy failures: a shares a factor with N, the recovered period is odd, or the half-period power is -1.

Evidence boundary. Quantum Fourier sampling/phase estimation estimates rational phases related to the order. [Peter W. Shor] [Don Coppersmith]

Modular exponentiation is the quantum workload

Specify the reversible unitary and its register costs.

The full algorithm is a pipeline with exactly one quantum stage:

Choose a random $a$ less than $N$ .
Compute $gcd ( a , N )$ classically; if it exceeds 1, you already have a factor and can stop.
Estimate the period $r$ of $a x mod N$ using quantum phase estimation on the modular-exponentiation unitary.
Use classical continued fractions to convert the phase estimate into a candidate $r$ .
Compute the candidate factors with $gcd$ and verify them; if the period was odd or unhelpful, retry with a new $a$ .

The precision question from the previous chapter is now a security-relevant number:

\text{resolution}\approx2^{-m}

Cryptographic-scale instances need enough counting qubits to resolve the period and controlled modular exponentiation deep enough to reach it. Toy examples demonstrate the structure beautifully; they establish nothing about near-term capability against real keys.

Evidence boundary. Practical resource estimates are dominated by reversible modular arithmetic and fault-tolerant overhead. [Craig Gidney] [National Academies of Sciences]

N composite; a coprime base; order r; modular exponentiation U_a|x>=|ax mod N>; fractions k/r; bit precision declared.

Phase estimation reveals a rational multiple

Connect measured fractions to r with continued fractions.

The quantum register samples a value near j 2^m/r. Continued fractions converts y/2^m into a candidate denominator, which must be checked by modular exponentiation. Finite precision may yield a divisor or unusable convergent; repeated samples and least-common-multiple logic recover the period with bounded probability. The classical validation step is part of correctness, not cleanup.

Failure branches and retries

Handle odd periods, trivial square roots, and unlucky samples.

Shor is a stack, and every layer is a potential bottleneck:

the number-theoretic reduction from factoring to period finding;
reversible circuits for modular exponentiation;
phase estimation at the required precision;
the QFT and inverse QFT;
classical continued fractions and verification;
error correction underneath all of it;
resource estimation across qubits, depth, and runtime.

The mathematics has been sound since 1994. The open question is engineering: each layer must survive contact with a real, noisy machine, and the layers multiply. A full-stack view is mandatory for any security or investment judgment that invokes this algorithm.

Resource account: from logical arithmetic to physical execution

Separate theorem, circuit, and fault-tolerant estimate.

Order-finding resource layers that must not be collapsed
Layer	Reported quantity	Verification
Query theorem	Controlled modular-multiplication uses under the selected phase-estimation construction	Promise and success probability stated.
Logical circuit	Register width, modular-arithmetic gates, non-Clifford count, depth, ancillas, and retries	Candidate period checked classically.
Fault-tolerant execution	Code distance, physical qubits, factory throughput, cycle time, and wall time	Assumptions tied to an explicit error budget.
Classical wrapper	GCD, continued fractions, least-common multiples, and failed-base retries	All branches retained in the run record.

The order-finding circuit needs coherent modular exponentiation, controlled arithmetic, inverse QFT, and enough precision to recover r. Logical gate counts depend on the arithmetic design and can be dominated by non-Clifford operations; physical cost additionally depends on code distance, factory throughput, routing, and cycle time. Small-N demonstrations do not validate that full resource chain.

Order-finding end-to-end notebook

Acceptance contract for Order-finding end-to-end notebook
Field	Reader-visible record
Format	Classical/quantum small-N trace with reversible-cost and continued-fraction logs
Verification	Tests multiple bases for N=15 and 21, verifies periods and gcd recovery, records failure/retry branches, and reconciles quantum samples with classical post-processing.
Availability	Source-embedded acceptance record; no separate download is claimed

{
  "artifact": "Order-finding end-to-end notebook",
  "format": "Classical/quantum small-N trace with reversible-cost and continued-fraction logs",
  "acceptance_test": "Tests multiple bases for N=15 and 21, verifies periods and gcd recovery, records failure/retry branches, and reconciles quantum samples with classical post-processing.",
  "publication_state": "source-embedded contract and worked fixture"
}

Executable reference fixture

Run with Python 3.11 or later. The final assertion is the chapter-level pass condition for this small instance.

from math import gcd

def period_trace(modulus, base):
    if modulus < 3 or not 1 < base < modulus or gcd(modulus, base) != 1:
        raise ValueError("base must be nontrivial and coprime to modulus")
    values, current = [], 1
    while current not in values:
        values.append(current)
        current = current * base % modulus
    return {"period": len(values), "orbit": values}

def factor_from_period(modulus, base):
    trace = period_trace(modulus, base)
    period = trace["period"]
    if period % 2 or pow(base, period // 2, modulus) == modulus - 1:
        return {**trace, "factors": set()}
    factors = {gcd(pow(base, period // 2) - 1, modulus),
               gcd(pow(base, period // 2) + 1, modulus)} - {1, modulus}
    return {**trace, "factors": factors}

fifteen = factor_from_period(15, 2)
twenty_one = factor_from_period(21, 2)
invalid_rejected = False
try:
    factor_from_period(15, 3)
except ValueError:
    invalid_rejected = True
assert fifteen["period"] == 4 and fifteen["factors"] == {3, 5}
assert twenty_one["period"] == 6 and twenty_one["factors"] == {3, 7}
assert invalid_rejected
print(f"PASS: 33 period finding N15_r={fifteen['period']} factors={sorted(fifteen['factors'])} N21_r={twenty_one['period']} factors={sorted(twenty_one['factors'])}")

Scope boundary

This chapter does not imply every base succeeds, that the quantum circuit outputs factors directly, or that textbook query complexity equals a near-term runtime.
It does not make current cryptographic migration estimates without dated resource assumptions.

Depth commitment. One N=15 trace, one N=21 exercise, one phase sample, retries, and one sourced resource comparison.

Practice problem

For N=21, test bases a=2,4,5; compute orders, identify successful factor-recovery conditions, and trace one phase-estimation sample through continued fractions.

N=21; bases a in {2,4,5}.
For the continued-fraction branch use a=2, six phase bits, and measured y=11; analyze y/64.

Deliverable: Classical power tables, success/failure labels, one rational reconstruction, gcd outputs, and a resource boundary.
Pass condition: The notebook reproduces each order and factor, checks failed conditions, and validates the continued-fraction convergent.

Verification record

Expected solution form. Complete N=21 order-finding dossier with executable arithmetic.

Model answer. For N=21, base 2 has order 6 and yields gcd(2^3-1,21)=7 and gcd(2^3+1,21)=3. Base 4 has odd order 3; base 5 has order 6 but 5^3=-1 mod 21, so both branches fail. The convergent 1/6 from 11/64 identifies the successful period candidate for base 2.

Model result and check. CI reruns modular powers, gcds, convergents, and the declared branch outcomes.

Acceptance test. The notebook reproduces each order and factor, checks failed conditions, and validates the continued-fraction convergent.

Companion work

Artifacts for this chapter

These entries resolve to checked-in local source. Commands are reproduced exactly from the chapter manifest, and source-embedded fixtures are exported as direct downloads.

algorithm fixture
Order-finding end-to-end notebook
Download fixture (.py)Verification record (.json)
Reproduce or test
python3 tools/validate_briefs.py --briefs data/editorial_briefs_00_35.json --from 0 --through 35 --check-rewritten-sources --execute-artifacts

Provenance

Sources and review

The load-bearing claims in the chapter are mapped inline to this registered source set. A citation supports only the bounded claim beside it.

External review: Open.

How review works Revision history Report or inspect errata

Book contents

Part IV. Protocols and Algorithms

Shor as Period Finding

Factoring becomes an order-finding task

N=15 shows every classical branch

Modular exponentiation is the quantum workload

Phase estimation reveals a rational multiple

Failure branches and retries

Resource account: from logical arithmetic to physical execution

Order-finding end-to-end notebook

Artifacts for this chapter

Order-finding end-to-end notebook

Sources and review

Cite this chapter

Factoring becomes an order-finding task#

N=15 shows every classical branch#

Modular exponentiation is the quantum workload#

Phase estimation reveals a rational multiple#

Failure branches and retries#

Resource account: from logical arithmetic to physical execution#

Order-finding end-to-end notebook#

Artifacts for this chapter

Order-finding end-to-end notebook

Sources and review

Prerequisites for this chapter

Next concepts from this chapter

Factoring becomes an order-finding task

N=15 shows every classical branch

Modular exponentiation is the quantum workload

Phase estimation reveals a rational multiple

Failure branches and retries

Resource account: from logical arithmetic to physical execution

Order-finding end-to-end notebook