Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 39 ยท Quantum Algorithms

Shor's Algorithm: Factoring with Quantum Computers

Follow Shor's factoring algorithm from number theory to quantum order finding, with a simulated run that factors 15 and a continued-fraction step.

In 1994, Peter Shor showed that a quantum computer can factor an integer N in time polynomial in log N. The best known classical algorithms are sub-exponential but far from polynomial. Since the security of RSA rests on factoring being hard, this result is the reason governments and companies are moving to post-quantum cryptography (see Quantum Cryptography and Key Distribution).

The surprise is how little of Shor's algorithm is quantum. Factoring reduces, by classical number theory, to order finding: given a and N, find the smallest r > 0 with a^r = 1 (mod N). Only that step uses the quantum computer, via phase estimation and the QFT.

From factoring to order finding

Take an odd composite N that is not a prime power, and pick a random a with 1 < a < N.

  1. If gcd(a, N) > 1, that gcd is already a factor. Done (lucky).
  2. Otherwise find the order r of a modulo N (the quantum step).
  3. If r is odd, or a^(r/2) = -1 (mod N), choose a new a.
  4. Otherwise gcd(a^(r/2) - 1, N) and gcd(a^(r/2) + 1, N) are non-trivial factors.

Why step 4 works: a^r - 1 = (a^(r/2) - 1)(a^(r/2) + 1) is divisible by N, but neither bracket alone is (by the exclusions in step 3). So N shares a factor with each of them. For a random a, the failure chance in step 3 is at most 1/2, so a couple of tries suffice.

Python The classical wrapper around order finding

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For N = 15 and a = 7 the order is 4 (7, 4, 13, 1), giving gcd(48, 15) = 3 and gcd(50, 15) = 5.

The quantum part: order finding

Choose Q = 2^q with Q >= N^2. The circuit has two registers:

  1. Put the first register (q qubits) in uniform superposition: (1/sqrt(Q)) * sum over x of |x>.
  2. Compute f(x) = a^x mod N into the second register, giving sum of |x>|a^x mod N>.
  3. Measure the second register. Suppose you read the value f0. The first register collapses to an equal superposition of all x with a^x = f0, which are x0, x0 + r, x0 + 2r, ...: a periodic state with period r.
  4. Apply the QFT to the first register. As in the QFT lesson, amplitude concentrates near multiples of Q/r.
  5. Measure to get y. Then y/Q is very close to s/r for a random integer s.
  6. Use continued fractions on y/Q to recover the denominator r.
flowchart LR
    A["Superpose x"] --> B["Compute a^x mod N"]
    B --> C["Measure 2nd register"]
    C --> D["QFT on 1st register"]
    D --> E["Measure y"]
    E --> F["Continued fractions: y/Q ~ s/r"]
    F --> G["Order r"]

Quantum order finding: the quantum steps produce a number y near a multiple of Q/r, and classical code extracts r.

A simulated run for N = 15

A real circuit would need many qubits for modular exponentiation. We can still simulate the mathematics exactly: build the state after step 3, take its transform with an FFT (identical to the QFT up to the sign convention), and sample.

Python Simulated quantum order finding, a=7, N=15

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sometimes s shares a factor with r (for example s = 2, r = 4 gives 1/2), and you recover only a divisor of r. The code above checks a^r = 1 and retries. Real implementations also try small multiples of the candidate.

How big is the quantum cost?

The expensive part is step 2, modular exponentiation a^x mod N as a reversible circuit. Implemented with repeated squaring and fast multiplication, it needs O(n^2 log n)-ish gates for an n-bit modulus, on roughly 2n to 3n logical qubits (optimized constructions use fewer than 2n + 3).

  • Factoring an RSA-2048 modulus is estimated to need on the order of a few thousand logical qubits, which translates to millions of physical qubits with the error correction covered in Quantum Error Correction and Surface Codes, and many hours of runtime.
  • Public demonstrations so far have factored tiny numbers like 15 and 21, often with circuits simplified using prior knowledge of the answer. They show the principle, not a threat.

Do not treat "quantum computers can break RSA" as a present-day fact. It is a future capability. But data encrypted today could be recorded now and decrypted later ("harvest now, decrypt later"), which is why migration to post-quantum algorithms has already started.

The same period-finding core solves discrete logarithms, which breaks Diffie-Hellman and elliptic-curve cryptography. Both are instances of the hidden subgroup problem, which also includes Simon's problem. Symmetric ciphers like AES are only affected by Grover's quadratic speed-up, so doubling the key size is enough.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which step of Shor's algorithm needs a quantum computer?

    Everything else is classical. Order finding is done with superposition, modular exponentiation and the QFT.
  2. 2. For N = 15 and a = 7, what order r do you find and what factors follow?

    7^4 = 2401 = 1 (mod 15). gcd(7^2 - 1, 15) = gcd(48, 15) = 3 and gcd(7^2 + 1, 15) = gcd(50, 15) = 5.
  3. 3. What does the QFT do to the periodic state after measuring the second register?

    Constructive interference occurs only near multiples of Q/r, so y/Q is close to s/r.
  4. 4. Why is symmetric encryption (AES) less affected than RSA?

    Brute-force search costs about 2^(k/2) with Grover; doubling the key length restores the security margin.

Summary

  • Factoring reduces to order finding by number theory: gcd(a^(r/2) +- 1, N) yields factors for an even order with a^(r/2) != -1.
  • The quantum part prepares a periodic state with modular exponentiation, uses the QFT to get a number near s * Q / r, and continued fractions recover r.
  • The work is polynomial in log N, but practical RSA-breaking needs millions of physical qubits.
  • Prepare now: post-quantum cryptography protects data against future decryption.

Next: Noise and Decoherence