Shor's Factoring Algorithm

Factoring a large integer is the quiet hardness assumption that most of the internet trusts. The best classical algorithm known — the general number field sieve — needs time $\exp\!\big(O(n^{1/3}(\log n)^{2/3})\big)$ to split an $n$ -bit modulus, subexponential yet stubbornly superpolynomial, and RSA, the workhorse of public-key cryptography, is safe only for as long as nobody does better. In 1994 Peter Shor did better, and by an exponential margin: a quantum algorithm that factors in time polynomial in $n$ . The result did not just add an entry to a complexity table; it redrew the map of what a computer is, and it is the reason "post-quantum cryptography" is a funded field rather than a thought experiment. The algorithm is a hinge between two worlds. Almost all of it is ordinary number theory: to factor $N$ , pick a random base $a$ , and — unless you get lucky and $\gcd(a,N)$ is already a factor — find the multiplicative order $r$ of $a$ modulo $N$ , the smallest $r$ with $a^r\equiv 1$ . From an even $r$ with $a^{r/2}\not\equiv-1$ , a difference of squares hands you $\gcd(a^{r/2}\pm1,\,N)$ , two nontrivial factors, in a few lines of Euclid. The one step no classical machine can do quickly is finding $r$ , because the period of $x\mapsto a^x\bmod N$ hides the factorization. That single step is the quantum computer's entire job. Quantum mechanically, $r$ stops being a needle in an exponential haystack and becomes a global phase pattern. The operator "multiply by $a$ " has eigenvalues $e^{2\pi i s/r}$ ; quantum phase estimation reads one, the inverse quantum Fourier transform sharpens it into a measurement peak, and continued fractions strip the unknown numerator to expose $r$ . This article assembles that pipeline from its named prerequisites — the QFT, phase estimation, order finding — and shows why it is the flagship instance of the abelian hidden subgroup problem.

Key takeaways

Shor's algorithm factors an $n$ -bit integer in time $O(n^2\log n\log\log n)$ on a quantum computer — an exponential speedup over every classical method known.
The engine is a classical reduction: factoring reduces, with probability $\ge \tfrac12$ per random base, to finding the multiplicative order $r$ of $a$ modulo $N$ .
The quantum core solves order finding by phase estimation on the modular-multiplication unitary $U_a\lvert y\rangle=\lvert ay\bmod N\rangle$ , whose eigenvalues $e^{2\pi i s/r}$ carry the period.
You never build an eigenstate: the trivial state $\lvert 1\rangle$ is an equal superposition of all $r$ of them, so one run samples a random $s$ and the same circuit works without knowing $r$ .
The measured estimate of $s/r$ is post-processed by continued fractions to recover $r$ exactly; this demands a phase register of $t\approx 2n+1$ qubits so that $Q=2^t\ge N^2$ .
Breaking RSA is the headline, but order finding is also discrete log, Diffie–Hellman, and elliptic-curve crypto — all abelian hidden subgroup problems solved by one Fourier-sampling template.
Key idea: Factoring reduces to finding the period $r$ of $x\mapsto a^x\bmod N$ ; the quantum Fourier transform reads that period out of a uniform superposition in one shot, turning an exponentially hard classical search into polynomial-time phase estimation on the modular-multiplication operator.

The core insight

Factoring reduces to finding the period $r$ of $x\mapsto a^x\bmod N$ ; the quantum Fourier transform reads this period out of a uniform superposition in one shot, turning an exponentially hard classical search into polynomial-time phase estimation on the modular-multiplication operator.

Where this lives today

Shor's algorithm is at once a laboratory demonstration, an engineering target, and a policy driver. Experimentally it has been shown but never scaled: a 2001 nuclear-magnetic-resonance experiment factored $15=3\times5$ on seven spins, and later photonic and ion-trap demonstrations repeated small cases — but every published "factoring" of a large number is either a compiled special case exploiting the known answer or a different algorithm entirely, not honest scalable Shor. The number that matters is the resource estimate: the Gidney–Ekerå analysis (2021) puts a 2048-bit RSA break at roughly $20$ million noisy physical qubits running about $8$ hours under surface-code error correction — thousands of logical qubits and $10^9$ – $10^{10}$ Toffoli gates. That is far beyond present devices, but it is a concrete, shrinking target, and the modular-exponentiation arithmetic dominating it is where circuit-optimization research now concentrates. The consequences are already operational. Because "harvest now, decrypt later" — recording encrypted traffic today to break it once hardware matures — turns a future capability into a present risk, standards bodies have moved: in 2024 NIST finalized its first post-quantum cryptography standards (lattice-based ML-KEM and ML-DSA, hash-based SLH-DSA), and migration away from RSA and elliptic-curve schemes is underway across governments and industry. Meanwhile the algorithm's descendants define a frontier: order finding is the abelian hidden subgroup problem for $\mathbb{Z}$ , discrete log is the HSP for $\mathbb{Z}\times\mathbb{Z}$ , and the open question of efficient nonabelian HSP algorithms — bearing on graph isomorphism (symmetric group) and lattice problems (dihedral group) — takes Shor's success as both its inspiration and its stubborn limit.

The physical picture

Think of $f(x)=a^x\bmod N$ as a periodic signal whose hidden period is exactly the number the algorithm wants. A quantum computer evaluates $f$ on every input at once, entangling a label of $x$ with the value $f(x)$ in one pass of reversible arithmetic. Ignore the value register and the input register collapses onto a single arithmetic progression $\{x_0,\,x_0+r,\,x_0+2r,\dots\}$ — one period's worth of the comb. The quantum Fourier transform of a comb of spacing $r$ is itself a comb, but of spacing $Q/r$ : the period, invisible in the values, reappears as sharp interference peaks. No individual function value was ever examined; only the global periodicity survived. The phase-estimation viewpoint is cleaner, and the one this article builds on. The operator $U_a$ — multiply a residue by $a$ , modulo $N$ — is a permutation of the residues, and a permutation whose cycles have length $r$ has eigenvalues that are $r$ -th roots of unity, $e^{2\pi i s/r}$ . Estimate one eigenvalue's phase and you have measured a fraction $s/r$ ; run it through continued fractions and the unknown numerator $s$ falls away, leaving $r$ . The genius of the construction is that you never have to prepare an eigenstate — which would require knowing $r$ first. The residue $1$ , trivial to write down, is an exactly equal superposition of all $r$ eigenstates, so one run samples a uniformly random $s$ for free. The first figure lays out this two-register circuit; the second shows the interference comb it produces.

Figure

The Shor circuit: a phase register of t ≈ 2n+1 qubits is put in uniform superposition, drives a controlled modular exponentiation that writes aˣ mod N into the lower register, then the inverse QFT concentrates the amplitude so the measured y ≈ sQ per r, with Q = 2ᵗ ≥ N²

Where the comb's teeth land is set entirely by number theory, and one instance shows the mechanism sharply. Take $N=15$ , $a=7$ : the powers of $7$ mod $15$ cycle $7,4,13,1,\dots$ , so $r=4$ ; with $t=8$ qubits, $Q=256\ge N^2=225$ , and the post-QFT distribution is four sharp peaks at $y=sQ/r=64s$ . Reading $y=64$ gives $1/4$ , whose continued-fraction denominator is $r=4$ — done in one shot. The second figure is that exact distribution, the payoff picture of the whole algorithm.

Figure

Post-QFT measurement distribution for N = 15, a = 7 with r = 4 and Q = 256: because r divides Q the comb is four exact peaks at y = sQ/r = 0, 64, 128, 192, each with probability 1/4; the coprime outcomes y = 64 and y = 192 return r = 4 through continued fractions, the outcome y = 128 gives only the divisor 2, and y = 0 is uninformative

The core equations

The whole algorithm rests on one classical fact — that the order gives up the factors — and one quantum fact — that phase estimation gives up the order. Start with the classical bridge, which is elementary number theory: an even order with a non-trivial square root of unity yields factors by a difference of squares.

\gcd\!\big(a^{r/2}-1,\,N\big)\ \text{and}\ \gcd\!\big(a^{r/2}+1,\,N\big)\ \text{are nontrivial factors of } N \qquad (1)

where: $N$ — composite integer to factor, $n=\lceil\log_2 N\rceil$ bits; $a$ — random base with $1<a<N$ and $\gcd(a,N)=1$ ; $r$ — multiplicative order of $a$ mod $N$ , the least $r\ge1$ with $a^r\equiv1$ . Reading: given a good $a$ (even $r$ , $a^{r/2}\not\equiv-1$ ), two Euclid gcds finish the factoring in $O(n^2)$ classical work. The quantum side needs an operator whose spectrum stores $r$ . Multiplication by $a$ modulo $N$ is a bijection of residues, hence a unitary permutation, and it is the object phase estimation acts on.

U_a\,\lvert y\rangle = \lvert a y \bmod N\rangle,\qquad 0\le y<N \qquad (2)

where: $U_a$ — permutation operator on residues, unitary because multiplication by a unit $a$ is invertible mod $N$ ; $\lvert y\rangle$ — computational basis state labelling residue $y$ . Reading: $U_a$ moves along the cycle $1\to a\to a^2\to\cdots$ , closing after exactly $r$ steps. Because that cycle has length $r$ , the operator's eigenstates are discrete Fourier modes over the cycle, and their eigenvalues are the $r$ -th roots of unity — the period, encoded directly in a phase.

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

where: $\lvert u_s\rangle$ — eigenstate indexed by $s\in\{0,\dots,r-1\}$ ; $e^{2\pi i s/r}$ — eigenvalue, an $r$ -th root of unity. Reading: phase estimation on $\lvert u_s\rangle$ would return the fraction $s/r$ — but preparing $\lvert u_s\rangle$ needs $r$ , the very unknown. The escape is that the residue $1$ is already an equal superposition over all $r$ eigenstates, so it needs no knowledge of $r$ at all.

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

where: $\lvert 1\rangle$ — computational basis state for residue $1$ , trivially prepared. Reading: feed $\lvert 1\rangle$ into phase estimation and each run collapses onto one random $\lvert u_s\rangle$ , sampling $s$ uniformly from $\{0,\dots,r-1\}$ . Running phase estimation is running the modular exponentiation controlled on a superposed exponent, which produces the entangled comb state that the inverse QFT will read.

\lvert\psi\rangle = \frac{1}{\sqrt Q}\sum_{x=0}^{Q-1}\lvert x\rangle\,\lvert a^x\bmod N\rangle,\qquad Q=2^t,\ \ t\approx 2n+1 \qquad (5)

where: $Q$ — size of the phase register, chosen $Q\ge N^2$ ; $t$ — qubits in the phase register, $t=\lceil\log_2 Q\rceil$ . Reading: this one line does exponentially many evaluations of $a^x$ in superposition; everything after is interference, not further arithmetic. Applying the inverse QFT and measuring concentrates the amplitude near integer multiples of $Q/r$ — the interference comb of the second figure.

\Pr[\text{measure } y] = \frac{1}{rQ}\left|\sum_{j=0}^{m-1} e^{2\pi i\,jr y/Q}\right|^2 \ \xrightarrow{\ Q\to\infty\ }\ \text{peaks at } y\approx\frac{sQ}{r} \qquad (6)

where: $y$ — measured value of the phase register; $m\approx Q/r$ — number of terms in the collapsed progression; $s$ — the random integer $0\le s<r$ selected by that run. Reading: the geometric sum is $O(m)$ only when $ry/Q$ is near an integer, so measurement lands on the tooth nearest $sQ/r$ with high probability. Dividing $y$ by $Q$ gives an approximation to $s/r$ ; continued fractions recover the exact fraction, but only if the register is large enough that no other fraction with denominator below $N$ is as close.

\left|\frac{y}{Q}-\frac{s}{r}\right|\le\frac{1}{2Q}\le\frac{1}{2N^2}\ \Rightarrow\ \frac{s}{r}\ \text{is the unique convergent of}\ \frac{y}{Q}\ \text{with denominator}<N \qquad (7)

where: $y/Q$ — measured fraction fed to the continued-fraction algorithm; $s/r$ — target rational, in lowest terms exactly when $\gcd(s,r)=1$ . Reading: this is why $t\approx 2n+1$ — the resolution $1/(2Q)$ must beat the $1/(2N^2)$ gap between distinct fractions of denominator $<N$ . Finally, the cost. The QFT is cheap ( $O(n^2)$ ); the bill is the modular exponentiation, a ladder of controlled modular multiplications.

\lvert x\rangle\lvert y\rangle \xrightarrow{\ \prod_j C\text{-}U_a^{2^j}\ } \lvert x\rangle\,\big\lvert y\,a^x\bmod N\big\rangle,\qquad T_{\text{Shor}}=O\!\big(n^2\log n\log\log n\big) \qquad (8)

where: $C\text{-}U_a^{2^j}$ — controlled multiplication by $a^{2^j}\bmod N$ , conditioned on exponent bit $x_j$ ; $T_{\text{Shor}}$ — total gate count with fast (Schönhage–Strassen) integer multiplication. Reading: $O(n)$ modular multiplications each costing $O(n^2)$ give $O(n^3)$ with schoolbook arithmetic, dropping to $O(n^2\log n\log\log n)$ with fast multiplication — polynomial, and that is the whole point.

Derivation AFrom the order to the factors

The goal of this first derivation is to justify equation (1) completely — to show precisely why knowing the order $r$ of a random base $a$ lets ordinary greatest-common-divisor arithmetic split $N$ , and to pin down exactly which two conditions on $r$ make the trick work. Everything here is classical; not a single qubit appears. The plan is to start from the defining congruence of the order, factor a difference of squares, and then argue that a common factor with $N$ must be non-trivial precisely when $r$ is even and $a^{r/2}$ is not the "boring" square root $-1$ of unity.

Step 1. By definition of the order, $a^r\equiv 1\pmod N$ , so $N$ divides $a^r-1$ . Why: the order is the exact period of the powers of $a$ , so $a^r-1$ is the first power difference that $N$ cleanly divides — the anchor the rest of the argument hangs from.

Step 2. Assume $r$ is even and write $a^r-1=(a^{r/2}-1)(a^{r/2}+1)$ ; then $N$ divides the product $(a^{r/2}-1)(a^{r/2}+1)$ . Why: the difference of squares is the whole mechanism — it splits the quantity $N$ divides into two explicit integers, and any prime of $N$ must land in one of them.

Step 3. Now $a^{r/2}\not\equiv 1\pmod N$ , because $r/2<r$ and $r$ is the least exponent giving $1$ ; assume also the favourable case $a^{r/2}\not\equiv -1\pmod N$ . Why: if $a^{r/2}\equiv\pm1$ then one factor is $\equiv0$ and the other carries all of $N$ , so the gcds return only $1$ and $N$ — these are exactly the two "bad-base" failure modes the reduction must dodge.

Step 4. Since $N$ divides neither $a^{r/2}-1$ nor $a^{r/2}+1$ individually, yet divides their product, $N$ shares a proper factor with each; hence $\gcd(a^{r/2}-1,N)$ and $\gcd(a^{r/2}+1,N)$ are non-trivial, computed in $O(n^2)$ by Euclid. Why: a prime power $p^m\parallel N$ cannot sit entirely inside a factor that $N$ fails to divide, so its parts distribute across the two gcds — this is the difference of squares delivering the split concretely. *Verified: $N=15,\,a=7,\,r=4,\,a^{r/2}=4$ gives $\gcd(3,15)=3$ and $\gcd(5,15)=5$ ; the bad base $a=14$ has $a^{r/2}=14\equiv-1$ and returns only $1$ and $15$ .*

Go deeper · Derivation B · 1 minWhy the trivial state 1 phase-estimates the period

Derivation BWhy the trivial state 1 phase-estimates the period

This derivation resolves the apparent circularity at the heart of Shor's construction: phase estimation reads the eigenphase $s/r$ of an eigenstate $\lvert u_s\rangle$ , yet every $\lvert u_s\rangle$ is defined in terms of the unknown $r$ , so how can one prepare the input without already solving the problem. The goal is to prove equation (4) — that the equal superposition of all $r$ eigenstates collapses to the single computational basis state $\lvert 1\rangle$ — so that the algorithm runs on a state anyone can prepare, and each run silently samples a uniformly random $s$ . The plan is to sum the eigenstate definitions over $s$ , swap the order of summation, and evaluate the resulting geometric sum.

Step 1. Sum equation (3) over $s$ and interchange the two sums: $\frac{1}{\sqrt r}\sum_{s}\lvert u_s\rangle=\frac{1}{r}\sum_{k=0}^{r-1}\big(\sum_{s=0}^{r-1}e^{-2\pi i sk/r}\big)\lvert a^k\bmod N\rangle$ . Why: pulling the $k$ -sum outside isolates a pure phase sum over $s$ for each fixed $k$ , which is a geometric series with a clean closed form.

Step 2. Evaluate the inner sum: $\sum_{s=0}^{r-1}e^{-2\pi i sk/r}=r\,\delta_{k,0}$ , zero for every $k\not\equiv0$ and $r$ for $k=0$ . Why: this is the discrete orthogonality of roots of unity — the same identity that makes the Fourier transform diagonalize cyclic shifts, here killing every basis term except one.

Step 3. Only $k=0$ survives, leaving $\lvert a^0\bmod N\rangle=\lvert 1\rangle$ . Why: the entire equal superposition of eigenstates is nothing but the residue $1$ in disguise, so preparing $\lvert 1\rangle$ is preparing $\frac{1}{\sqrt r}\sum_s\lvert u_s\rangle$ without ever naming $r$ .

Step 4. Phase estimation is linear, so running it on $\lvert 1\rangle=\frac{1}{\sqrt r}\sum_s\lvert u_s\rangle$ produces the entangled sum $\frac{1}{\sqrt r}\sum_s\lvert \widetilde{s/r}\rangle\lvert u_s\rangle$ ; measuring the phase register collapses one term, delivering a uniformly random $s$ . Why: linearity converts "superposition of eigenstates" into "random choice of eigenphase" at measurement — the one probabilistic step, and the reason a few repetitions suffice. *Verified: for $r=4$ the four eigenphases are $s/4\in\{0,\tfrac14,\tfrac12,\tfrac34\}$ ; summing the four $\lvert u_s\rangle$ returns $\lvert 1\rangle$ , and equal sampling of $s$ matches the four equal peaks in the second figure.*

Go deeper · Derivation C · 2 minRegister size and continued-fraction recovery

Derivation CRegister size and continued-fraction recovery

The output of phase estimation is not $r$ but a noisy estimate $y/Q$ of the fraction $s/r$ , and the final classical step must recover the exact rational from that approximation. The goal here is to derive the register-size rule $t\approx 2n+1$ (equivalently $Q\ge N^2$ ) as the exact resolution needed for continued fractions to return $s/r$ uniquely, and to explain why an undersized register makes the answer ambiguous rather than merely imprecise. The plan is to bound the phase-estimation error, invoke the uniqueness theorem for continued-fraction convergents, and combine the two into a condition on $Q$ .

Step 1. With $t$ qubits, phase estimation returns the integer $y$ whose fraction $y/Q$ is within $1/(2Q)$ of the true $s/r$ with constant probability. Why: $Q=2^t$ is the grid spacing of representable phases, so the best estimate is off by at most half a grid cell — the resolution improves exponentially in $t$ , cheaply.

Step 2. A rational $s/r$ with $r<N$ is the unique fraction of denominator below $N$ within $1/(2N^2)$ of a given real, because two distinct fractions $s/r$ and $s'/r'$ with denominators $<N$ differ by at least $1/(rr')>1/N^2$ . Why: fractions of bounded denominator are spread apart by at least $1/N^2$ , so any approximation closer than half that gap can match only one of them — this is the theorem that makes recovery deterministic.

Step 3. Demand the estimation resolution beat the fraction gap: $1/(2Q)\le 1/(2N^2)$ , i.e. $Q\ge N^2$ , hence $t\ge 2n$ ; the standard choice $t=2n+1$ adds one bit of headroom for the constant success probability. Why: matching the two scales is exactly equation (7) — undersize the register and several fractions of denominator $<N$ tie for closest, so continued fractions cannot decide and the readout is corrupted, not just coarse.

Step 4. Run the continued-fraction expansion of $y/Q$ and take the last convergent with denominator below $N$ ; its denominator is $r$ when $\gcd(s,r)=1$ , and a proper divisor of $r$ otherwise, cured by repetition. Why: the convergents of a continued fraction are provably the best rational approximations of bounded denominator, so the algorithm reads $s/r$ off directly — and a coprime $s$ , which occurs with probability $\varphi(r)/r=\Omega(1/\log\log r)$ , delivers $r$ itself. *Verified: $N=15$ needs $n=4$ , $N^2=225$ , so $t=8$ , $Q=256$ suffices; the outcome $y=192$ gives $192/256=3/4$ , whose convergent denominator is $r=4$ , while $y=128$ gives $1/2$ and only the divisor $2$ .*

Limiting cases

The algorithm's behaviour is governed by number-theoretic luck in the base $a$ and by correct sizing of the phase register:

Case	Result	Meaning
Odd order	$r$ odd	$a^{r/2}$ is not an integer power, so the factoring step (1) is undefined; this run is discarded and a fresh $a$ is drawn.
Trivial square root	$a^{r/2}\equiv -1\pmod N$	The difference of squares gives only $\gcd=1$ and $\gcd=N$ ; another bad-base event cured by retrying.
Both good conditions	$r$ even, $a^{r/2}\not\equiv-1$	Success: $\gcd(a^{r/2}\pm1,N)$ split $N$ . For $N$ with $k\ge2$ distinct odd prime factors this holds with probability $\ge 1-2^{-(k-1)}\ge\tfrac12$ per random $a$ .
Prime power $N=p^m$	$N=p^m$	Order finding need not split cleanly, but prime powers are caught by a classical preprocessing test (is $N^{1/b}$ an integer for $b\le\log_2 N$ ).
Even $N$	$2\mid N$	Trivial — divide out factors of $2$ classically before invoking the quantum routine at all.
Register too small	$Q<N^2$	Continued fractions cannot resolve $s/r$ uniquely; distinct fractions tie and the readout is ambiguous. Must use $t\approx 2n+1$ .

Common trapThe QFT does not measure r

The single most common misconception is that the quantum computer outputs the period directly. It does not. Measurement returns an integer $y$ close to $sQ/r$ for an unknown, random numerator $s$ — never $r$ by itself. Three classical steps stand between the measurement and the answer: run continued fractions on $y/Q$ to get a candidate fraction; take its denominator as the candidate $r$ ; and verify $a^r\equiv1\pmod N$ before trusting it. If $\gcd(s,r)\ne1$ the candidate is only a divisor of $r$ , so one repeats and takes least common multiples across runs. The twin conceptual error is imagining the circuit prepares a specific eigenstate $\lvert u_s\rangle$ — it never does; it runs on the trivial state $\lvert 1\rangle$ and lets measurement pick $s$ . Skip the post-processing and you have a beautiful phase, and no factor.

Worked examples

1 · Factoring 15 end to end (fully worked)

Factor $N=15$ using the base $a=7$ : run the classical setup, state what the quantum order-finding subroutine returns, and finish the factoring — with every number explicit.

Step 1. Classical setup. Check $\gcd(7,15)=1$ , so $7$ is a valid base and gives no free factor. The modulus has $n=\lceil\log_2 15\rceil=4$ bits, so choose a phase register of $t=8$ qubits: $Q=2^8=256\ge N^2=225$ . The circuit uses an 8-qubit phase register.

Step 2. What order finding returns. The powers of $7$ mod $15$ cycle $7^1=7,\ 7^2=4,\ 7^3=13,\ 7^4=1$ , so the order is $r=4$ . The quantum subroutine does not know this in advance; it prepares $\lvert 1\rangle$ , runs controlled modular exponentiation, applies the inverse QFT, and measures. Because $r=4$ divides $Q=256$ exactly, the outcome is one of four sharp peaks $y\in\{0,64,128,192\}$ , each with probability $\tfrac14$ . Measurement yields $y\in\{0,64,128,192\}$ .

Step 3. Continued-fraction recovery. Suppose the run returns $y=64$ . Then $y/Q=64/256=1/4$ , already in lowest terms, so the denominator is the candidate $r=4$ . Verify: $7^4=2401=160\times15+1\equiv1\pmod{15}$ . Good — $r=4$ confirmed. (Had the run returned $y=128$ , giving $1/2$ , the candidate would be the divisor $2$ ; verifying $7^2=49\equiv4\not\equiv1$ rejects it, and one simply reruns. The outcomes $64$ and $192$ — a $\tfrac12$ chance — succeed immediately.) Recovered $r=4$ .

Step 4. Extract the factors. The order is even and $a^{r/2}=7^2=49\equiv4\pmod{15}$ , which is neither $1$ nor $-1\equiv14$ — a good base. Apply equation (1): $\gcd(4-1,15)=\gcd(3,15)=\mathbf{3}$ and $\gcd(4+1,15)=\gcd(5,15)=\mathbf{5}$ . $15=3\times5$ .

2 · A larger period and a bad base (21)

Factor $N=21$ with $a=2$ , then show what goes wrong for the base $a=5$ .

Step 1. Good base $a=2$ . Here $\gcd(2,21)=1$ . The powers $2^1=2,\,2^2=4,\,2^3=8,\,2^4=16,\,2^5=11,\,2^6=1\pmod{21}$ give order $r=6$ — even, and larger than the modest register would suggest, illustrating why $t\approx 2n+1$ (here $2\cdot5+1=11$ qubits, $Q\ge N^2=441$ ) is needed to resolve $s/6$ .

Step 2. Finish the factoring. With $r=6$ , $a^{r/2}=2^3=8\pmod{21}$ , and $8\not\equiv\pm1$ . Then $\gcd(8-1,21)=\gcd(7,21)=\mathbf{7}$ and $\gcd(8+1,21)=\gcd(9,21)=\mathbf{3}$ . $21=7\times3$ .

Step 3. Why $a=5$ fails. The base $5$ also has order $r=6$ mod $21$ (powers $5,4,20,16,17,1$ ), but now $a^{r/2}=5^3=125\equiv20\equiv-1\pmod{21}$ . The difference of squares collapses: $\gcd(20-1,21)=\gcd(19,21)=1$ and $\gcd(20+1,21)=\gcd(21,21)=21$ — only the trivial factors. A bad base returns $1$ and $N$ ; discard and redraw $a$ . Because at least half of all valid bases are good, a handful of trials suffices.

Physics of the portrait

Shor's algorithm is the moment computer science reached into quantum mechanics and pulled out something no classical machine could match — and it did so by recognizing that a period, invisible to sampling, is a phase written across a superposition that interference can read.

Origins · 1 minPeter Shor and how this was discovered

Peter Shor

born 1959 · quantum algorithms and complexity

Peter Williston Shor, an American mathematician then at AT&T Bell Laboratories, changed the stakes of quantum computing in a single 1994 paper. Before it, quantum computers were a curiosity with a few contrived speedups (Deutsch–Jozsa, Simon) over problems nobody cared about; Shor produced a polynomial-time algorithm for a problem the entire world's cryptography depended on being hard — integer factorization — and for its cousin, discrete logarithm. His insight braided three threads: the reduction of factoring to order finding, the quantum Fourier transform as an efficient circuit, and phase estimation on the modular-multiplication operator. The reaction was immediate and double-edged: it poured funding and talent into quantum computing and launched post-quantum cryptography as a defensive discipline. Shor's fingerprints are elsewhere too — the nine-qubit Shor code of 1995, the first quantum error-correcting code, showed quantum information could in principle be protected against decoherence, removing the last "in-principle-impossible" objection to scalable machines. He later moved to MIT. What makes the factoring result endure is its structure: it is the clean, canonical solution of the abelian hidden subgroup problem, and essentially every exponential-speedup quantum algorithm since is measured against its template.

History

1994

— Peter Shor presents the polynomial-time factoring and discrete-log algorithm at the FOCS conference

1995

— Shor introduces the nine-qubit code, the first quantum error-correcting code, and gives an approximate QFT

1996

— Ekert and Jozsa expose the order-finding and hidden-subgroup structure underlying the algorithm

1997

— Shor's expanded paper appears in the SIAM Journal on Computing

2001

— a seven-qubit nuclear-magnetic-resonance experiment factors 15 into 3 and 5

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, §5.2–5.3 (order finding and factoring) and Appendix 4 (the reduction-success bound) · Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," SIAM J. Comput. 26, 1484 (1997) · Preskill, Lecture Notes for Physics 219, Ch. 6 · Kitaev, Shen & Vyalyi, Classical and Quantum Computation, Ch. 13 · Mermin, Quantum Computer Science, Ch. 3 · Watrous, The Theory of Quantum Information, lecture notes on factoring.

Provenance. The equations and complexity bounds follow Nielsen & Chuang Ch. 5 and Shor's 1997 paper. A verifier should recompute: the difference-of-squares step and the two Euclid gcds of equation (1); the eigenphase $e^{2\pi i s/r}$ of $U_a$ and the orthogonality collapse $\sum_s e^{-2\pi i sk/r}=r\delta_{k,0}$ giving $\lvert 1\rangle=\frac{1}{\sqrt r}\sum_s\lvert u_s\rangle$ ; the register condition $1/(2Q)\le1/(2N^2)\Rightarrow Q\ge N^2$ ; the reduction-success bound $\ge1-2^{-(k-1)}$ via the CRT two-adic-valuation argument (N&C Appendix 4 / Theorem 5.3); the worked instances $N=15,a=7\Rightarrow r=4\Rightarrow\{3,5\}$ and $N=21,a=2\Rightarrow r=6\Rightarrow\{7,3\}$ , including the bad base $a=5$ mod $21$ ; and the $O(n^2\log n\log\log n)$ gate count. Hardware resource figures (roughly $20$ million qubits / $8$ hours for RSA-2048; NIST's 2024 PQC standards) are cited as reported estimates, not derived here.

Builds on: Quantum Fourier Transform · Quantum Phase Estimation · Order Finding and Period Finding · Quantum Parallelism and the Oracle Model. Leads to: Quantum Discrete Logarithm Algorithm · Hidden Subgroup Problem · Simon's Algorithm.

Ask the tutor: Ask me to walk you through factoring your own small $N$ — pick a base, and we will find its order, draw the interference comb, and read the factors off together.

Does Shor's algorithm try all the factors of N at once in superposition?

No — that is the wrong model, and the one to unlearn first. The quantum computer never tests candidate divisors. It solves a different problem, order finding: given the base $a$ , it finds the period $r$ of $a^0,a^1,a^2,\dots$ modulo $N$ . The "parallelism" is real but subtle — the circuit evaluates $a^x$ for all $x$ at once, entangling $x$ with $a^x\bmod N$ — yet you cannot read those values out; measurement gives one useless random pair. What survives is a global property, the period, which the QFT converts into a measurable interference pattern. Factoring then follows classically from the period, not from any parallel division.

Where exactly is the exponential speedup — the QFT is only quadratic?

The QFT is not the source of the speedup, which surprises many people. It costs only $O(n^2)$ gates, no faster asymptotically than the modular exponentiation it accompanies. The speedup lives in the problem framing: classically, detecting the period of $a^x\bmod N$ seems to need exponentially many evaluations, because the period encodes the factorization and no local structure reveals it. Quantum mechanically the period is a phase pattern spread across a superposition, and interference reads a global phase in one shot. The win is not a faster Fourier transform — the classical FFT is comparably fast — but the ability to apply that transform to an exponentially large superposition prepared with only polynomial work. Speedup is superposition plus interference, not the transform alone.

Why is the register 2n+1 qubits and not just n?

Because continued fractions need enough resolution to name the fraction $s/r$ uniquely. Two different fractions with denominators below $N$ can be as close as $1/N^2$ , so to guarantee your measured estimate $y/Q$ is nearer the true $s/r$ than to any impostor, the resolution $1/(2Q)$ must beat $1/(2N^2)$ . That forces $Q\ge N^2$ , i.e. $t\ge 2n$ ; one extra bit buys the constant success probability, giving $t\approx 2n+1$ . Use only $n$ qubits and the estimate of $s/r$ is too coarse — several fractions of denominator below $N$ are all consistent with the measurement, and continued fractions cannot pick the right one. The register size is set by classical post-processing, not by the quantum part.

What are the "bad bases," and how often do they ruin a run?

Two things can go wrong with a random base $a$ : its order $r$ can be odd (so $a^{r/2}$ is not an integer power and the factoring formula is undefined), or $a^{r/2}$ can equal $-1$ modulo $N$ (so the difference of squares gives only the trivial factors $1$ and $N$ ). Both are number-theoretic accidents of that particular $a$ , not failures of the quantum circuit. The reassuring theorem, proved via the Chinese Remainder Theorem, is that for an odd composite with $k\ge2$ distinct prime factors these bad events together have probability at most $2^{-(k-1)}\le\tfrac12$ . So a good base turns up in a couple of tries on average, and the whole algorithm just redraws $a$ and repeats when it hits a bad one.

Has anyone actually factored a big number with Shor's algorithm?

Not honestly, and this is widely misreported. The genuine demonstrations are tiny: a 2001 NMR experiment factored $15$ , and later photonic and ion-trap experiments repeated small cases. Headlines claiming much larger factorizations almost always describe either compiled circuits that secretly hard-code the known answer, or a different method entirely (a variational or annealing heuristic) that does not scale and is not Shor's algorithm. Breaking RSA-2048 requires thousands of logical qubits — roughly twenty million noisy physical qubits for hours — under full error correction, hardware that does not yet exist. The algorithm is proven on paper and in toy demonstrations; running it at cryptographic scale is the open engineering challenge.

If we can't run it yet, why worry about it now?

Because encrypted data has a long shelf life and adversaries are patient. The "harvest now, decrypt later" threat is simple: record encrypted traffic today, store it, and decrypt it years from now once a large fault-tolerant quantum computer exists. Anything that must stay secret for a decade — state secrets, medical records, long-lived keys — is therefore already at risk from a machine that has not been built. That is why standards bodies moved ahead of the hardware: NIST finalized post-quantum cryptography standards in 2024, and migration away from RSA and elliptic-curve cryptography is underway now. Shor's algorithm is thus a present-tense policy problem despite being a future-tense engineering one — its mere existence, provably correct, is enough to force the change.