Shor's Algorithm & Period r
How quantum physics cracks classical encryption in hours.
The Problem: Why Current Encryption is Crumbling
In our Prime Factorisation lesson, we saw that multiplying two secret primes (p × q = N) is effortless, but reversing it takes classical computers over 10⁶⁰
tests, creating an impenetrable 3.4-billion-year wall.
From Trial Division to Wave Interference
A quantum computer does not break RSA by brute-forcing trial division faster. Instead, it relies on a clever mathematical translation discovered by Peter Shor, paired with quantum wave interference:
1. Testing Divisors Sequentially
To factor N = p × q, classical computers have no
general shortcut beyond trial division: testing candidate primes
one by one (N ÷ 3, N ÷ 5, N ÷ 7...). With over 10⁶⁰
candidate primes guarding an RSA-2048 key, sequential testing
hits an insurmountable time barrier.
Binary: One State at a Time
Classical bits are strictly 0 or 1. Every candidate divisor requires its own distinct calculation step. Without a mathematical bypass, classical supercomputing clusters run out of time long before finding the matching factors.
2. Shor's Algorithm: Finding the Period
In 1994, mathematician Peter Shor showed that factoring can be
reframed as finding the repeating cycle (period r) of
modular powers: f(x) = aˣ mod N. Once the period r is determined, standard greatest-common-divisor (GCD) arithmetic
directly uncovers p and q.
Quantum: Wave Interference
Qubits take advantage of superposition and wave interference. Using the Quantum Fourier Transform (QFT), destructive interference cancels out incorrect values while constructive interference amplifies the true period r. This reduces billions of years of sequential guessing to roughly eight hours of quantum runtime.
What is the Period r?
In modular arithmetic, when you raise a coprime number a to increasing powers and take the remainder modulo N (evaluating aˣ mod N), the sequence of remainders
doesn't continue indefinitely into chaos; it repeats in an exact cycle:
ax + r ≡ ax (mod N) ⟹ ar ≡ 1 (mod N) 1. The Repeating Wave
The smallest positive integer r is the period (or order). It represents the exact wavelength of the repeating sequence, just like measuring the crest-to-crest distance of an ocean wave.
2. The Classical Bottleneck
Finding r classically requires calculating a¹, a², a³... one by one until the cycle loops back to 1. For a 2048-bit modulus
N, the cycle length r can be as large as N itself, taking billions of years to trace.
3. Why Period r Breaks RSA
Once r is an even number, basic algebra yields (ar/2 - 1)(ar/2 + 1) = k × N. This means the prime factors p and q are hidden within those two brackets! Running a simple classical
GCD test against N extracts the secret primes in milliseconds.
4. The Quantum Shortcut
Instead of checking powers one by one, a quantum computer feeds all values of x simultaneously into a quantum state. The Quantum Fourier Transform (QFT) measures the wave frequency of the repeating pattern, pinpointing r in roughly eight hours.
How Shor's Algorithm Works: The Radio Tuning Analogy
Imagine RSA's secret lock is a hidden radio station broadcasting on an unknown frequency. A classical computer has to scan every possible channel one by one. A quantum computer tunes into all channels simultaneously, letting wave interference silence the wrong ones and amplify the right one. Here is how that works in four stages:
Interactive Demonstration: Tuning In to N = 15
Follow along as we use the radio analogy to factor the number 15 into its secret prime building blocks (3 and 5). Each stage below lights up as the algorithm progresses.
The Secret Station
The analogy: RSA's lock number (N = 15) has a hidden signal repeating inside it.
What really happens: Multiplying 7 by itself and wrapping at 15 creates a loop:
The signal repeats every 4 steps. This hidden rhythm is the "station frequency" we need to find.
Quantum Radio Scan
The analogy: A quantum radio tunes into ALL channels simultaneously. Wrong channels cancel each other out like noise-cancelling headphones.
What really happens: The quantum computer tests every possible value at once. Wave interference silences wrong answers and produces a sharp resonance spike at the correct frequency.
The spike reveals: the signal repeats every 4 steps. Period r = 4 detected!
Locked On
The analogy: Now that we've locked on to the station frequency, we decode the broadcast to extract the secret combination.
What really happens: We cut the cycle in half (4 / 2 = 2), then compute 7 squared = 49. The numbers beside 49 are 48 and 50. Their product (48 x 50 = 2,400) is a perfect multiple of 15, which means the primes are trapped inside!
The secret primes are hiding in 48 and 50.
Code Cracked!
The analogy: The station frequency is decoded. The secret combination is revealed: the lock is open.
What really happens: A regular laptop asks: "What do 48 and 15 share in common?" Answer: 3. "What do 50 and 15 share?" Answer: 5. Done in under a millisecond.
🔓 Secret Primes: 3 x 5 = 15
How Shor's Algorithm Cracks RSA (The Radio Analogy)
RSA's secret is two prime numbers multiplied together (N = 15 = 3 x 5). A classical computer has to guess these primes one by one. Shor's algorithm uses quantum physics to find them in a completely different way. Click 'Next' to see how.
