Shor's Factoring Algorithm

⚡ Key Takeaways

Shor's Algorithm is a quantum algorithm that factors an $n$ -bit integer $N$ in time polynomial in $n$ — specifically $O(n^2 \log n \log\log n)$ gate operations (with fast multiplication) — providing an exponential speedup over the best known classical algorithms. Discovered by Peter Shor in 1994, it reduces factoring to order-finding, solved efficiently using the Quantum Fourier Transform. Its existence threatens RSA, Diffie–Hellman, and elliptic-curve cryptography, motivating the field of post-quantum cryptography.

💡 The Core Insight

Factoring is hard, but periodicity detection is easy for quantum computers. The function $f(x) = a^x \bmod N$ is periodic with period $r$ (the order of $a$ ). A classical computer must evaluate $f$ at exponentially many points to detect this period, but a quantum computer evaluates $f$ on a superposition of all inputs simultaneously, then uses the Quantum Fourier Transform to interfere those amplitudes so that measuring the output yields information about $1/r$ . Once $r$ is known (and even, with $a^{r/2}\not\equiv -1$ ), the factors emerge from $\gcd(a^{r/2}\pm 1, N)$ . The quantum speedup lives entirely in the period-finding subroutine; everything else is classical number theory.

DefinitionOrder / Multiplicative Order

Let $N$ be a positive integer and $a$ an integer coprime to $N$ , $\gcd(a,N)=1$ . The multiplicative order of $a$ modulo $N$ is the least positive integer $r$ such that

1

\quad a^r \equiv 1 \pmod N.

Derivation hint: Existence follows because the map $x \mapsto ax \bmod N$ permutes the finite group $(\mathbb{Z}/N\mathbb{Z})^\times$ , so some power must return to the identity; minimality defines $r$ . The element $a$ generates a cyclic subgroup $\langle a\rangle$ of order $r$ inside $(\mathbb{Z}/N\mathbb{Z})^\times$ , and $r \mid \varphi(N)$ where $\varphi$ is Euler's totient.

TheoremFactoring via Order-Finding

Let $N$ be an odd composite integer that is not a prime power. Choose $a$ uniformly at random from $\{2,\dots,N-1\}$ with $\gcd(a,N)=1$ , and let $r$ be its order. Then with probability at least $1/2$ (over the choice of $a$ ):

2

\quad r \text{ is even} \quad\text{and}\quad a^{r/2} \not\equiv -1 \pmod N.

Derivation hint: Using the Chinese Remainder Theorem decompose $(\mathbb{Z}/N\mathbb{Z})^\times \cong \prod (\mathbb{Z}/p_i^{e_i}\mathbb{Z})^\times$ and bound the fraction of elements whose order is odd or whose half-power is $-1$ ; each prime-power factor contributes at most a factor $1/2$ . When [2] holds, set $x = a^{r/2} \bmod N$ . Then $x^2 \equiv 1 \pmod N$ but $x \not\equiv \pm 1$ , so

3

\quad N \mid (x-1)(x+1), \quad N \nmid (x-1), \quad N \nmid (x+1),

Derivation hint: $a^r - 1 = (a^{r/2}-1)(a^{r/2}+1)\equiv 0$ . Since $x\neq\pm1 \bmod N$ , neither factor is divisible by all of $N$ , so the common factors split. and therefore $\gcd(x-1, N)$ is a nontrivial factor of $N$ .

DefinitionQuantum Fourier Transform

The Quantum Fourier Transform on $\mathbb{Z}/2^t\mathbb{Z}$ acts on basis states $|x\rangle$ ( $0\le x<2^t$ ) by

4

\quad \mathrm{QFT}\,|x\rangle = \frac{1}{\sqrt{2^t}}\sum_{y=0}^{2^t-1} e^{2\pi i\, x y / 2^t}\,|y\rangle.

Derivation hint: This is the discrete Fourier transform unitarized; the prefactor $2^{-t/2}$ ensures the map preserves norm, and the kernel is the $2^t$ -th root of unity raised to $xy$ . It is implemented with $O(t^2)$ Hadamard and controlled-phase gates via the product (tensor-factored) form of the transform.

ProofOrder-Finding via Phase Estimation

Setup. Choose $t$ such that $N^2 \le 2^t < 2N^2$ (a "counting" register of $t$ qubits) and a "work" register of $\lceil\log_2 N\rceil$ qubits.

Step 1 — Uniform superposition. Apply Hadamards to the counting register:

5

\quad |0\rangle|0\rangle \;\longmapsto\; \frac{1}{\sqrt{2^t}}\sum_{x=0}^{2^t-1}|x\rangle\,|0\rangle.

Derivation hint: $H^{\otimes t}|0\rangle^{\otimes t} = 2^{-t/2}\sum_x |x\rangle$ , the equal superposition over all computational basis states.

Step 2 — Modular exponentiation. Apply the reversible unitary $U_f:|x\rangle|0\rangle\mapsto|x\rangle|a^x\bmod N\rangle$ :

6

\quad \frac{1}{\sqrt{2^t}}\sum_{x=0}^{2^t-1}|x\rangle\,|a^x\bmod N\rangle.

Derivation hint: Implemented by repeated squaring — $a^x = \prod_k (a^{2^k})^{x_k}$ — each controlled modular multiplication costing $O(n^2)$ gates, $O(n)$ of them.

Step 3 — Measure (or trace out) the work register. This collapses to a coset: for some random $x_0\in\{0,\dots,r-1\}$ ,

7

\quad |\psi\rangle = \frac{1}{\sqrt{M}}\sum_{j=0}^{M-1}|x_0 + jr\rangle, \qquad M = \Big\lceil \frac{2^t - x_0}{r}\Big\rceil,

Derivation hint: All $x$ with the same value $a^x \bmod N$ differ by multiples of $r$ ; conditioning on the measured value $a^{x_0}$ leaves exactly the arithmetic progression $x_0, x_0+r, \dots$ .

Step 4 — Apply the QFT to the counting register. The amplitude on $|y\rangle$ is

8

\quad \langle y|\mathrm{QFT}|\psi\rangle = \frac{1}{\sqrt{M\,2^t}}\sum_{j=0}^{M-1} e^{2\pi i (x_0+jr)y/2^t}.

Derivation hint: Apply [4] term-by-term; the phase factor $e^{2\pi i x_0 y/2^t}$ is a global phase per fixed $y$ and drops out of the probability.

Step 5 — Constructive interference. The geometric sum over $j$ is large precisely when $ry/2^t$ is near an integer, i.e. $y \approx k\,2^t/r$ for integer $k$ . The probability concentrates:

9

\quad \Pr[y] = \frac{1}{M\,2^t}\left|\frac{\sin(\pi M r y/2^t)}{\sin(\pi r y/2^t)}\right|^2,

Derivation hint: Sum the finite geometric series $\sum_j z^j = (z^M-1)/(z-1)$ with $z=e^{2\pi i ry/2^t}$ and take the squared modulus, yielding the Dirichlet (Fejér) kernel.

Step 6 — Continued fractions. Measure $y$ . With probability $\Omega(1/\log\log r)$ , $|y/2^t - k/r| \le 1/2^{t+1} \le 1/(2N^2) < 1/(2r^2)$ . Since $k/r$ is a fraction with denominator $< N$ , it is the unique such fraction within $1/(2r^2)$ , recoverable from $y/2^t$ by the continued fraction expansion, yielding $r$ (after dividing out $\gcd(k,r)$ ).

Step 7 — Verify and repeat. Check $a^r \equiv 1 \pmod N$ . If $r$ is odd or $a^{r/2}\equiv -1$ , choose a new $a$ . A constant number of repetitions succeeds with overwhelming probability. $\qquad\blacksquare$

∎

⚠️ Common mistake

Step 6 may return only a divisor of $r$ (when $\gcd(k,r)>1$ ) or fail when $k=0$ . Standard fixes: take the least common multiple of denominators from two independent runs, or test small multiples $r, 2r, 3r,\dots$ . The success probability per run is bounded below by a constant (after accounting for these losses), so $O(1)$ or $O(\log\log N)$ runs suffice.

Figure

Schematic of Shor's order-finding circuit and the post-QFT probability peaks at multiples of

2^t/r

.

mathematician · Peter Williston Shor | b. 1959

Peter Shor, an applied mathematician at Bell Labs (later MIT), introduced the factoring and discrete-logarithm algorithms in his landmark 1994 FOCS paper "Algorithms for Quantum Computation: Discrete Logarithms and Factoring." Trained in combinatorics and probability, Shor recognized that the hidden-subgroup structure underlying period-finding could be exposed by the quantum Fourier transform — building conceptually on Simon's problem and Deutsch–Jozsa. He also pioneered quantum error correction (the 9-qubit Shor code, 1995), making fault-tolerant quantum computation conceivable and thereby giving his algorithm physical plausibility. He received the Nevanlinna Prize (1998) and the Gödel Prize, and his work catalyzed both quantum computing as a field and the entire post-quantum cryptography enterprise.

🧠 Intuition

Imagine the modular exponential function $f(x)=a^x \bmod N$ as a striped tablecloth: it repeats with period $r$ , but $r$ is hidden among exponentially many columns. A classical observer can only lift the cloth at one spot at a time. The quantum computer instead lifts the entire cloth into a superposition. After measuring the work register, you're left not with a single column but with a perfectly periodic "comb" of positions $x_0, x_0+r, x_0+2r,\dots$ — though you cannot read it directly, because measuring would give one random tooth. The QFT acts like a prism: a periodic comb of spacing $r$ in the input transforms into a new comb of spacing $2^t/r$ in the output, and crucially the random offset $x_0$ becomes an unobservable global phase. So measuring the QFT output samples near integer multiples of $2^t/r$ , and the continued-fraction algorithm reads off $r$ from any one of them. The whole trick is converting "find a hidden period" — exponentially hard classically — into "find the spacing of bright fringes," which interference does for free.

IP

Interference picture

Physically, this is a multi-slit diffraction experiment. The collapsed state [7] is an array of "slits" at positions spaced $r$ apart. The QFT is the propagation to the far field (Fraunhofer regime). Constructive interference produces bright fringes exactly where the path-phase $2\pi r y/2^t$ is a multiple of $2\pi$ — at $y=k\,2^t/r$ . The width of each fringe shrinks as $1/M\sim r/2^t$ , so choosing $2^t\ge N^2$ makes the peaks sharp enough that the nearest fraction $k/r$ is uniquely resolvable. Quantum factoring is, at heart, diffraction grating spectroscopy of an arithmetic period.

ExampleFactoring N = 15 with a = 7

Given: $N=15$ , choose $a=7$ (coprime to 15).

Find the order: $7^1=7,\ 7^2=49\equiv 4,\ 7^3\equiv 28\equiv 13,\ 7^4\equiv 91\equiv 1 \pmod{15}$ . So $r=4$ .

Check conditions [2]: $r=4$ is even ✓. $a^{r/2}=7^2=49\equiv 4 \pmod{15}$ , and $4\not\equiv -1\equiv 14$ ✓.

Extract factors via [3]:

$\gcd(a^{r/2}-1,\,N)=\gcd(4-1,15)=\gcd(3,15)=3.$
$\gcd(a^{r/2}+1,\,N)=\gcd(4+1,15)=\gcd(5,15)=5.$

Quantum side (sanity check): with $t=8$ so $2^t=256$ , the QFT peaks at $y\approx k\cdot 256/4 = 0, 64, 128, 192$ . Measuring $y=192$ gives $192/256 = 3/4$ ; continued fractions yield denominator $r=4$ . ✓

\boxed{15 = 3 \times 5}

ExampleFactoring N = 21 with a = 2

Given: $N=21$ , choose $a=2$ ( $\gcd(2,21)=1$ ).

Find the order: $2^1=2,\ 2^2=4,\ 2^3=8,\ 2^4=16,\ 2^5\equiv 32\equiv 11,\ 2^6\equiv 22\equiv 1 \pmod{21}$ . So $r=6$ .

Check conditions [2]: $r=6$ even ✓. $a^{r/2}=2^3=8$ , and $8\not\equiv -1\equiv 20$ ✓.

Extract factors via [3]:

$\gcd(8-1,21)=\gcd(7,21)=7.$
$\gcd(8+1,21)=\gcd(9,21)=3.$

Quantum side: with $2^t=512$ , peaks at $y\approx k\cdot 512/6 \approx 0, 85.3, 170.7, 256, \dots$ . Measuring $y=85$ gives $85/512\approx 0.1660$ ; continued fraction $[0;6,42,\dots]$ yields convergent $1/6$ , so $r=6$ . ✓

\boxed{21 = 3 \times 7}

⚠️ Common mistake

"Shor's algorithm tries all factors in parallel." No — quantum parallelism alone is useless because measurement returns a single random outcome. The power comes from interference engineered by the QFT, which concentrates amplitude on outcomes encoding $r$ . Naive superposition without the Fourier step would just yield a uniformly random $a^x$ , conveying nothing about the period.

⚠️ Common mistake

"It directly factors $N$ ." The quantum subroutine never factors anything; it finds the order $r$ . All the factoring happens in classical post-processing through GCD computations [3]. The reduction (order-finding → factoring) is pure number theory, predating quantum computing.

CounterexampleWhen the lucky-condition fails

Take $N=15$ , $a=14\equiv -1$ . Then $a^2 = 196 \equiv 1 \pmod{15}$ , so $r=2$ (even). But $a^{r/2}=a^1 = 14 \equiv -1 \pmod{15}$ — condition [2] fails. Computing $\gcd(14-1,15)=\gcd(13,15)=1$ and $\gcd(14+1,15)=\gcd(15,15)=15$ : both trivial. The algorithm learns nothing and must restart with a fresh $a$ . This is exactly the "bad $a$ " case that Theorem [2] bounds to probability $\le 1/2$ .

⚠️ Common mistake

Preconditions matter. Before running, classically dispose of easy cases: if $N$ is even, return 2; if $N=p^k$ is a perfect power, find $p$ by testing $k$ -th roots; if $\gcd(a,N)>1$ you already have a factor. Shor's quantum core is invoked only on odd composites with at least two distinct prime factors.

connection

Shor's algorithm is the flagship instance of the abelian <span class="wiki-link-missing">Hidden Subgroup Problem</span>: order-finding is HSP over $\mathbb{Z}$ , and the same QFT machinery solves the Discrete Logarithm Problem (breaking Diffie–Hellman and ECC). Its period-finding kernel generalizes Simon's Algorithm (HSP over $(\mathbb{Z}/2)^n$ ). The order-finding subroutine is precisely Quantum Phase Estimation applied to the modular-multiplication unitary $U_a|y\rangle=|ay\bmod N\rangle$ , whose eigenvalues are $e^{2\pi i k/r}$ . The classical reduction relies on the Chinese Remainder Theorem and Continued Fractions, while implementation cost is dominated by reversible Modular Exponentiation circuits.

🔬 Where this appears

⏳ History

- 1980–1985 — Benioff, Feynman, and Deutsch lay theoretical foundations of quantum computation; Deutsch defines the universal quantum Turing machine.

- 1992 — Deutsch–Jozsa algorithm gives the first exponential (deterministic) quantum–classical separation, albeit for an artificial problem.

- 1993 — Bernstein–Vazirani and the formalization of quantum query complexity sharpen the notion of quantum advantage.

- 1994 — Daniel Simon presents Simon's problem with an exponential speedup; its period-finding structure directly inspires Shor.

- 1994 (Nov) — Peter Shor announces the polynomial-time factoring and discrete-log algorithms at FOCS; published in full in SIAM J. Comput. 1997.

- 1995 — Shor introduces the 9-qubit quantum error-correcting code, showing fault tolerance is in principle possible — making the algorithm physically relevant.

- 1996–1998 — Kitaev reframes the method via quantum phase estimation and the eigenvalue/HSP perspective; Coppersmith analyzes the approximate QFT.

- 2001 — IBM and Stanford factor

N=15

on a 7-qubit NMR quantum computer (Vandersypen et al.), the first experimental demonstration.

- 2012–2019 — Photonic and superconducting demonstrations; Gidney–Ekerå (2019) estimate ~20 million qubits / 8 hours to break RSA-2048, refining the resource picture.

open-problem

Resource gap and noise. No quantum computer has factored a number that resists classical methods; demonstrations are tiny and often compiled with knowledge of the answer. The decisive obstacle is fault tolerance — Shor's algorithm needs millions of physical qubits and deep, coherent circuits, far beyond NISQ-era hardware.

Classical lower bounds. It remains unproven that factoring is classically hard. The best classical algorithm, the General Number Field Sieve, runs in $\exp\!\big(O((\log N)^{1/3}(\log\log N)^{2/3})\big)$ — sub-exponential but super-polynomial — yet no proof rules out a polynomial-time classical factoring algorithm. Thus Shor's speedup is conditional on this folklore hardness.

HSP frontier. Order-finding is the abelian HSP, fully solved by the QFT. The non-abelian Hidden Subgroup Problem (e.g. the dihedral group, linked to lattice problems, and the symmetric group, linked to graph isomorphism) resists efficient quantum solution; whether Shor-style techniques extend there is a major open question with cryptographic stakes for post-quantum schemes.

Formal Statement

Why It Holds — The Algorithm and Its Analysis

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also