Shor's Algorithm: Order Finding and Factoring

Derivation

Shor's Algorithm: Order Finding and Factoring

D-415 Home PU-404 Threads symmetry · chance · waves Depends on Quantum Phase Estimation, The Quantum Fourier Transform Circuit

Statement

For an odd composite integer N that is not a prime power, factoring is polynomial-time reducible to order-finding: given a random base a coprime to N, the multiplicative order r (least r > 0 with a^r ≡ 1 (mod N)) is extracted by quantum phase estimation applied to the modular-multiplication unitary U_a |y〉 = |ay mod N〉, whose eigenphases are the fractions s/r; a classical continued-fraction step then recovers r, and with constant probability gcd(a^r/2 ± 1, N) is a nontrivial factor.

Why it matters

Shor's algorithm is the flagship demonstration that a quantum computer can solve a problem believed classically intractable: the best known classical factoring algorithm (the general number field sieve) runs in sub-exponential but super-polynomial time exp(O( (log N)^1/3(log log N)^2/3)), whereas the quantum routine runs in O((log N)² log log N log log log N) gates. The security of RSA rests entirely on the assumed hardness of this problem, so the algorithm is the reason post-quantum cryptography exists as a field.

Conceptually it is the archetype of the hidden-subgroup paradigm: order-finding is the abelian hidden-subgroup problem for the map k ↦ a^k mod N, and the Fourier transform over ℤ is exactly the tool that exposes the hidden period. The same skeleton solves discrete logarithm, Pell's equation, and principal-ideal problems.

Assumptions

N is odd and not a prime power.Even N is factored by dividing by 2; prime powers N = p^m are found in classical polynomial time by testing N^1/k for each k. These cases are stripped off classically first, so the quantum routine is only invoked when it can succeed.

a is drawn uniformly from {2, …, N−1} and gcd(a, N) = 1.If gcd(a, N) > 1 we already hold a factor and stop; requiring coprimality guarantees a is an element of the group ℤ_N^× so that a finite order r exists.

The control register uses t = 2n + 1 qubits, where n = ⌈log₂ N⌉.Fewer qubits leave the phase estimate coarser than 1/2r², and the continued-fraction convergent for s/r is then no longer guaranteed unique, so r may not be recoverable from a single run.

Modular exponentiation a^{2^j} mod N is precomputed classically and applied reversibly.The controlled-U_a^{2^j} gates require the exponents a^{2^j} mod N as data; computing them on the quantum device by repeated squaring would dominate the cost, whereas classical precomputation reduces each controlled operation to a single controlled modular multiply.

Derivation

a^r ≡ 1 (mod N), r = ord_N(a)

Since a ∈ ℤ_N^× and the group is finite, some power returns to the identity; r is defined as the least such exponent. A

(a^r/2 − 1)(a^r/2 + 1) = a^r − 1 ≡ 0 (mod N)

Factor the difference of squares, valid whenever r is even so that r/2 is an integer. The product is divisible by N. A

a^r/2 ≢ ±1 (mod N) ⇒ 1 < gcd(a^r/2 − 1, N) < N

If neither factor is ≡ 0 (mod N) yet their product is, then N divides neither but divides the product, so N shares a proper factor with each — a nontrivial gcd, computed classically by Euclid. This is the whole payoff: r yields a factor. B

U_a |y〉 = |ay mod N〉

Define the target-register operator. Because multiplication by the invertible element a permutes ℤ_N^× (extend by the identity on y not coprime to N), U_a is a permutation of basis states, hence unitary. B

|u_s〉 = (1/√r) ∑_k=0^r−1 e^{−2πi sk/r} |a^k mod N〉, U_a |u_s〉 = e^2πi s/r|u_s〉

Apply U_a: it shifts |a^k〉 ↦ |a^k+1〉; relabel the sum index k → k−1 to pull out the phase e^2πi s/r. The r states |u_s〉, s = 0, …, r−1, are the eigenvectors, with eigenphases exactly the rationals s/r. C

(1/√r) ∑_s=0^r−1 |u_s〉 = |1〉

Sum the eigenvectors: the amplitude of |a^k〉 is (1/r)∑_s e^{−2πi sk/r} = δ_k,0 by the geometric-series (orthogonality) identity, leaving only |a⁰〉 = |1〉. Thus the easily prepared state |1〉 is an equal superposition over all eigenvectors — we need never know r to prepare an eigenstate. C

|0〉^⊗t|1〉 ⟶^QPE (1/√r) ∑_s=0^r−1 |φ̃_s〉|u_s〉, φ̃_s ≈ s/r

Run quantum phase estimation (prior result) on U_a with input |1〉 = (1/√r)∑_s|u_s〉. By linearity the control register lands, for each branch, on a t-bit estimate of the eigenphase s/r. Measuring gives x/2^t ≈ s/r with s uniform on {0, …, r−1}. B

| x/2^t − s/r | ≤ 1/2^t−n · ½ ≤ 1/2N² ≤ 1/2r²

With t = 2n+1 and 2ⁿ ≥ N > r, phase estimation delivers the best t-bit approximant to within 2⁻⁽ⁿ⁺¹⁾ ≤ 1/2N² (with success probability at least 4/π²). This is the tolerance the classical post-processing needs. C

| x/2^t − s/r | ≤ 1/2r² ⇒ s/r is a convergent of the continued fraction of x/2^t

By the classical continued-fraction theorem, any rational within 1/2r² of a target is one of its convergents, and each convergent is computed in O(n³) classical time. Scan the convergents for the one with denominator < N; in lowest terms its denominator is r/gcd(s,r), which equals r precisely when gcd(s, r) = 1. C

Pr[ gcd(s, r) = 1 ] = φ(r)/r = Ω(1 / log log r)

The count of s ∈ {0, …, r−1} coprime to r is Euler's totient φ(r); the totient bound φ(r)/r ≥ c/log log r guarantees a coprime s after O(log log r) repetitions, recovering the true r with high probability. C

r = ord_N(a) ⟶ factor = gcd(a^r/2 ± 1, N), valid when r even and a^r/2 ≢ −1 (mod N)

Reading. Phase estimation on the modular-multiplication unitary reads off a random multiple s/r of the reciprocal period; continued fractions strip the random numerator s to expose r; and a single even, non-trivial order hands two proper factors of N to Euclid's algorithm. The favourable-a condition (r even and a^r/2 ≢ −1) holds for at least half of the admissible bases, so a handful of random a suffices.

Units check. Every quantity is a dimensionless integer or a pure phase. Eigenphases s/r ∈ [0,1) are dimensionless fractions of a full turn; the measured x/2^t is a bit-fraction, also dimensionless; and the output gcd(·, N) is an integer in {2, …, N−1}. The gate count O(n² log log n) with n = ⌈log₂N⌉ is a pure number, confirming polynomial scaling in the input length.

Limiting cases

r = 1: means a ≡ 1, an uninformative base; discard and redraw a.
r odd: a^r/2 is not an integer, step 2 fails; redraw a (happens for at most half of bases).
a^r/2 ≡ −1 (mod N): then a^r/2+1 ≡ 0, both gcds are trivial (1 or N); redraw a.
N prime: no non-trivial factor exists; the algorithm is never run on primes (Miller–Rabin screens them out first).
r ≈ N (large period): the routine is unaffected — t = 2n+1 qubits already resolve any r < N; this is the generic and hardest classical case where the quantum speedup is largest.

Breaks when

Under-resolved control register (t < 2n+1). The estimate x/2^t is no longer within 1/2r² of s/r, so s/r need not appear among the continued-fraction convergents and r cannot be read out reliably.
Persistently unlucky bases. If every sampled a gives odd r or a^r/2 ≡ −1 (impossible in probability but adversarially constructible for special N such as prime powers, which are why they are excluded), no factor emerges. For genuine composites the failure probability per base is ≤ ½, so this is exponentially unlikely to persist.
Decoherence over the O(n³) modular-exponentiation circuit. The controlled-U_a^{2^j} stage is by far the deepest part; if the coherence time is shorter than this depth, phase errors accumulate, the eigenphase kickback washes out, and the measured distribution flattens toward uniform noise — no period signal survives. This, not the algorithm's logic, is the present engineering barrier.

Failure modes

Confusing the two registers. The t-qubit control register carries the phase; the n-qubit target register holds |a^k mod N〉. The inverse QFT acts on the control register only.
Reading r directly from the measurement. The raw outcome is x ≈ 2^ts/r, not r; students who skip the continued-fraction step get a meaningless integer.
Taking the convergent denominator as r when gcd(s, r) > 1. It is then r/gcd(s,r), a proper divisor; the fix is to test whether the candidate is a true order and, if not, combine denominators from two runs via lcm.
Forgetting to verify a^r ≡ 1. The recovered r is a guess; always confirm classically before using it, and take the least valid multiple.
Assuming a^r/2 ≡ −1 is impossible. It is a genuine failure branch (e.g. it can dominate for prime-power N), not a corner case to ignore.
Using QFT instead of QFT^†. Phase estimation ends with the inverse transform; the forward QFT sends the sharp phase register to the wrong basis.

Discussion

The heart of the algorithm is a change of viewpoint enabled by step 6: although the period r is unknown, the state |1〉 is automatically an equal superposition of all r eigenvectors of U_a. Phase estimation therefore samples the eigenphase spectrum {s/r} without ever preparing a single eigenstate. The quantum Fourier transform inside phase estimation is the abelian group Fourier transform that diagonalises the shift |a^k〉 ↦ |a^k+1〉; the “interference of amplitudes” that concentrates measurement probability onto x ≈ 2^ts/r is precisely the constructive/destructive interference of the waves thread, and the uniform sampling of s is the chance thread supplying the randomness that continued fractions later tame.

The symmetry thread runs deeper: order-finding is the hidden-subgroup problem for the homomorphism f : ℤ → ℤ_N^×, k ↦ a^k, whose kernel is the subgroup rℤ. Fourier analysis over the domain group ℤ (approximated by ℤ_2^t) exposes the annihilator of that hidden subgroup — the multiples of 1/r. Every efficient quantum algorithm in the abelian hidden-subgroup family — Simon's problem, discrete log, the Deutsch–Jozsa promise — is this same representation-theoretic mechanism in a different group.

The division of labour between the quantum and classical parts is instructive and often misread. The quantum device does not compute r; it produces a single noisy sample s/r with s uniformly random. All the number theory — continued fractions to invert the sampling, the totient bound to guarantee a coprime numerator, gcd to convert order into factor — is classical. What is quantum is exclusively the ability to evaluate f in superposition and Fourier-transform the resulting periodic structure in O(n²) operations, where any classical Fourier read-out of the period would need exponentially many evaluations of f. The speedup is entirely in the period-extraction subroutine, not in arithmetic.

Common misconceptions. Shor's algorithm does not “try all factors in parallel” — no branch of the superposition ever holds a factor of N; it holds a value of a^k mod N, and factoring emerges only after the classical gcd. Nor does it break all cryptography: it targets problems with hidden abelian periodicity (RSA, Diffie–Hellman, elliptic-curve discrete log), while lattice-based schemes have no known such structure and are the basis of post-quantum standards.

Worked examples

N = 15, choose a = 7, gcd(7, 15) = 1

15 is odd and not a prime power, and 7 is coprime, so order-finding applies. A

7¹=7, 7²=49≡4, 7³≡28≡13, 7⁴≡91≡1 (mod 15) ⇒ r = 4

The powers cycle with least return at exponent 4; phase estimation would report x/2^t ≈ s/4 for random s ∈ {0,1,2,3}, e.g. x/2^t = 0.25 → convergent 1/4 → r = 4. B

r = 4 even, a^r/2 = 7² ≡ 4 (mod 15), 4 ≢ −1 ≡ 14

The favourable condition holds, so both gcds are candidates for a factor. A

gcd(4 − 1, 15) = gcd(3, 15) = 3, gcd(4 + 1, 15) = gcd(5, 15) = 5

Euclid on a^r/2 ± 1 against N returns proper divisors. A

15 = 3 × 5

Reading. A single even order r = 4 with 7² ≡ 4 factors 15 completely. Units check. All integers: 3, 5 ∈ {2, …, 14} and 3 × 5 = 15 = N.

N = 21, choose a = 2, gcd(2, 21) = 1, n = ⌈log₂21⌉ = 5, t = 2n+1 = 11, 2^t = 2048

21 is odd and composite (not a prime power); the register sizes follow from the assumption t = 2n+1. A

2¹=2, 2²=4, 2³=8, 2⁴=16, 2⁵≡11, 2⁶≡64≡1 (mod 21) ⇒ r = 6

Least return at exponent 6, so the true eigenphases are multiples of 1/6. B

measure x = 341 (branch s = 1): x/2^t = 341/2048 = 0.16650…

Phase estimation returns the nearest 11-bit fraction to s/r = 1/6 = 0.16667; the error 1.6×10⁻⁴ < 1/2r² = 1/72 ≈ 0.0139, so recovery is guaranteed. B

341/2048 = [0; 6, 170, …], convergents 0/1, 1/6, …

Euclidean continued-fraction expansion: 2048 = 6·341 + 2 gives the partial quotient 6, so the convergent is 1/6, the first with denominator < 21. Since gcd(1, 6) = 1, the denominator is exactly r = 6. C

r = 6 even, a^r/2 = 2³ = 8 ≢ −1 ≡ 20; gcd(8−1,21)=gcd(7,21)=7, gcd(8+1,21)=gcd(9,21)=3

Favourable order; Euclid on 8 ± 1 against 21 yields both factors. A

21 = 3 × 7

Reading. An 11-qubit control register resolves the period-6 signal, continued fractions strip the numerator, and the even order factors 21. Units check. Integers throughout: 3, 7 ∈ {2, …, 20}, 3 × 7 = 21 = N; the register widths n = 5, t = 11 are pure counts.

Problems

For N = 15 and a = 2, find the order r by hand and determine whether it yields a factor.
Solution
2¹=2, 2²=4, 2³=8, 2⁴=16≡1 (mod 15), so r = 4. It is even and a^r/2 = 2² = 4 ≢ −1≡14. Then gcd(4−1,15)=gcd(3,15)=3 and gcd(4+1,15)=gcd(5,15)=5. Factors 3 and 5 — success.
Choose a = 14 for N = 15. Show it is an unfavourable base and explain what the algorithm does next.
Solution
14 ≡ −1 (mod 15), so 14² ≡ 1 and r = 2. Then a^r/2 = 14¹ = 14 ≡ −1 (mod 15), which is exactly the failure branch: gcd(14+1,15)=gcd(15,15)=15 (trivial) and gcd(14−1,15)=gcd(13,15)=1 (trivial). No factor. The algorithm discards this base and redraws a new random a; since at least half of admissible bases are favourable, few retries are expected.
A phase-estimation run on N = 21 (so 2^t = 2048) returns x = 1365. Recover the candidate order via continued fractions and check it.
Solution
1365/2048 = 0.66650…, close to 2/3 = 0.66667. Continued fraction: 2048 = 1·1365 + 683 (quotient 1), 1365 = 1·683 + 682 (quotient 1), giving convergents 0/1, 1/1, 1/2, 2/3, …. The first convergent with denominator < 21 matching to tolerance is 2/3, denominator 3. But gcd(2,3)=1 gives candidate r = 3, and 2³ = 8 ≢ 1 (mod 21), so 3 is only a divisor of the true order (here s = 2, r = 6, so the run reported s/r = 2/6 = 1/3 — reduced). Combine with another run (e.g. one giving denominator 6 or 2) via lcm(3, 2) = 6 to obtain the true r = 6.
Show that for any odd composite N that is not a prime power, a base a chosen uniformly from ℤ_N^× is favourable (r even and a^r/2 ≢ −1) with probability at least ½. (State the theorem; sketch why the prime-power exclusion matters.)
Solution
By the Chinese remainder theorem, ℤ_N^× ≅ ∏_i ℤ_{p_i^e_i}^× across the distinct prime-power factors. The theorem (Nielsen & Chuang, Thm 5.3) states that for N with at least two distinct odd prime factors, a uniformly random a coprime to N is unfavourable with probability ≤ 1/2^m−1 ≤ ½, where m ≥ 2 is the number of distinct prime factors. The proof pairs each unfavourable residue with a favourable partner across the CRT factors. If N = p^e were a prime power there would be a single factor (m = 1) and the bound would not hold — indeed the order structure can force a^r/2 ≡ −1 systematically — which is exactly why prime powers are stripped off by a classical N^1/k test before the quantum routine runs.
Estimate the number of control qubits t and the leading gate cost for factoring a 2048-bit RSA modulus, and comment on why this is not yet feasible.
Solution
Here n = 2048, so t = 2n + 1 = 4097 control qubits (logical), plus n = 2048 target qubits, i.e. of order 6000 logical qubits before ancillas for modular arithmetic (realistic circuits use ≈ 2n to 5n total). The dominant cost is modular exponentiation: naively O(n³) ≈ 8.6×10⁹ gates, or O(n² log n log log n) with fast multiplication. Infeasibility is not the logic but the error rate: a fault-tolerant run needs on the order of 10¹⁰ coherent operations, demanding physical error rates below ∼10⁻³ and, after surface-code overhead of 10³–10⁴ physical qubits per logical qubit, on the order of 10⁶–10⁷ physical qubits — far beyond present hardware of a few hundred noisy qubits.