The Promise: Shor’s algorithm is a famous quantum algorithm that can factor integers exponentially faster than the best known classical algorithms. This capability threatens the security of modern encryption systems like RSA.
The Roadmap: The algorithm works by converting the factoring problem into a period-finding problem, which quantum computers can solve efficiently. The steps are: Factoring $\rightarrow$ Period-finding $\rightarrow$ Factors.
RSA encryption, the backbone of secure internet communication (like HTTPS), relies on the mathematical difficulty of factoring a large number $N$.
$N$ is created by multiplying two large prime numbers, $P$ and $Q$. While multiplying them is computationally cheap (easy for your browser), "un-multiplying" (factoring) $N$ to retrieve $P$ and $Q$ is incredibly difficult for anyone trying to eavesdrop.
As the number $N$ grows in size (more bits), the time required to check divisors explodes exponentially. It's a "trapdoor" function: easy to fall in (multiply), impossible to climb out (factor).
For a 2048-bit number, even the world's fastest supercomputers working together would take longer than the age of the universe to find the factors using classical methods.
Peter Shor realized that we don't need to attack the factoring problem head-on by checking every possible number.
We can transform the problem into Period Finding. If we can find the repeating pattern (period $r$) of a specific modular function, simple mathematics can convert that period into the factors of $N$. Quantum computers are excellent at finding patterns.
Let's choose a small number to factor: $N = 15$. We want to find $P$ and $Q$ such that $P \times Q = 15$.
First, we pick a random number $a < N$ that doesn't share any factors with $N$. Let's pick $a = 2$.
Goal: Find the period (how often the sequence repeats) of the function $f(x) = 2^x \bmod 15$.
Let's compute the sequence $2^x \bmod 15$ (which means $2^x$ divided by 15, keep the remainder):
$2^1 = 2 \rightarrow 2$
$2^2 = 4 \rightarrow 4$
$2^3 = 8 \rightarrow 8$
$2^4 = 16 \rightarrow 1$ (since $16 = 1 \times 15 + 1$)
The sequence repeats (2, 4, 8, 1...), so the period is $r = 4$. Finding this $r$ is the hard part for large numbers.
Once we have the period $r=4$, we can use a mathematical trick to find the factors.
We calculate the greatest common divisor (GCD) of $(a^{r/2} \pm 1)$ and $N$.
$a^{r/2} = 2^{4/2} = 2^2 = 4$
$\gcd(4-1, 15) = \gcd(3, 15) = 3$
$\gcd(4+1, 15) = \gcd(5, 15) = 5$
We found the factors: 3 and 5! We broke the encryption.
The classical steps we just did work fine for small numbers like 15.
But for huge numbers used in encryption (hundreds of digits long), the period $r$ can be incredibly large. Calculating the sequence one by one to find when it repeats would take forever.
Shor's algorithm uses a quantum computer to find $r$ efficiently, without checking every number.
Superposition: We use quantum superposition to represent every possible input number $x$ simultaneously. It's like spinning a coin that is both heads and tails.
Quantum Parallelism: We perform the calculation $a^x \bmod N$ on all these inputs at once. The result is encoded in the quantum state.
Interference: We then use interference (like noise-canceling headphones) to cancel out the wrong answers and amplify the correct period.
We use two quantum registers (groups of qubits).
Register 1: The input counter. We put this in a superposition of all integers from 0 to a large number.
Register 2: The output. We compute $f(x) = a^x \bmod N$ and store it here.
Because of quantum entanglement, the two registers are linked. The outputs in Register 2 repeat with the hidden period $r$.
If we measure Register 2, it collapses to a single random value, say $y$.
Because the registers are entangled, Register 1 also changes. It collapses to a superposition of only the $x$ values that produced that specific $y$.
Crucially, these remaining $x$ values are spaced apart by exactly the period $r$. The pattern is now stamped into Register 1.
If we measured Register 1 now, we would just get a random number, which wouldn't tell us the spacing ($r$). The periodicity is hidden in the amplitudes (probability waves).
We apply the Quantum Fourier Transform (QFT). Just like a musical chord reveals its notes in a frequency analyzer, the QFT processes the quantum state to reveal the frequency (period) as sharp peaks in probability.
The QFT concentrates the probability so that when we measure, we get a value $y$ that is highly likely to be close to a multiple of $2^n/r$.
By dividing our measurement by the total size of the register ($y/2^n$), we get a fraction that approximates $k/r$. We use a classical algorithm called Continued Fractions to find the denominator $r$ from this approximation.
Back to our example: $N=15, a=2$. The period is $r=4$.
The QFT produces probability peaks near fractions with denominator 4: $0, \frac{1}{4}, \frac{2}{4}, \frac{3}{4}$.
Measuring the quantum state gives us one of these fractions. If we measure $0.75$ ($\frac{3}{4}$), the denominator tells us $r=4$.
Shor's algorithm is probabilistic—it doesn't work 100% of the time.
Sometimes we get an odd period $r$ (which we can't use), or the factors turn out to be trivial (1 and N). Or we might measure a peak that doesn't give us the full period.
That's okay! We just pick a new random $a$ and try again. The success rate is high enough that a few tries are usually sufficient.
Classical: The best known methods are sub-exponential. Adding a few bits to the key length makes the problem much, much harder.
Quantum: Shor's algorithm is polynomial. Adding bits to the key only increases the difficulty slightly.
This exponential speedup is what makes large-scale quantum computers a threat to RSA. They turn an impossible problem into a manageable one.
Does this break RSA today?
No. We need thousands of perfect logical qubits (which requires millions of physical qubits for error correction) to factor large numbers.
Current quantum computers are noisy and small. However, the threat of "Harvest Now, Decrypt Later" means we need to upgrade our encryption before powerful quantum computers arrive.
Shor's algorithm proves that our current locks (RSA, ECC) have a mathematical weakness: Periodicity. Quantum computers will eventually find it.
The solution is Post-Quantum Cryptography (PQC). We are moving to new math problems, like Lattice Cryptography, which involve finding points in high-dimensional grids. These problems have no known quantum shortcuts.
The transition is happening now. NIST has standardized algorithms like Kyber (ML-KEM) to secure the internet against the quantum threat.