Skip to content

Lesson 17: The Factorization Attack on RSA and Order Finding

17.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Derive the reduction from factoring to order finding and prove why it works.
  2. State and apply the success-probability theorem for a random base \(a\).
  3. Execute the classical part of Shor's algorithm by hand on small numbers.
  4. Explain why order finding is classically hard but quantum-easy.
  5. Survey the best classical factoring algorithms and place them against the quantum result.

17.2 The Strategy

Shor's algorithm is not a purely quantum algorithm. It is a hybrid:

CLASSICAL   reduce factoring to order finding
   QUANTUM  find the order r of a mod N      <-- the only quantum step
CLASSICAL   convert r into factors via gcd

This lesson covers the two classical halves. L20 covers the quantum core. Understanding the reduction first makes Shor's algorithm feel inevitable rather than magical.

17.3 The Reduction: From Factoring to Order Finding

The core identity

Let \(N\) be an odd composite, and let \(a\) be chosen with \(\gcd(a,N)=1\). Let \(r = \mathrm{ord}_N(a)\) be the order, so \(a^r\equiv1\pmod N\).

Suppose \(r\) is even. Then we may write

\[ a^{r} - 1 \equiv 0 \pmod N \]
\[ \left(a^{r/2}\right)^2 - 1 \equiv 0 \pmod N \]
\[ \big(a^{r/2}-1\big)\big(a^{r/2}+1\big) \equiv 0 \pmod N \]

So \(N\) divides the product \(\big(a^{r/2}-1\big)\big(a^{r/2}+1\big)\).

Key step. \(N\) does not divide either factor alone, provided:

  • \(a^{r/2}\not\equiv 1 \pmod N\) — guaranteed, because \(r\) is the smallest exponent giving 1, and \(r/2 < r\).
  • \(a^{r/2}\not\equiv -1 \pmod N\) — this is a genuine condition that may fail.

If both hold, then \(N\) shares a proper factor with each of \(a^{r/2}\mp1\), and

\[ \boxed{\ \gcd\!\left(a^{r/2}-1,\ N\right) \ \text{ and } \ \gcd\!\left(a^{r/2}+1,\ N\right) \ \text{ are non-trivial factors of } N .\ } \]

Both gcds are computed by the Euclidean algorithm in \(O(\log^2 N)\) time.

Why a^r/2≡-1 ruins it

If \(a^{r/2}\equiv -1\pmod N\) then \(a^{r/2}+1 \equiv 0\), so \(\gcd(a^{r/2}+1, N) = N\) — trivial. And \(\gcd(a^{r/2}-1,N) = \gcd(-2, N) = 1\) since \(N\) is odd — also trivial. Both gcds fail. Pick a new \(a\) and try again.

The success-probability theorem

Theorem. Let \(N\) be odd with at least two distinct prime factors, \(N = p_1^{k_1}\cdots p_m^{k_m}\) with \(m\ge2\). Choose \(a\) uniformly at random from \(\mathbb{Z}_N^{*}\) and let \(r = \mathrm{ord}_N(a)\). Then

\[ \Pr\Big[\,r \text{ is even \textbf{and} } a^{r/2}\not\equiv-1\ (\mathrm{mod}\ N)\,\Big] \ \ge\ 1 - \frac{1}{2^{m-1}} \ \ge\ \frac{1}{2} . \]

Consequence. Each random choice of \(a\) succeeds with probability at least \(\frac12\). After \(k\) attempts the failure probability is at most \(2^{-k}\); 10 attempts give failure probability under \(0.1\%\). So the expected number of quantum runs is a small constant.

Proof idea. By the Chinese Remainder Theorem, \(\mathbb{Z}_N^*\cong\prod_j\mathbb{Z}_{p_j^{k_j}}^*\), each factor being cyclic (for odd \(p\)). Write \(r_j = \mathrm{ord}_{p_j^{k_j}}(a)\) and let \(2^{d_j}\) be the largest power of 2 dividing \(r_j\). Then \(r = \mathrm{lcm}(r_j)\), and the bad event (\(r\) odd, or \(a^{r/2}\equiv-1\)) occurs exactly when all \(d_j\) are equal. A counting argument over the cyclic groups shows this has probability at most \(2^{-(m-1)}\). \(\blacksquare\)

17.4 The Complete Algorithm

INPUT: composite N

1.  If N is even, return factor 2.
2.  If N = b^k for integers b >= 2, k >= 2, return b.        (classical, easy)
3.  Choose a uniformly at random from {2, ..., N-1}.
4.  Compute g = gcd(a, N)  [Euclid].
        If g > 1, return g.                                  (a lucky guess!)
5.  QUANTUM: find r = ord_N(a).                              <== the only quantum step
6.  If r is odd, go to 3.
7.  Compute x = a^(r/2) mod N.
8.  If x == N-1  (i.e. -1 mod N), go to 3.
9.  Return gcd(x-1, N) and gcd(x+1, N).

Step 2 is necessary because the reduction requires at least two distinct prime factors; prime powers \(N = p^k\) must be handled separately (and are easy: test \(\sqrt[k]{N}\) for \(k \le \log_2 N\)).

Complexity.

Step Cost
gcd, primality, perfect-power tests \(O(\log^3 N)\) classical
Order finding (quantum) \(O(\log^3 N)\) gates, \(O(\log N)\) qubits
Expected repetitions \(O(1)\)
Total \(O(\log^3 N)\) — polynomial

Compare GNFS: \(\exp\big(O(\log^{1/3}N\,\log\log^{2/3}N)\big)\) — super-polynomial.

17.5 Why Order Finding Is Classically Hard

Given \(a\) and \(N\), finding the smallest \(r\) with \(a^r\equiv1\) appears to require searching. You cannot even enumerate the candidates efficiently, because \(r\mid\phi(N)\) and you do not know \(\phi(N)\) — computing it is equivalent to factoring.

The circular dependency:

\[ \text{factor } N \ \longleftrightarrow\ \text{compute } \phi(N) \ \longleftrightarrow\ \text{find } \mathrm{ord}_N(a) \]

All three are polynomial-time equivalent. Classically, breaking into this circle requires sub-exponential sieving.

The quantum key. The sequence \(a^0, a^1, a^2, \dots \pmod N\) is periodic with period \(r\). Periodicity is exactly what the Quantum Fourier Transform detects — and it detects it in one shot, not by scanning. This is Simon's algorithm (L15) transplanted from \((\mathbb{Z}_2)^n\) to \(\mathbb{Z}_N\).

17.6 The Classical Competition

Algorithm Complexity Best for
Trial division \(O(\sqrt N)\) tiny \(N\)
Fermat's method fast if \(p\approx q\) close primes
Pollard's rho \(O(N^{1/4})\) small factors
Pollard's \(p-1\) fast if \(p-1\) is smooth weak primes
Elliptic Curve Method (ECM) \(\exp(O(\sqrt{\log p\log\log p}))\) finding medium factors
Quadratic Sieve \(\exp(O(\sqrt{\log N\log\log N}))\) up to ~100 digits
General Number Field Sieve \(\exp\big(1.923(\ln N)^{1/3}(\ln\ln N)^{2/3}\big)\) the record holder
Shor (quantum) \(O(\log^3 N)\) all \(N\)

Records. RSA-250 (250 digits, 829 bits) was factored in 2020 with ≈2700 core-years. RSA-2048 would take an estimated \(10^{9}\) times longer — beyond reach for the foreseeable future classically.

17.7 Solved Problems

Problem 1 — Factoring 15 by hand

Factor \(N = 15\) using \(a = 7\).

Solution.

Step 4. \(\gcd(7,15) = 1\) ✓ (no lucky factor).

Step 5. Find \(r = \mathrm{ord}_{15}(7)\):

\[ 7^1 = 7,\quad 7^2 = 49 \equiv 4,\quad 7^3 \equiv 28 \equiv 13,\quad 7^4 \equiv 91 \equiv 1 \]
\[ r = 4 . \]

Step 6. \(r = 4\) is even ✓.

Step 7. \(x = 7^{4/2} = 7^2 = 49 \equiv 4 \pmod{15}\).

Step 8. \(x = 4 \ne 14 = N-1\) ✓.

Step 9.

\[ \gcd(4-1, 15) = \gcd(3,15) = \mathbf{3} \]
\[ \gcd(4+1, 15) = \gcd(5,15) = \mathbf{5} \]
\[ 15 = 3\times5 \ \checkmark \]

Problem 2 — A choice of a that fails, and one that works

Factor \(N = 21\). Try \(a = 8\), then \(a = 2\).

Solution.

Attempt with \(a = 8\). \(\gcd(8,21)=1\) ✓.

\[ 8^1 = 8,\quad 8^2 = 64 \equiv 1 \pmod{21} \]

so \(r = 2\), which is even ✓.

\[ x = 8^{1} = 8, \qquad x \ne 20 \ \checkmark \]
\[ \gcd(7, 21) = \mathbf{7}, \qquad \gcd(9,21) = \mathbf{3} \]
\[ 21 = 3\times 7 \ \checkmark \quad\text{— this one worked.} \]

Attempt with \(a = 2\).

\[ 2^1=2,\ 2^2=4,\ 2^3=8,\ 2^4=16,\ 2^5=32\equiv11,\ 2^6=22\equiv1 \]

\(r = 6\), even ✓. \(x = 2^3 = 8\), \(x \ne 20\) ✓.

\[ \gcd(7,21) = 7, \qquad \gcd(9,21)=3 \ \checkmark \]

Now a failing case: \(a = 20 \equiv -1\). \(r = 2\) (since \((-1)^2=1\)), even ✓, but \(x = 20^1 = 20 = N-1\). Step 8 rejects it. Indeed \(\gcd(19,21)=1\) and \(\gcd(21,21)=21\) — both trivial. Retry with a different \(a\).

Problem 3 — Factoring 91 and estimating the retry count

Factor \(N = 91\) with \(a = 3\). Then compute the theoretical lower bound on the per-attempt success probability.

Solution.

\(\gcd(3,91)=1\) ✓. Find \(r = \mathrm{ord}_{91}(3)\). Note \(91 = 7\times13\), so \(\phi(91) = 6\times12 = 72\) and \(r \mid 72\).

\[ 3^1=3,\ 3^2=9,\ 3^3=27,\ 3^4=81,\ 3^5 = 243 = 2\times91+61\equiv61 \]
\[ 3^6 \equiv 183 = 2\times91+1 \equiv \mathbf{1} \]
\[ r = 6 . \]

Even ✓. \(x = 3^{3} = 27\). \(x \ne 90\) ✓.

\[ \gcd(26, 91) = \mathbf{13}, \qquad \gcd(28,91) = \mathbf{7} \]
\[ 91 = 7\times13 \ \checkmark \]

Success probability bound. \(N = 91\) has \(m = 2\) distinct prime factors, so

\[ \Pr[\text{success}] \ge 1 - \frac{1}{2^{m-1}} = 1 - \frac12 = \frac12 . \]

Expected attempts \(\le 2\). With 10 attempts, failure probability \(\le 2^{-10} < 0.1\%\).

(Empirically, for \(N=91\) the actual success rate over all valid \(a\) is about 76 % — the theorem's bound is conservative.)

Problem 4 — Working backwards from a quantum output

A quantum order-finding run on \(N = 55\), \(a = 2\) returns \(r = 20\). Verify \(r\), complete the factorisation, and check the answer.

Solution.

Verify \(r\). \(55 = 5\times11\), \(\phi(55) = 4\times10 = 40\), so \(r\mid40\) ✓ (\(20\mid40\)).

\[ 2^{10} = 1024 = 18\times55 + 34 \equiv 34 \pmod{55} \]
\[ 2^{20} \equiv 34^2 = 1156 = 21\times55 + 1 \equiv \mathbf{1} \ \checkmark \]

And \(2^{10}\equiv34\ne1\), so no smaller divisor of 20 works among \(\{1,2,4,5,10\}\) — check \(2^4=16\), \(2^5=32\), both \(\ne1\) ✓. So \(r = 20\) exactly.

Complete the reduction. \(r = 20\) even ✓.

\[ x = 2^{10} \equiv 34 \pmod{55}, \qquad x \ne 54 \ \checkmark \]
\[ \gcd(33, 55) = \mathbf{11}, \qquad \gcd(35,55) = \mathbf{5} \]
\[ 55 = 5\times11 \ \checkmark \]

Note how little classical work this is: two Euclidean algorithms on 6-bit numbers. All the difficulty was concentrated in producing the number 20.

Problem 5 — Resource estimate for RSA-2048

Estimate the classical GNFS effort and the quantum resources needed to factor a 2048-bit RSA modulus. Comment on the timeline.

Solution.

Classical (GNFS). The heuristic complexity is

\[ L_N\!\left[\tfrac13, 1.923\right] = \exp\!\left(1.923\,(\ln N)^{1/3}(\ln\ln N)^{2/3}\right) . \]

With \(N = 2^{2048}\): \(\ln N = 2048\ln2 = 1419.6\), so \((\ln N)^{1/3} = 11.24\); \(\ln\ln N = \ln1419.6 = 7.258\), so \((\ln\ln N)^{2/3} = 3.73\).

\[ \text{exponent} = 1.923 \times 11.24 \times 3.73 = 80.6 \]
\[ \text{effort} \approx e^{80.6} \approx 10^{35} \ \text{operations}. \]

At \(10^{18}\) operations/second (an exascale machine devoted entirely to this):

\[ t \approx 10^{17}\ \mathrm{s} \approx 3\times10^{9}\ \text{years} . \]

Quantum (Shor). Gate count scales as \(O(n^3)\) with \(n = 2048\):

\[ n^3 = 2048^3 = 8.6\times10^{9} \ \text{logical operations (order of magnitude)}. \]

Logical qubits needed: about \(2n + O(\log n) \approx 4100\).

Physical resources. With surface-code overhead of \(\sim10^3\)–\(10^4\) physical qubits per logical qubit:

\[ 4100 \times 3000 \approx \mathbf{1.2\times10^{7}\ \text{physical qubits}} . \]

Published estimates (Gidney & Ekerå, 2021) give 20 million noisy physical qubits and about 8 hours at a \(10^{-3}\) gate error rate — a substantial optimisation over earlier billion-qubit estimates.

Timeline comment. Current devices have \(10^2\)–\(10^3\) physical qubits with error rates near \(10^{-3}\). The gap is roughly four orders of magnitude in qubit count. Estimates for crossing it range from 10 to 30 years, with wide uncertainty. Because of "harvest now, decrypt later", and because NIST published ML-KEM/ML-DSA in August 2024, migration to post-quantum cryptography is already underway for long-lived secrets. The correct posture is to migrate now, not to wait for the machine.

17.8 Practice Problems

  1. Factor \(N=33\) using \(a=5\). [Ans: \(r=10\), \(x=5^5\equiv 23\), gcds give 11 and 3]
  2. Factor \(N=35\) using \(a=6\). Does it succeed? [Ans: \(r = 2\), \(x = 6 \ne 34\); gcds give 5 and 7 ✓]
  3. Factor \(N = 39\) using \(a = 5\). [Ans: \(r=4\), \(x=25\), gcds give 3 and 13]
  4. For \(N=15\), \(a=14\): show that the attempt fails and explain which condition is violated.
  5. Prove that if \(r\) is odd, the reduction gives no information.
  6. Why is Step 2 (perfect-power test) required?
  7. If \(N\) has 3 distinct prime factors, what is the guaranteed success probability? [Ans: \(\ge 3/4\)]

17.9 Summary

  • Shor's algorithm is hybrid: classical reduction → quantum order finding → classical gcd.
  • If \(r = \mathrm{ord}_N(a)\) is even and \(a^{r/2}\not\equiv-1\pmod N\), then \(\gcd(a^{r/2}\pm1, N)\) are non-trivial factors.
  • A random \(a\) satisfies both conditions with probability \(\ge 1 - 2^{-(m-1)} \ge \frac12\), so \(O(1)\) attempts suffice.
  • Factoring, computing \(\phi(N)\) and order finding are all polynomial-time equivalent; classically all are hard because you cannot enumerate the divisors of an unknown \(\phi(N)\).
  • Order finding is a period-finding problem, which is what the QFT solves — the same structure as Simon's algorithm over a different group.
  • Classical best is GNFS (sub-exponential, \(\approx10^{35}\) operations for RSA-2048); Shor is \(O(\log^3N)\) but needs \(\sim10^7\) physical qubits with today's error rates.

Next lesson: L18 — The Quantum Fourier Transform.

Practise now: unit2-algorithms-lab.html → Shor Workbench: enter any \(N\) up to 10 000, watch the algorithm pick \(a\), compute the order (by simulation), and complete the factorisation, with a running tally of successful and failed attempts.