Shor's Factoring Algorithm

Shor's Algorithm is a quantum algorithm that factors an

n

-bit integer

N

in time polynomial in

n

— specifically

O (n^{2} lo g n lo g lo g 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.

Shor's algorithm solves the integer factorization problem: given a composite integer $N$ , find a nontrivial factor. The classical hardness of this problem underlies the RSA cryptosystem. The algorithm's central move is a reduction — factoring is achieved by finding the multiplicative order $r$ of a randomly chosen $a$ modulo $N$ , i.e., the least $r > 0$ with $a^{r} \equiv 1 (mod N)$ . This order-finding is performed by preparing a superposition over exponents, applying modular exponentiation, and using the quantum Fourier transform to extract the period $r$ via continued fractions. The surprising fact is that a problem believed to require super-polynomial classical effort collapses to polynomial time on a quantum computer — the first compelling evidence that quantum computation is qualitatively more powerful for a problem of genuine practical importance.

The Core Insight

Factoring is hard, but periodicity detection is easy for quantum computers. The function $f (x) = a^{x} mod 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} \neq \equiv - 1$ ), the factors emerge from $g cd (a^{r /2} \pm 1, N)$ . The quantum speedup lives entirely in the period-finding subroutine; everything else is classical number theory.

Formal Statement

Order / Multiplicative Order

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

a^{r} \equiv 1 (mod N) .

⟳Existence follows because the map

x \mapsto a x mod N

permutes the finite group

(Z / N Z)^{\times}

, so some power must return to the identity; minimality defines

r

The element $a$ generates a cyclic subgroup $⟨ a ⟩$ of order $r$ inside $(Z / N Z)^{\times}$ , and $r ∣ φ (N)$ where $φ$ is Euler's totient.

Factoring 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 $g cd (a, N) = 1$ , and let $r$ be its order. Then with probability at least $1/2$ (over the choice of $a$ ):

r is even and a^{r /2} \neq \equiv - 1 (mod N) .

⟳Using the Chinese Remainder Theorem decompose

(Z / N Z)^{\times} ≅ \prod (Z / p_{i}^{e_{i}} 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} mod N$ . Then $x^{2} \equiv 1 (mod N)$ but $x \neq \equiv \pm 1$ , so

N ∣ (x - 1) (x + 1), N ∤ (x - 1), N ∤ (x + 1),

⟳

a^{r} - 1 = (a^{r /2} - 1) (a^{r /2} + 1) \equiv 0

. Since

x \neq = \pm 1 mod N

, neither factor is divisible by all of

N

, so the common factors split.

and therefore $g cd (x - 1, N)$ is a nontrivial factor of $N$ .

Quantum Fourier Transform

The Quantum Fourier Transform on $Z / 2^{t} Z$ acts on basis states $∣ x ⟩$ ( $0 \leq x < 2^{t}$ ) by

QFT ∣ x ⟩ = \frac{1}{2 ^{t}} y = 0 \sum 2^{t} - 1 e^{2 π i x y / 2^{t}} ∣ y ⟩ .

⟳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

x y

It is implemented with $O (t^{2})$ Hadamard and controlled-phase gates via the product (tensor-factored) form of the transform.

Why It Holds — The Algorithm and Its Analysis

Order-Finding via Phase Estimation

Setup. Choose

t

such that

N^{2} \leq 2^{t} < 2 N^{2}

(a "counting" register of

t

qubits) and a "work" register of

⌈ lo g_{2} N ⌉

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

∣0 ⟩ ∣0 ⟩ ⟼ \frac{1}{2 ^{t}} x = 0 \sum 2^{t} - 1 ∣ x ⟩ ∣0 ⟩ .

⟳

H^{\otimes t} ∣0 ⟩^{\otimes t} = 2^{- t /2} \sum_{x} ∣ x ⟩

, the equal superposition over all computational basis states.

Step 2 — Modular exponentiation. Apply the reversible unitary

U_{f} : ∣ x ⟩ ∣0 ⟩ \mapsto ∣ x ⟩ ∣ a^{x} mod N ⟩

\frac{1}{2 ^{t}} x = 0 \sum 2^{t} - 1 ∣ x ⟩ ∣ a^{x} mod N ⟩ .

⟳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}

∣ ψ ⟩ = \frac{1}{M} j = 0 \sum M - 1 ∣ x_{0} + j r ⟩, M = ⌈ \frac{2 ^{t} - x _{0}}{r} ⌉,

⟳All

x

with the same value

a^{x} mod 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 ⟩

⟨ y ∣ QFT ∣ ψ ⟩ = \frac{1}{M 2 ^{t}} j = 0 \sum M - 1 e^{2 π i (x_{0} + j r) y / 2^{t}} .

⟳Apply [4] term-by-term; the phase factor

e^{2 π 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

r y / 2^{t}

is near an integer, i.e.

y \approx k 2^{t} / r

for integer

k

. The probability concentrates:

Pr [y] = \frac{1}{M 2 ^{t}} \frac{sin ( π M r y / 2 ^{t} )}{sin ( π r y / 2 ^{t} )}^{2},

⟳Sum the finite geometric series

\sum_{j} z^{j} = (z^{M} - 1) / (z - 1)

with

z = e^{2 π i r y / 2^{t}}

and take the squared modulus, yielding the Dirichlet (Fejér) kernel.

Step 6 — Continued fractions. Measure

y

. With probability

Ω (1/ lo g lo g r)

∣ y / 2^{t} - k / r ∣ \leq 1/ 2^{t + 1} \leq 1/ (2 N^{2}) < 1/ (2 r^{2})

. Since

k / r

is a fraction with denominator

< N

, it is the unique such fraction within

1/ (2 r^{2})

, recoverable from

y / 2^{t}

by the continued fraction expansion, yielding

r

(after dividing out

g cd (k, r)

). Step 7 — Verify and repeat. Check

a^{r} \equiv 1 (mod N)

. If

r

is odd or

a^{r /2} \equiv - 1

, choose a new

a

. A constant number of repetitions succeeds with overwhelming probability.

■

Step 6 may return only a divisor of $r$ (when $g cd (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, 2 r, 3 r, \dots$ . The success probability per run is bounded below by a constant (after accounting for these losses), so $O (1)$ or $O (lo g lo g N)$ runs suffice.

Schematic of Shor's order-finding circuit and the post-QFT probability peaks at multiples of $2^t/r$.

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.

Building Intuition

Imagine the modular exponential function $f (x) = a^{x} mod 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} + 2 r, \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.

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 π r y / 2^{t}$ is a multiple of $2 π$ — at $y = k 2^{t} / r$ . The width of each fringe shrinks as $1/ M \sim r / 2^{t}$ , so choosing $2^{t} \geq 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.

Worked Examples

Factoring 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 (mod 15)

. So

r = 4

. Check conditions [2]:

r = 4

is even ✓.

a^{r /2} = 7^{2} = 49 \equiv 4 (mod 15)

, and

4 \neq \equiv - 1 \equiv 14

✓. Extract factors via [3]:

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

Quantum side (sanity check): with

t = 8

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

. ✓

15 = 3 \times 5

Factoring N = 21 with a = 2

Given:

N = 21

, choose

a = 2

(

g cd (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 (mod 21)

. So

r = 6

. Check conditions [2]:

r = 6

even ✓.

a^{r /2} = 2^{3} = 8

, and

8 \neq \equiv - 1 \equiv 20

✓. Extract factors via [3]:

$g cd (8 - 1, 21) = g cd (7, 21) = 7.$
$g cd (8 + 1, 21) = g cd (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

. ✓

21 = 3 \times 7

Common Misconceptions

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

When the lucky-condition fails

Take $N = 15$ , $a = 14 \equiv - 1$ . Then $a^{2} = 196 \equiv 1 (mod 15)$ , so $r = 2$ (even). But $a^{r /2} = a^{1} = 14 \equiv - 1 (mod 15)$ — condition [2] fails. Computing $g cd (14 - 1, 15) = g cd (13, 15) = 1$ and $g cd (14 + 1, 15) = g cd (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 $\leq 1/2$ .

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

g cd (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.

Connections

Shor's algorithm is the flagship instance of the abelian Hidden Subgroup Problem: order-finding is HSP over $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 $(Z /2)^{n}$ ). The order-finding subroutine is precisely Quantum Phase Estimation applied to the modular-multiplication unitary $U_{a} ∣ y ⟩ = ∣ a y mod N ⟩$ , whose eigenvalues are $e^{2 π ik / r}$ . The classical reduction relies on the Chinese Remainder Theorem and Continued Fractions, while implementation cost is dominated by reversible Modular Exponentiation circuits.

Real-World Applications

Breaking RSA. RSA-2048 security rests on the difficulty of factoring a 2048-bit modulus; a fault-tolerant quantum computer running Shor's algorithm would recover the private key. Estimates suggest ~20 million noisy physical qubits (Gidney–Ekerå, 2019) — large but finite.
Breaking Diffie–Hellman and ECC. Via the discrete-log variant, Shor's method defeats elliptic-curve cryptography (ECDSA, used in Bitcoin and TLS) and classical Diffie–Hellman key exchange.
Driving post-quantum cryptography (PQC). NIST's standardization of lattice- and hash-based schemes (CRYSTALS-Kyber, Dilithium, SPHINCS+, 2022–2024) is a direct response to Shor's threat.
"Harvest now, decrypt later" defense. Governments and enterprises migrate to PQC today because encrypted traffic captured now could be broken once large quantum computers exist.
Benchmarking quantum hardware. Small instances ( $N = 15, 21, 35$ ) have been demonstrated on NMR, photonic, ion-trap, and superconducting platforms as proof-of-principle and as integration tests (though several "demonstrations" used precompiled shortcuts).
Cryptographic agility standards. IETF and TLS 1.3 hybrid key-exchange (X25519 + Kyber) deployments by Google, Cloudflare, and Apple are motivated by the Shor threat model.
Resource-estimation research. Shor's algorithm is the canonical workload for surface-code overhead, magic-state distillation, and logical-qubit cost analyses in fault-tolerant architecture design.

Historical Development

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.

Subtleties & Limits

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 (O ((lo g N)^{1/3} (lo g lo g N)^{2/3}))

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