Shor's Algorithm: How Quantum Computers Break RSA
Shor's algorithm is a quantum algorithm that can factor large numbers exponentially faster than classical computers, threatening RSA encryption. It works by reframing integer factorization as a period-finding problem, then using quantum mechanics to find that period via Fourier analysis and wave interference. Current quantum computers are too noisy to threaten real cryptography, but the threat is real enough to warrant post-quantum cryptography research now.
RSA and the Factorization Problem
RSA relies on the difficulty of factoring large semiprimes
RSA public key cryptography works because the public key N is a product of two large secret prime numbers P and Q. If an attacker can factor N to recover P and Q, they can derive the private key and forge signatures, impersonate servers, or launch phishing attacks. Factoring a realistic 2,000-bit RSA key would take hundreds of millions of years on classical computers.
RSA uses public key N = P × Q (both secret primes)
The RSA public key contains N, which is sent on digital certificates worldwide. The private key depends on the secret primes P and Q. As long as factoring N remains hard, the private key stays safe. Shor's algorithm changes this equation.
Shor's Algorithm: The Classical Part
Shor's algorithm has three phases: classical, quantum, classical
The algorithm starts with classical preprocessing, moves to a quantum period-finding subroutine, then returns to classical post-processing to extract the prime factors. This hybrid structure is key to its elegance.
Reframe factorization as period-finding
Instead of directly factoring N, Shor's algorithm picks a random number A and computes successive powers A^1 mod N, A^2 mod N, A^3 mod N, etc. This sequence eventually repeats with some period R. Finding R is much easier than factoring, and R directly leads to P and Q.
Example: Finding the period for N=15, A=2
Computing 2^k mod 15: 2^0=1, 2^1=2, 2^2=4, 2^3=8, 2^4=1, 2^5=2, 2^6=4, 2^7=8, 2^8=1... The sequence repeats with period R=4 (cycles 1→2→4→8→1). Once R is known, use the formula A^(R/2)+1 and find GCD with N to extract a prime factor.
Use difference of squares to factor
Once period R is found, A^R ≡ 1 (mod N) means A^R - 1 ≡ 0 (mod N). Factor as (A^(R/2) - 1)(A^(R/2) + 1) ≡ 0 (mod N). Since N = P×Q, one of these factors likely shares a prime with N. Compute GCD(A^(R/2) + 1, N) to extract P or Q directly.
Why Quantum? Fourier Transform and Periodicity
Physicists use Fourier transforms to find periodicity everywhere
From crystal lattices to the cosmic microwave background, physicists decompose complex patterns into sine and cosine waves to identify repeating frequencies. Shor's algorithm applies the same principle: decompose the modular exponentiation function into its frequency components to extract the period R.
Fourier decomposition breaks patterns into frequency components
A complex pattern (like a zebra crossing) can be represented as a sum of simple sine and cosine waves at different frequencies and phases. The Fourier spectrum shows which frequencies contribute most. For Shor's algorithm, the dominant frequency in the spectrum directly reveals the period R.
For N=15, A=2: period R=4 emerges as the dominant frequency
The sequence 1→2→4→8→1→2→4→8... repeats 4 times in a window of 16 slots. When computing the Fourier spectrum, the peak appears at k=4 cycles, revealing the period. This is exactly what a quantum computer does, but for 2,000-bit numbers where classical Fourier analysis is impossible.
Quantum Mechanics: Waves, Superposition, and Interference
Superposition is not parallel universes; it's wave interference
A qubit in superposition is not simultaneously in two parallel realities. Rather, it's like a sound wave that is a sum of multiple frequency components. Superposition happens everywhere in classical physics: musical instruments, images, radio signals. The quantum version uses the same principle—waves adding constructively or destructively.
Constructive and destructive interference control quantum outcomes
When two waves are in phase (peaks align), they add constructively to amplify the signal. When out of phase (peak meets trough), they cancel destructively. By precisely controlling the phase of quantum waves (via microwave pulses), quantum computers engineer interference patterns so the correct answer amplifies and wrong answers cancel out.
Trapped-ion quantum computers use two atomic energy levels as 0 and 1
A trapped ion has two energy states (low and high). Microwave pulses of precise duration and frequency can place the ion in a superposition of both states with any desired probability split. The ion's state is represented as an arrow on a circle (a phasor): the arrow's length encodes probability, and its rotation speed encodes energy.
Measurement collapses the quantum state and requires reset
When a laser fires at the trapped ion, photons reveal which state it is in. This measurement collapses the superposition into a definite outcome. To run the algorithm again, the system must be reset from scratch. Quantum algorithms are probabilistic: run many times, collect statistics, extract the answer from the distribution.
Phasor model: arrows represent quantum waves
A quantum state is represented as an arrow on a circle. The arrow's length squared gives the probability of measuring that state. The arrow's angle represents the phase (position on the wave cycle). Higher energy states spin faster. By controlling microwave pulses and waiting times, engineers control the arrow's length and angle to orchestrate constructive interference for the correct answer.
Quantum Fourier Transform in Shor's Algorithm
Quantum Fourier transform extracts the period automatically
The quantum computer applies a sequence of microwave pulses and waiting periods that implement the Fourier transform on the modular exponentiation function. This causes the quantum waves to interfere: the frequency corresponding to the period R constructively interferes and amplifies, while other frequencies cancel. Measurement then reveals R with high probability.
Same pulse sequence works for any N, regardless of size
The quantum Fourier transform algorithm is size-agnostic. Whether N is 15 or a 2,000-bit number, the same sequence of quantum gates (pulses, waits, measurements) extracts the period. This is why quantum computers gain exponential speedup: the number of operations grows polynomially with the number of bits, not exponentially.
Quantum speedup comes from wave interference, not parallel universes
The exponential speedup of Shor's algorithm is not because a quantum computer explores all possibilities in parallel universes. It is because quantum interference allows the algorithm to amplify the correct answer and cancel wrong answers in a single run. This happens in one universe, using one quantum computer.
Practical Challenges and Timeline
Current quantum computers can only factor numbers up to 15
Today's quantum computers are very noisy. Error correction requires many redundant qubits. The largest number factored by a quantum computer is 15 (in 2001). A 2,000-bit RSA key is far beyond current capability.
Quantum decoherence: environment noise washes out quantum effects
Quantum computers must be isolated from the environment (ultra-high vacuum, low temperature, electromagnetic shielding). Any coupling to the environment introduces random phase shifts that destroy the carefully orchestrated interference patterns. This decoherence limits how long a quantum computation can run.
Timeline to break RSA: 5 to 30+ years, or longer
Experts disagree on when quantum computers will be large and stable enough to factor 2,000-bit numbers. Estimates range from 5 years to 30+ years to potentially centuries. The uncertainty is why post-quantum cryptography research is urgent now.
Post-quantum cryptography must be deployed before quantum threat arrives
Because quantum computers could break RSA retroactively (decrypt old messages stored today), organizations should transition to post-quantum algorithms now, even though the threat is not immediate. This is a massive engineering and policy challenge.
Notable quotes
We can't do this integer factorization. That's too difficult. What we're going to do instead is create a function that loops periodically back to one. — Mike (classical explanation)
Everything we've talked about happened in this universe. We didn't have an infinite number of pixies in other universes doing the calculations for us. — Phil (quantum physicist)
Don't confuse the map with the territory. Don't confuse the model with actually what's happening in terms of reality. — Phil