Factoring Reduces to Order Finding

Shor's algorithm has a clever shape. You might expect a quantum factoring algorithm to directly pull p and q out of N using quantum interference. It does not. Instead, it reaches for a completely different number-theoretic problem — one that, from the outside, has nothing to do with factoring — and uses a pre-existing classical result to connect the two.

The problem is order-finding. Given N and a random integer a between 2 and N-1 (with a coprime to N), the multiplicative order of a modulo N is the smallest positive integer r such that

If you could find r, it turns out you can factor N. Not always, but with probability at least 1/2, and you only need the factoring to work once — any success tells you a factor and you're done.

This chapter explains the reduction. No quantum mechanics appears anywhere in these pages. The reduction is elementary number theory, stitched together from Fermat-style modular identities and the Euclidean algorithm. It is the kind of result a motivated undergraduate can prove in a lecture. What makes it interesting is that Shor's algorithm sits on top of it — the quantum computer does only the order-finding, and this classical wrapper does the rest.

The reduction, in one picture

The entire Shor algorithm is a sandwich.

The top slice is trivial: pick a, run Euclidean gcd with N, branch. The bottom slice is the content of this chapter — given r, produce a factor. The middle slice, where the quantum magic happens, is covered in chapters 76–77.

Why the reduction works — the one key identity

The entire reduction hinges on a single observation. Suppose you have r such that a^r \equiv 1 \pmod N, and suppose further that r is even. Then

Factor the left-hand side using the difference-of-squares identity, which is just the observation that X^2 - 1 = (X-1)(X+1):

Why this factorisation: a^r = (a^{r/2})^2 by laws of exponents, so a^r - 1 is a perfect square minus one, which factors as a product of two consecutive integers either side of a^{r/2}. Elementary algebra, but it is the only load-bearing move.

Define x = a^{r/2} \bmod N. Then

This is the miracle. Two integers, x - 1 and x + 1, whose product is divisible by N. If neither of them is divisible by N individually — that is, if x \not\equiv \pm 1 \pmod N — then N must share some prime factor with x - 1 and some other prime factor with x + 1. In that case, the greatest common divisor \gcd(x - 1, N) is a proper, non-trivial divisor of N. A factor.

Write that out explicitly:

The \gcd is cheap — the Euclidean algorithm runs in O((\log N)^2) time — so if you have r, you have a factor in milliseconds.

What can go wrong. Two failure modes:

1. r is odd. Then a^{r/2} is not an integer (it is an integer raised to a half-power), and the factorisation a^r - 1 = (a^{r/2} - 1)(a^{r/2} + 1) doesn't hold over the integers. You cannot use this r. Retry with a different random a.
2. r is even but x = a^{r/2} \equiv -1 \pmod N. Then x + 1 \equiv 0 \pmod N, so \gcd(x+1, N) = N — trivial. And x - 1 \equiv -2 \pmod N, so \gcd(x-1, N) is usually just \gcd(-2, N) = \gcd(2, N) = 1 or 2 — also essentially trivial. Both gcds give no useful factor. Retry with a different a.

The case x \equiv +1 \pmod N cannot happen: if a^{r/2} \equiv 1 \pmod N, then by definition r/2 is an exponent at which a returns to 1, but r was supposed to be the smallest such positive exponent, so r/2 < r is a contradiction. You can safely rule this out.

Why r was chosen to be the smallest: the definition of "order" — the smallest positive r with a^r \equiv 1 \pmod N — is exactly what rules out the x \equiv 1 case. If you used any exponent r' with a^{r'} \equiv 1 (not necessarily the smallest), r'/2 could also give a^{r'/2} \equiv 1, and the reduction wouldn't work. The quantum order-finding algorithm does return the smallest r, which is why it matters that we define order this way.

Why it succeeds with probability at least 1/2

The failure modes — r odd, or x = -1 \pmod N — are not catastrophic. For any odd composite N with at least two distinct prime factors, a theorem of Ekert and Jozsa (tightening an earlier result by Miller and Rabin) says:

Fact. If N is odd, composite, and not a prime power, and a is chosen uniformly at random from the integers in \{1, \ldots, N-1\} coprime to N, then

So at least half the time, the reduction works and you get a factor. If it fails, you draw a new a and try again. After k attempts, the probability of never succeeding is at most (1/2)^k. Twenty attempts give you 2^{-20} \approx 10^{-6} failure probability — essentially guaranteed.

Why the bound is only \geq 1/2, not something larger: the proof goes through the Chinese Remainder Theorem. For N = p_1^{e_1} \cdots p_k^{e_k}, the multiplicative group mod N decomposes as a product of groups mod p_i^{e_i}, each cyclic of order \varphi(p_i^{e_i}). The condition "r even and a^{r/2} \not\equiv -1" translates into conditions on the 2-adic valuations of a's order in each factor — and when N has at least two distinct primes, those conditions agree with probability at most 1/2. The proof is a page of elementary group theory; the lower bound is tight for some N.

This is why the full Shor algorithm has a repeat loop built in: pick a, find order, try the reduction, if it fails pick a new a and go again. The expected number of attempts before success is at most 2.

Why N needs to be odd, composite, and not a prime power. Each exclusion is mild:

• N even (2 \mid N) is handled classically: just divide out all factors of 2 before calling Shor.
• N prime is detected in polynomial time by the Miller-Rabin primality test; in that case, N has no non-trivial factors to find.
• N a prime power (N = p^k for some prime p) is detected by classical root-extraction: try N^{1/k} for k = 2, 3, \ldots, \log_2 N and check if any root is an integer prime. This takes O((\log N)^3) time classically.

After these classical pre-checks, what's left is the case the reduction handles: odd, composite, not a prime power. Which is exactly the interesting case — RSA moduli N = pq with p and q distinct large primes.

A full worked factoring — N = 15 via order-finding

The canonical warm-up example is N = 15 = 3 \times 5. Small enough to do by hand, structured enough to show every step of the reduction. The quantum order-finding can be simulated on paper, so this is a complete factoring — reduction wrapper and all — with nothing hidden.

A second worked example — N = 21 showing the retry

A slightly larger example shows the retry mechanism in action: the first a you pick might fail, and you have to pick another.

What this means for the quantum part

Zoom out for a moment. The reduction above shows that factoring is no harder than order-finding — if you can solve order-finding, you can factor. The converse is also true: order-finding is no harder than factoring (see "Going deeper" below). So the two problems are computationally equivalent: an efficient algorithm for either gives an efficient algorithm for the other.

Why, then, is Shor's algorithm phrased as order-finding rather than as direct factoring? Because order-finding has a quantum-native structure that factoring does not. The function f(k) = a^k \bmod N is periodic with period r, and the quantum Fourier transform excels at extracting periods from periodic functions. Direct factoring — pull p and q out of N — has no such periodic structure. The reduction lets Shor's algorithm attack the easy-looking quantum version of the problem and then translate the answer back to factoring through pure classical number theory.

This is a pattern you will see throughout quantum algorithms. The reduction is classical. The core subroutine exploits some mathematical structure — periodicity, symmetry, an interference pattern — that quantum mechanics is natively good at. Shor's algorithm, the HHL linear-systems algorithm, and quantum chemistry all share this shape: classical wrapper, quantum core.

Common confusions

• "Factoring is hard because order-finding is hard." It is more subtle than that. Order-finding is classically as hard as factoring (they are computationally equivalent). Shor's algorithm makes order-finding easy quantumly, which is what cracks factoring. The relationship is symmetric: breaking either problem quantumly breaks both.
• "The reduction needs quantum." No. Every step in this chapter is pure classical arithmetic. The only quantum step — finding r — is an opaque subroutine here. The next chapters expose its guts.
• "We always find a factor." No. For each random a, the reduction succeeds with probability at least 1/2. On failure, you retry with a new a. Failures are easy to detect (either r is odd or a^{r/2} \equiv -1 \pmod N), and the expected number of attempts is \leq 2.
• "Order-finding is defined for any a." Only for a coprime to N. If \gcd(a, N) > 1 the order does not exist (because a is a zero-divisor mod N) — but in that lucky case, \gcd(a, N) is itself already a non-trivial factor of N, and you never need order-finding at all. The classical pre-processing step catches this.
• "Any r with a^r \equiv 1 works." Only the smallest r is guaranteed to work via the reduction. If you use a multiple of the true order, r/2 might land on a value where a^{r/2} \equiv 1 (not -1), and the reduction becomes ambiguous. Quantum order-finding is specifically designed to return the smallest r (more precisely, to return a rational approximation k/r with small denominator, from which the true r is recovered by continued fractions).

Going deeper

Proof that the success probability is at least 1/2

Let N = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} be an odd composite with at least two distinct prime factors. For each i, let r_i be the order of a modulo p_i^{e_i}. By the Chinese Remainder Theorem, the order r of a modulo N is the least common multiple of the r_i.

Write each r_i = 2^{v_i} \cdot m_i with m_i odd, where v_i \geq 0 is the 2-adic valuation. Then r = \text{lcm}(r_i) has v(r) = \max_i v_i. The reduction fails in two cases:

• r odd: This happens iff every v_i = 0, i.e., a has odd order modulo every p_i^{e_i}.
• r even and a^{r/2} \equiv -1 \pmod N: This happens iff a^{r/2} \equiv -1 \pmod{p_i^{e_i}} for every i.

Miller (1976) showed that for random a coprime to N, the probability of the combined failure event — "odd order modulo every factor, or a^{r/2} \equiv -1 in every factor" — is at most 2^{1-k} where k is the number of distinct prime factors. For k = 2 (the RSA case), this is 1/2. For k \geq 3, the success probability is even higher.

The proof uses the structure of the multiplicative group modulo p^e, which is cyclic of order \varphi(p^e) = p^{e-1}(p-1). In a cyclic group, the fraction of elements with any specific 2-adic valuation pattern is exactly 1/2 per factor — which combines multiplicatively via CRT. The full argument is a few pages in Nielsen and Chuang §5.3.2.

The reverse reduction — order-finding from factoring

Suppose you could factor any N. Can you find orders?

Given N and a coprime to N, factor N = p_1^{e_1} \cdots p_k^{e_k}. Then \varphi(N) = \prod p_i^{e_i - 1}(p_i - 1) is an exact multiple of every element's order. Factor \varphi(N) itself, and the order of a is the smallest divisor of \varphi(N) for which a^d \equiv 1. You can check divisors of \varphi(N) in polynomial time (there are at most O(\log \varphi(N)) prime factors, so only O(2^{\log \varphi(N)}) divisors — but the greedy approach of removing one prime factor at a time works in polynomial time).

This shows factoring implies order-finding. Combined with the forward reduction, the two problems are polynomial-time equivalent.

The same trick for discrete logarithm — ch. 82 preview

Shor's algorithm also breaks the discrete logarithm problem: given g, h, p, find x such that g^x \equiv h \pmod p. The reduction is analogous: express the DLP as a period-finding problem over a two-dimensional function f(k, \ell) = g^k h^{-\ell} \bmod p, which is periodic along the diagonal (k, \ell) = (x m, m) where m is a parameter. Quantum Fourier transform on the two-dimensional lattice extracts this diagonal, from which x falls out.

Since elliptic-curve cryptography (ECC) is built on discrete logarithm in elliptic-curve groups, Shor's algorithm also breaks ECC. This doubles the cryptographic stakes: RSA, finite-field Diffie-Hellman, and ECC all fall to variants of the same quantum circuit.

Why prime powers need separate handling

The reduction as stated requires N to have at least two distinct prime factors. For N = p^e (a prime power), two things break down:

• The 2^{1-k} bound on failure probability becomes 2^0 = 1 — no useful guarantee.
• The difference-of-squares factorisation (a^{r/2} - 1)(a^{r/2} + 1) always gives \gcd(x \pm 1, N) equal to either 1 or p^e — both trivial.

Classical root-extraction handles prime powers separately: for each candidate k from 2 to \log_2 N, compute \lfloor N^{1/k} \rfloor using Newton's method, test whether its k-th power equals N, and check if that base is prime. Total cost O((\log N)^3). So in the Shor pipeline, you check for prime-power structure classically before invoking the quantum order-finder.

Indian context — where this matters

Every RSA-2048 modulus used in Aadhaar signatures, UPI transactions, and banking TLS is specifically the "interesting case" for this reduction: odd, composite, the product of exactly two large primes, not a prime power. The classical pre-checks (test for 2, test for primality, test for prime-power) all pass through quickly, and the reduction-success probability is the full 1/2.

When India's National Quantum Mission researchers build early demonstrations of Shor's algorithm on Indian-built hardware — the NQM's Thematic Hub on quantum computing, headquartered at IIT Madras, has exactly this on its 2028 roadmap — the first milestones will be factoring small primes-products (15, 21, 35, 91) exactly as shown in this chapter. The target for 2030s is factoring semiprimes of up to 8 bits using fully fault-tolerant circuits, after which scaling to cryptographically relevant sizes becomes an engineering problem of error-correction overhead rather than an algorithmic one.

Where this leads next

• Order Finding — The Quantum Idea — how quantum phase estimation on the modular-multiplication operator extracts r in polynomial time.
• The Shor Circuit End to End — the complete quantum circuit for Shor's algorithm, wrapped in the classical reduction shown here.
• Factoring and RSA — why factoring matters: the cryptosystems whose security depends on it.
• Discrete Logarithm Quantumly — the parallel reduction that lets Shor's algorithm break elliptic-curve cryptography as well.

References

1. Peter Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer (1994) — arXiv:quant-ph/9508027. The original paper; the reduction in this chapter is in §4.
2. Gary Miller, Riemann's Hypothesis and Tests for Primality (1976) — DOI:10.1016/S0022-0000(76)80043-8. The original probabilistic-factoring argument.
3. Nielsen and Chuang, Quantum Computation and Quantum Information (2010), §5.3.2 — the cleanest textbook presentation of the reduction and its probability analysis — Cambridge University Press.
4. John Preskill, Lecture Notes on Quantum Computation, Chapter 6 — theory.caltech.edu/~preskill/ph229.
5. Wikipedia, Shor's algorithm — the reduction and classical post-processing section.
6. Wikipedia, Multiplicative order — definitions and basic properties.