The classical number theory at the heart of Shor's algorithm — how finding the period of modular exponentiation lets us factor integers.
Shor's algorithm factors a composite integer N in two stages:
1. Classical reduction — convert factoring into finding the period of the function f(x) = ax mod N.
2. Quantum subroutine — use quantum phase estimation to find that period efficiently.
This page focuses entirely on stage 1: the purely classical, number-theoretic argument that transforms a factoring problem into a period-finding problem. No quantum mechanics here — just modular arithmetic and one elegant algebraic trick (the difference of squares).
We are given a composite odd integer N that we want to factor. We may assume:
The strategy: pick a random integer a with 1 < a < N and use it to probe the structure of N. We check that a is coprimeTwo integers are coprime if their greatest common divisor (gcd) equals 1, meaning they share no prime factors. to N.
Because the set {1, 2, …, N−1} with gcd(a, N) = 1 forms a finite groupThe multiplicative group mod N: the set of integers from 1 to N−1 that are coprime to N, with multiplication mod N as the operation. under multiplication mod N, the sequence a0, a1, a2, … (mod N) must eventually cycle. The length of that cycle is the orderThe order (or period) of a modulo N is the smallest positive integer r such that ar ≡ 1 (mod N). (or period) r of a modulo N.
Suppose we have found the period r. Then:
If r is even, we can write this as a difference of squaresThe algebraic identity a² − b² = (a − b)(a + b). Here applied with a = ar/2 and b = 1.:
This means N divides the product (ar/2 − 1)(ar/2 + 1). If neither factor is itself a multiple of N, then N must share a non-trivial common factor with at least one of them. We can extract those factors efficiently with the Euclidean algorithmAn efficient method for computing the greatest common divisor of two integers, running in O(log N) time — very fast even for large numbers.:
The method fails when:
In either case we simply pick a new random a and try again. This succeeds after a few attempts with high probability.
One can show (using the Chinese Remainder TheoremA theorem that describes the structure of the group ℤ/Nℤ when N factors as a product of coprimes: the group splits as a direct product.) that for a random a coprime to N, the probability that r is even and ar/2 ≢ −1 (mod N) is at least 1 − 1/2k−1, where k is the number of distinct prime factors of N.
For the simplest case, N = pq (two distinct primes), the success probability is at least 1/2. After a few random tries, we factor N with overwhelming probability.
function FACTOR(N):
if N is even: return 2
if N = a^b for some a, b ≥ 2: return a
repeat:
pick random a ∈ {2, …, N−1}
g ← gcd(a, N)
if g > 1: return g // lucky: a shares a factor
r ← FIND_ORDER(a, N) // ← quantum subroutine
if r is odd: continue
if a^(r/2) ≡ −1 (mod N): continue
p ← gcd(a^(r/2) − 1, N)
q ← gcd(a^(r/2) + 1, N)
return p, qChoose an N to factor and a base a, then step through the reduction one step at a time.
See which values of a succeed and which fail for a given N. This builds intuition for why random selection works.
The reduction itself is classical — but the period-finding step is the bottleneck.
Classically, finding the order of a mod N requires computing a1, a2, …, ar mod N and checking each one for equality with 1. The period r can be as large as N itself, so this brute-force search takes up to O(N) = O(2n) steps for an n-bit number — exponential in the input size.
Quantum phase estimation creates a superposition over all exponents x, applies modular exponentiation as a single unitary operation, then extracts the period via the Quantum Fourier Transform. The full circuit uses O(n3) gates for an n-bit N — polynomial, not exponential.
The quantum speedup is not about factoring directly — it is about efficiently detecting hidden periodicity. The function f(x) = ax mod N is periodic, but extracting that period from its outputs is classically hard. Quantum phase estimation can detect this periodicity in polynomial time because interference amplifies the periodic signal. The classical reduction on this page is what makes that quantum capability useful for factoring.
How long would period finding take at different input sizes, assuming 109 operations per second?
| Bits of N | N (approx) | Classical brute force | Quantum (Shor) |
|---|---|---|---|
| 10 | ~103 | < 1 ms | < 1 ms |
| 20 | ~106 | < 1 sec | < 1 ms |
| 50 | ~1015 | ~12 days | < 1 ms |
| 100 | ~1030 | ~1021 years | < 1 sec |
| 2048 | ~10616 | ~10607 years | ~minutes |
Classical brute force: O(N) = O(2n) modular multiplications to scan all possible periods.
Quantum (Shor): O(n3) gates where n = number of bits. Times are rough order-of-magnitude estimates.
Test your understanding of the factoring-to-period-finding reduction. Click an answer to check it.
Use the Interactive Explorer and Batch Explorer above to investigate these questions.
Set N = 15 and try base a = 14 in the Interactive Explorer (try N=15, a=14). What happens? Now try a = 11 (try N=15, a=11). Which failure condition does each one hit? Use the Batch Explorer for N=15 and identify all bases that fail due to ar/2 ≡ −1.
For a = 14: the order is r = 2 (even), but 141 mod 15 = 14 ≡ −1 (mod 15). This is the −1 failure. For a = 11: the order is r = 2, and 111 mod 15 = 11 ≠ 14, so gcd(10, 15) = 5 and gcd(12, 15) = 3 — success! In the Batch Explorer, a = 4 and a = 14 are the only bases that fail via the −1 condition. Notice 4 ≡ −11 and 14 ≡ −1 (mod 15).
For N = 21, use the Batch Explorer for N=21 to find all bases that produce period r = 6. How many are there? Euler's totientφ(N) counts how many integers from 1 to N−1 are coprime to N. For N = pq, φ(N) = (p−1)(q−1). gives φ(21) = φ(3)φ(7) = 2 × 6 = 12. What is the relationship between the possible orders and φ(N)?
The possible orders must divide φ(N) = 12. So the possible orders are: 1, 2, 3, 4, 6, 12. Run the batch to see how many bases have each order. Bases with order 6 include a = 2, 5 among others. The number of elements of order d equals φ(d) in each cyclic subgroup, but the full group (ℤ/21ℤ)* ≅ ℤ/2ℤ × ℤ/6ℤ is not cyclic, so the distribution is richer.
Compare the success rates for N=15, N=77, and N=221 using the Batch Explorer. Are they all above the theoretical 50% lower bound? Which N has the highest success rate, and can you guess why?
Run the Batch Explorer for each. All three exceed 50%. The success rate depends on the structure of p−1 and q−1: when these have few common factors, more random bases yield even orders with the non-trivial property. N = 77 = 7 × 11 has p−1 = 6 and q−1 = 10, with gcd(6,10) = 2. N = 221 = 13 × 17 has p−1 = 12 and q−1 = 16, with gcd(12,16) = 4, leading to relatively more failure cases.
Success probability per attempt: at least 50% for N = pq. A handful of random attempts suffice.
This page showed the classical reduction — the "outer loop" of Shor's algorithm. The next module, Period Finding, tackles the quantum inner loop: how phase estimation and the QFT efficiently extract the period r that we need here.