Shor's Factoring Algorithm

Shor's algorithm does not factor $N$ directly. Instead it reduces factoring to order-finding: given $N$ and an integer $a$ coprime to $N$, find the smallest positive integer $r$ (the multiplicative order of $a$ modulo $N$) such that

The set of integers coprime to $N$ under multiplication mod $N$ forms a finite abelian group, $\mathbb{Z}_N^*$, and every element has some finite order dividing $|\mathbb{Z}_N^*| = \varphi(N)$ (Euler's totient). The function $f(x) = a^x \bmod N$ is periodic with period exactly $r$, and this periodicity is what the quantum subroutine detects. The classical number-theoretic insight, due essentially to a folklore reduction predating Shor but combined by him with quantum order-finding, is this: if $r$ is even and $a^{r/2} \not\equiv \pm 1 \pmod N$, then $a^{r/2}$ is a nontrivial square root of $1$ modulo $N$. Writing

and knowing neither factor is $\equiv 0 \pmod N$, the Euclidean algorithm applied to $\gcd(a^{r/2} - 1,\, N)$ (or $+1$) must return a proper, nontrivial divisor of $N$. This works because $N$ divides the product but divides neither factor individually — meaning $N$'s prime factors must be split between the two terms, and the gcd isolates a nontrivial subset of them. Shor's contribution was showing order-finding is exactly the kind of problem the quantum Fourier transform solves efficiently: it reveals the period of a periodic quantum superposition in polynomial time, via Quantum Phase Estimation applied to the modular-exponentiation unitary $U_a\lvert y\rangle = \lvert ay \bmod N\rangle$. This article treats that subroutine as a trusted primitive and focuses on the surrounding reduction and classical control flow that make the full factoring algorithm work.

The full algorithm alternates classical preprocessing, one call to quantum order-finding, and classical postprocessing, retrying with fresh randomness when a trial fails.

Step 1 — Trivial-case filter. If $N$ is even, output the factor $2$. If $N$ is a perfect power $p^k$ (checkable classically in polynomial time by trying all exponents $k \le \log_2 N$ and testing integer $k$-th roots), output $p$. These classical pre-checks remove degenerate cases where the group-theoretic argument below can fail or become trivial.

Step 2 — Random base. Choose $a$ uniformly at random from $\{2, \dots, N-1\}$.

Step 3 — GCD shortcut. Compute $\gcd(a, N)$ using the Euclidean algorithm. If this gcd is not $1$, it is already a nontrivial factor of $N$ — done, no quantum computer needed.

Step 4 — Quantum order-finding. Otherwise $a \in \mathbb{Z}_N^*$. Call the quantum subroutine to find the order $r$ of $a$ mod $N$, i.e. the smallest $r>0$ with $a^r \equiv 1 \pmod N$.

Step 5 — Parity and nontriviality check. If $r$ is odd, or if $r$ is even but $a^{r/2} \equiv -1 \pmod N$, this trial fails to produce a factor; go back to Step 2 with a new random $a$.

Step 6 — Extract the factor. Otherwise compute $\gcd(a^{r/2} - 1, N)$. This is guaranteed to be a nontrivial, proper factor of $N$. ``` ALGORITHM ShorFactor(N):

# N: odd composite integer > 1, not a prime power (checked below) if N is even: return 2 if N is a perfect power p^k (k >= 2): return p loop forever: a := uniform_random_integer(2, N - 1) g := gcd(a, N) # classical Euclidean algorithm if g != 1: return g # lucky classical hit r := QuantumOrderFind(a, N) # calls order-finding subroutine if r is odd: continue # retry with new a if a^(r/2) mod N == N - 1: # i.e. == -1 mod N continue # retry with new a f := gcd(a^(r/2) - 1, N) if f == 1 or f == N: continue # extremely rare degenerate case return f # f is a nontrivial factor of N ``` Once a single nontrivial factor $f$ is found, $N$ splits as $f \times (N/f)$, and the same routine (or classical trial division for small remaining factors) is applied recursively to fully factor $N$ into primes. Modular exponentiation $a^{r/2} \bmod N$ is done classically via fast exponentiation-by-squaring, in $O(n^3)$ bit operations for $n$-bit $N$ (schoolbook multiplication) or better with fast multiplication. The diagram below shows the control flow: the quantum computer is invoked only inside the shaded box, and everything else — random sampling, gcd, modular arithmetic, retry logic — is ordinary classical computation.

Time complexity. For $n$-bit $N$: the trivial-case checks (evenness, perfect-power test) run in $O(n^2)$ or so, negligible compared to the rest. Each trial does one $\gcd$ computation ($O(n^2)$ bit operations classically), one call to quantum order-finding, and one modular exponentiation plus another $\gcd$ for the postprocessing. The quantum order-finding subroutine itself runs in $O(n^3)$ time (dominated by modular exponentiation controlled by the phase-estimation register, plus an $O(n^2)$ quantum Fourier transform), using $O(n)$ qubits for the target register and $O(n)$ (or $O(2n)$ for accuracy margin) qubits for the phase register. The key question is how many trials are expected. As shown below, each random $a$ succeeds — meaning it yields an even order $r$ with $a^{r/2}\not\equiv -1$ — with probability at least $1/2$ (more precisely $1 - 1/2^{k-1}$ where $k$ is the number of distinct odd prime factors of $N$, which is at least $1/2$ whenever $N$ has at least one odd prime factor with multiplicity, i.e. essentially always for $N$ not a power of $2$). So the expected number of trials is $O(1)$, and the total expected running time is

bit operations (with $O(n)$ expected calls dominated by a constant), which is polynomial in $n = \log N$ — an exponential improvement over the best known classical factoring algorithms, whose running time is sub-exponential, e.g. the general number field sieve at roughly $\exp(O(n^{1/3}\log^{2/3} n))$.

Space complexity. $O(n)$ qubits for the quantum register (the exact count depends on the phase-estimation precision and the modular-exponentiation circuit's ancillas, typically $O(n)$ to $O(n^2)$ total qubits in explicit constructions), plus $O(n)$ classical bits for bookkeeping.

Correctness argument. The proof has two independent parts. Part 1 (number theory: why the reduction is correct when it succeeds). Suppose $r = \text{ord}_N(a)$ is even and $x = a^{r/2} \bmod N$ satisfies $x \ne N-1$ (i.e. $x \not\equiv -1$). Since $r$ is the smallest exponent with $a^r \equiv 1$, and $x^2 = a^r \equiv 1 \pmod N$, we know $x$ is a square root of $1$ mod $N$ that is neither $1$ (else $r/2$ would already satisfy $a^{r/2}\equiv 1$, contradicting minimality of $r$) nor $-1$ (by assumption). So

By the Chinese Remainder Theorem, $N$'s prime power factors are distributed between $x - 1$ and $x + 1$ in a way that is not all-or-nothing, so $\gcd(x - 1, N)$ is strictly between $1$ and $N$ — a genuine nontrivial factor. This argument requires $N$ to have at least two distinct prime factors (guaranteed once the perfect-power and even cases are filtered out in Step 1, since a non-power-of-2, non-prime-power composite must have at least two distinct odd prime factors, or one odd prime factor and the factor $2$ handled separately — the standard treatment restricts attention to odd $N$ with at least two distinct prime factors after trivial filtering). Part 2 (probability: why a random $a$ succeeds often enough). Fix the distinct odd prime power factors $N = p_1^{e_1}\cdots p_k^{e_k}$ (with $k \ge 2$ after filtering). By CRT, choosing $a$ uniformly at random mod $N$ (coprime to $N$) is equivalent to choosing independent uniform random elements $a_i \in \mathbb{Z}_{p_i^{e_i}}^*$ for each $i$. Each $\mathbb{Z}_{p_i^{e_i}}^*$ is cyclic (a classical fact for odd prime powers), so the order of $a_i$, and in particular the largest power of $2$ dividing that order, behaves like that of a uniform random element of a cyclic group. A counting argument over cyclic groups shows: the probability that all the $2$-adic valuations $v_2(\text{ord}(a_i))$ coincide across all $i$ — the exact condition under which $r$ is odd or $a^{r/2}\equiv -1$ — is at most $1/2^{k-1} \le 1/2$ for $k \ge 2$. Hence with probability at least $1/2$, a random trial yields a usable $r$, giving expected $O(1)$ retries. This is the classical randomized wrapper's core correctness guarantee, entirely independent of the quantum subroutine's internal workings.

Tradeoffs to be honest about. The quantum order-finding step needs a fault-tolerant quantum computer with enough logical qubits and low enough error rates to run a deep circuit (modular exponentiation is the expensive part, requiring $O(n)$ sequential controlled modular multiplications). Near-term noisy devices cannot run this reliably for cryptographically relevant $n$ (thousands of bits). The algorithm is also a Monte Carlo procedure — it can fail on any given trial (odd $r$, or unlucky $a$) — so a bounded number of retries with high-probability success is the correct framing, not a deterministic guarantee on the first try.

Factor $N = 21$ using $a = 2$.

Step 1. $21$ is odd; is it a perfect power? $21 \ne p^k$ for any prime $p$, $k\ge 2$. Continue.

Step 2–3. Pick $a = 2$. $\gcd(2, 21) = 1$, so proceed to order-finding.

Step 4 (quantum order-finding, traced classically here for illustration). Compute powers of $2$ mod $21$:

The order is $r = 6$ (the smallest positive $x$ with $2^x \equiv 1$). In the real algorithm, this value $r=6$ is what quantum phase estimation extracts (with high probability, via continued-fraction expansion of the measured phase) without ever computing this whole table — it uses superposition to probe all powers of $a$ simultaneously.

Step 5. $r = 6$ is even. Compute $a^{r/2} = 2^3 = 8 \bmod 21 = 8$. Since $8 \ne 21 - 1 = 20$, the nontriviality condition holds — proceed to extraction.

Step 6. Compute $\gcd(8 - 1, 21) = \gcd(7, 21) = 7$. $7$ is a nontrivial factor of $21$. Since $21 = 7 \times 3$, the algorithm succeeds on the very first trial, returning $f = 7$ and (by division) the cofactor $3$.

A failing trial, for contrast. Suppose instead $a = 20 \equiv -1 \pmod{21}$ had been chosen. Then $\gcd(20, 21) = 1$, and the order of $20 \equiv -1$ mod $21$ is $r = 2$ (since $(-1)^2 = 1$). This $r$ is even, so check $a^{r/2} = 20^1 \bmod 21 = 20 \equiv -1$. This is the forbidden case $a^{r/2} \equiv -1$, so this trial fails and the algorithm restarts with a new random $a$ — illustrating why the retry loop is necessary and why picking a "bad" $a$ like $N-1$ is a real, non-degenerate failure mode, not a bug.

Shor's algorithm is the central reason cryptographers now build post-quantum cryptography: RSA, Diffie–Hellman, and elliptic-curve cryptosystems all rely on the hardness of factoring or discrete logarithm, both broken in polynomial time by Shor's approach and its discrete-log variant. Standards bodies (NIST) have run multi-year competitions selecting lattice-based and hash-based replacements precisely because Shor's algorithm makes today's public-key infrastructure obsolete once large, fault-tolerant quantum computers exist. Beyond cryptography, Shor's algorithm is the flagship benchmark for quantum hardware progress: every major quantum computing effort (superconducting qubits, trapped ions, photonics) reports small-scale factoring or order-finding demonstrations as evidence of progress toward fault tolerance. It also inspired the broader class of hidden subgroup problem algorithms, unifying factoring, discrete log, and other abelian group problems under a single quantum algorithmic framework, and motivated deep study of the Quantum Fourier Transform as a general-purpose primitive analogous to the classical FFT in digital signal processing.

Ask the tutor: Can you walk through why a random a fails to give a usable order with probability at most 1/2, using the CRT decomposition explicitly?