Part 3: Algorithms 12 min read

Shor's Algorithm

The security of most internet encryption depends on one mathematical fact: factoring large numbers is practically impossible for classical computers. Shor's algorithm makes it feasible for quantum computers - and that changes everything about cryptography.

Why factoring matters

When you visit a bank website, send a private message, or make an online payment, your data is protected by encryption. The most widely used public-key encryption systems - RSA, Diffie-Hellman, and elliptic curve cryptography - all rest on the same mathematical assumption: given two large prime numbers multiplied together, it is computationally infeasible to factor the result back into those primes.

Multiplying two 300-digit prime numbers takes a fraction of a second. Finding those primes given only the product takes classical computers so long - longer than the age of the universe for large enough numbers - that it is considered practically impossible. The entire security of modern internet infrastructure relies on this asymmetry. It is the same one-way difficulty as mixing two paint colors versus un-mixing them: blending blue and yellow into green takes a second, but staring at the green and recovering the exact original shades of blue and yellow is far harder - the information about the ingredients is still in there, it is just computationally painful to extract.

In 1994, Peter Shor published an algorithm showing that a quantum computer could factor large numbers in polynomial time - time that grows as a polynomial in the number of digits, not exponentially. A quantum computer running Shor's algorithm would break RSA encryption. This single algorithm is responsible for much of the urgency around both quantum computing development and post-quantum cryptography research.

Period finding: the core problem

Shor's algorithm does not directly try to factor N. Instead, it reduces factoring to a different problem: finding the period of a modular exponential function.

Pick a random number a (less than N, and with no common factors with N). Consider the sequence: a¹ mod N, a² mod N, a³ mod N, a⁴ mod N, and so on. This sequence is periodic - it repeats with some period r, much like the hour hand on a clock cycling back to 12: the actual numbers it lands on look unpredictable step to step, but eventually the pattern loops back to where it started, and that loop length is the period. If you can find r, and if r is even, then a^(r/2) + 1 and a^(r/2) − 1 share common factors with N. Those common factors are likely to be the prime factors of N.

Classically, finding the period r requires testing many values - roughly as hard as factoring directly. Shor's algorithm uses the Quantum Fourier Transform to find r efficiently in quantum time.

The Quantum Fourier Transform

The Quantum Fourier Transform (QFT) is one of the most important quantum subroutines. It transforms a quantum state by performing a Fourier analysis on the amplitudes - converting from the "value basis" to the "frequency basis," similar to how the classical Fast Fourier Transform (FFT) decomposes a signal into its component frequencies.

The QFT can be implemented using O(n²) quantum gates on n qubits. The best classical FFT requires O(n × 2ⁿ) operations - exponentially more. This exponential advantage is what makes Shor's algorithm fast: applying the QFT to the periodic state created by modular exponentiation extracts the period r in polynomial time.

The QFT is built from Hadamard gates and controlled phase rotation gates (the S and T gates you have seen in the Sandbox, plus smaller phase rotations). Its circuit structure is beautiful: a cascade of Hadamards and phase shifts applied to each qubit, creating an interference pattern that "peaks" at the frequency of the input periodicity.

Try it in the Sandbox

Explore the Quantum Fourier Transform circuit

Open Algorithm Preset and select QFT (2-qubit).
Examine the circuit. H gates on each qubit, followed by controlled phase rotations.
Check the probability distribution. Peaks correspond to dominant frequencies in the input.
Note the phase display. QFT moves information between amplitudes and phases.
This is a tiny preview. Real Shor's needs hundreds of qubits and millions of gate operations.

Shor's algorithm step by step

The complete algorithm has these phases:

1. Classical preprocessing. Check obvious cases: is N even? (If so, 2 is a factor.) Is N a prime power? (These can be checked classically.) Pick a random a less than N and compute gcd(a, N). If it is not 1, you found a factor - done.

2. Quantum period finding. Prepare a quantum state over superpositions of x values. Apply the modular exponentiation function f(x) = aˣ mod N as a quantum circuit. Apply the QFT. Measure. The result is a multiple of N/r, which reveals r after classical post-processing.

3. Classical post-processing. Use the measured value and number theory to compute r. Check if r is even and aʳ/² ≠ −1 mod N. If so, compute gcd(aʳ/² ± 1, N) to get the prime factors. If the conditions fail, pick a new random a and repeat.

The quantum speedup is entirely in step 2. Everything else is classical. The algorithm is probabilistic - it succeeds with high probability and may need to be run a few times, but each run is polynomial time.

What this means for cryptography today

A fault-tolerant quantum computer running Shor's algorithm on RSA-2048 (the current standard) would require roughly 4,000 logical qubits and millions of gate operations. With current error rates, that corresponds to millions of physical qubits - far beyond today's hardware.

But the threat is taken seriously now because of a strategy called "harvest now, decrypt later." An adversary can record encrypted traffic today and decrypt it when a sufficiently powerful quantum computer becomes available in the future. Long-term secrets - government communications, medical records, financial data - have a long shelf life and may be vulnerable.

This is why NIST (the U.S. National Institute of Standards and Technology) standardized new post-quantum cryptographic algorithms in 2024. These are mathematical problems believed to be hard even for quantum computers. The transition to post-quantum cryptography is already underway.

Key takeaway

Shor's algorithm uses the Quantum Fourier Transform to find the period of a modular exponential function, reducing the factoring problem to an efficient quantum computation. It would break RSA and elliptic curve cryptography if run on a fault-tolerant quantum computer - driving urgent development of post-quantum cryptographic standards.

Knowledge check · Question 1 of 4

Why does RSA encryption rely on multiplying two large primes together rather than some other operation?

RSA's security depends entirely on this asymmetry: computing the product is easy, but reversing it - factoring - takes classical computers an impractically long time for large enough numbers, similar to how mixing two paint colors is trivial but separating them back out is not.

Knowledge check · Question 2 of 4

Why is the "harvest now, decrypt later" attack a concern even before large quantum computers exist?

Encrypted communications captured today can be stored for years or decades. When a sufficiently powerful quantum computer eventually arrives, all that stored data becomes readable - so data that needs to remain secret for a long time must be protected now with post-quantum cryptography.

Knowledge check · Question 3 of 4

What gives the Quantum Fourier Transform its advantage over the classical Fast Fourier Transform in Shor's algorithm?

The QFT's gate count scales polynomially (O(n²)) instead of exponentially (O(n × 2ⁿ)) like the classical FFT. Applying it to the periodic state from modular exponentiation is what lets Shor's algorithm extract the period r in polynomial time.

Knowledge check · Question 4 of 4

In Shor's algorithm, which part of the process actually requires a quantum computer?

Only step 2 - quantum period finding - needs a quantum computer. The classical preprocessing and post-processing steps (checking easy cases, computing gcd) run on ordinary hardware; the quantum speedup is entirely confined to finding r efficiently.