Shor's Algorithm Overview

Understand the algorithm that threatens RSA encryption.

Shor's Algorithm: Factoring with Quantum Computing

Shor's algorithm, published by Peter Shor in 1994, can factor large integers in polynomial time: a problem believed to be classically intractable for large numbers. It is the reason quantum computers threaten RSA encryption and why post-quantum cryptography is now a priority.

Why factoring is hard classically:

Given a composite number N = p × q where p and q are large primes, the best known classical algorithm (the General Number Field Sieve) runs in sub-exponential time: approximately exp(∛(64/9 · ln N · (ln ln N)²)). For N with 2048 bits (RSA-2048), this requires computational effort beyond all current classical resources.

Shor's key insight: reduction to period-finding:

Shor realized that factoring reduces to finding the period r of the function:

$f (x) = a^{x} mod N$

where a is a randomly chosen number coprime to N. Once r is found:

•If r is even, compute $g cd (a^{r /2} \pm 1, N)$
•With high probability, this gives a non-trivial factor of N

Example: Factor N=15 using a=7. The period of $7^{x} mod 15$ is $r = 4$ (since $7^{4} = 2401 = 160 \times 15 + 1$ ). Then $g cd (7^{2} - 1, 15) = g cd (48, 15) = 3$ and $g cd (7^{2} + 1, 15) = g cd (50, 15) = 5$ . Factors found: 3 and 5.

Why quantum computers find periods faster

The period-finding step requires evaluating $f (x) = a^{x} mod N$ for exponentially many values of x simultaneously. A quantum computer prepares the superposition (1/√Q)∑|x⟩|0⟩ over the Q = 2^n values of the n-qubit counting register, applies the modular exponentiation $U_{f}$ to get (1/√Q)∑|x⟩|f(x)⟩, then applies the QFT to the first register. The QFT converts the periodic structure into peaks at multiples of Q/r = 2^n/r: measuring one such peak gives information about r. Classical computers cannot do this superposition trick.

The quantum subroutines:

Shor's algorithm combines:

1.Classical preprocessing — choose random a, check gcd(a,N) (already a factor if not 1)
2.Quantum phase estimation — use QPE with the unitary $U_{a} ∣ x ⟩ = ∣ a x mod N ⟩$ to find the eigenphase $φ = k / r$
3.Classical postprocessing — use continued fractions to extract r from φ, then compute gcd

This is the opening of the lesson. The full walkthrough, the interactive circuit, and the graded challenge continue inside myqubit.

How this lesson works

A guided reading lesson with interactive knowledge checks. Concepts are explained step by step with circuit diagrams and runnable examples, and you confirm understanding before moving on.

Part of: Quantum Algorithms

Learn the algorithms that make quantum computers powerful.

Previous lessonQuantum Phase Estimation Next lessonShor's Algorithm Capstone

This lesson is part of Pro

Unlock Quantum Algorithms and all 10 tracks with Pro: $12.99/month, $79/year, or $97 lifetime. Start with the free track first if you are new.

Create account Try the Playground