Shor's Algorithm: How Quantum Computers Threaten to Break RSA Encryption
In 1994, mathematician Peter Shor showed that a sufficiently powerful quantum computer could factor large numbers exponentially faster than any known classical algorithm. That single result turned quantum computing from an academic curiosity into a subject of serious concern for banks, governments, and anyone who relies on encrypted communication. This post walks through what Shor's algorithm actually does, why factoring is so important, and how the quantum "magic" behind it works.
1. Why Factoring Large Numbers Matters
Modern secure communication — the padlock icon in your browser, encrypted messaging apps, online banking — relies heavily on a cryptographic system called RSA. RSA's security rests on one simple mathematical fact: it is easy to multiply two large prime numbers together, but extremely hard to reverse the process and find those two primes if you're only given their product.
For example, multiplying two 300-digit primes takes a computer a fraction of a second. But given only the 600-digit result, no known classical algorithm can find the original primes in any reasonable amount of time — even using every computer on Earth, it would take longer than the age of the universe for sufficiently large keys.
Public key = product of two large primes (easy to compute). Private key = the two primes themselves (hard to recover). Security depends entirely on factoring being computationally infeasible.
2. What Shor's Algorithm Does
Shor's algorithm is a quantum algorithm that factors large integers in polynomial time — meaning the time it takes grows manageably as the numbers get bigger, instead of exploding exponentially like classical methods. If run on a large enough, error-corrected quantum computer, it could factor a 2048-bit RSA key in hours or days, compared to the billions of years a classical supercomputer would need.
| Approach | Best Known Time Complexity | Practical Feasibility (2048-bit key) |
|---|---|---|
| Classical (General Number Field Sieve) | Sub-exponential, ~O(exp((64/9)^(1/3) (ln N)^(1/3) (ln ln N)^(2/3))) | Infeasible — longer than the age of the universe |
| Shor's Algorithm (Quantum) | Polynomial, ~O((log N)^3) | Feasible in principle, given a large fault-tolerant quantum computer |
3. The Key Insight: Factoring Is a Period-Finding Problem
Shor's real breakthrough wasn't a quantum trick for factoring directly — it was recognizing that factoring can be reduced to a different problem: finding the period of a mathematical function. And period-finding is something quantum computers are exceptionally good at.
Here's the connection. Suppose we want to factor a number N. We pick a random number a smaller than N, and look at the sequence:
This sequence is periodic — it eventually repeats. If we can find that period r (the smallest number such that a^r mod N = 1), we can use it to compute a factor of N using simple classical math (a greatest common divisor calculation). The hard part — finding r — is exactly what the quantum portion of the algorithm solves efficiently.
4. Step-by-Step Walkthrough
Choose a random integer a such that 1 < a < N.
Compute gcd(a, N) classically. If it's not 1, you've accidentally already found a factor — done!
Use a quantum computer to find the period r of the function f(x) = a^x mod N. This step uses superposition to evaluate the function on many values of x simultaneously, then applies a Quantum Fourier Transform (QFT) to extract the periodicity — this is the heart of the quantum speedup.
If r is odd, or if a^(r/2) ≡ -1 (mod N), the attempt fails — go back to step 1 and try a different a.
If r is even, compute gcd(a^(r/2) - 1, N) and gcd(a^(r/2) + 1, N). These are, with high probability, non-trivial factors of N.
5. Inside the Quantum Step: Superposition and the QFT
The quantum part of Shor's algorithm uses two registers of qubits. The first register is put into a superposition of all possible values of x at once, using Hadamard gates. Then a controlled modular exponentiation operation computes a^x mod N and stores it in the second register — entangling the two registers together.
Because of quantum parallelism, this single operation effectively evaluates the function for every value of x simultaneously — something no classical computer could do without repeating the calculation millions of times over.
The catch is that you can't just "read off" all these results — measuring a quantum register collapses it to one random value. This is where the Quantum Fourier Transform comes in. The QFT converts the periodic pattern hidden in the superposition into a new quantum state where the periodicity shows up as sharp, measurable peaks in probability. Measuring the first register after the QFT gives a value strongly related to the period r, which can then be recovered classically using a mathematical technique called continued fractions.
Register 1 is superposed, entangled with Register 2 via modular exponentiation, then transformed by an inverse QFT before measurement reveals the period.
6. A Worked Toy Example
Let's factor N = 15 (small enough to trace by hand). Choose a = 7.
7¹ mod 15 = 7
7² mod 15 = 4
7³ mod 15 = 13
7⁴ mod 15 = 1 ← the sequence repeats from here
The period is r = 4 (even, good). We compute:
gcd(7² − 1, 15) = gcd(48, 15) = 3
gcd(7² + 1, 15) = gcd(50, 15) = 5
And indeed, 15 = 3 × 5. A quantum computer finds this same period using superposition and the QFT — the payoff is that for enormous numbers, this quantum period-finding step stays fast, while the classical version would require checking an astronomical number of values of x one at a time.
7. Why This Matters for Cryptography
RSA (and related schemes like Diffie-Hellman and elliptic curve cryptography) underpin most of the internet's security infrastructure. A large-scale, fault-tolerant quantum computer running Shor's algorithm could, in principle, break these systems. This has triggered a global push toward post-quantum cryptography — encryption schemes based on mathematical problems believed to be hard even for quantum computers, such as lattice-based cryptography.
As of now, real quantum computers can only factor very small numbers (like 15 or 21) using Shor's algorithm, because building enough stable, error-corrected qubits remains a massive engineering challenge. Factoring a real 2048-bit RSA key would require thousands of logical qubits with strong error correction — likely millions of physical qubits with today's technology. Most experts estimate this is still years to decades away, but the risk is taken seriously enough that organizations like NIST have already standardized post-quantum encryption algorithms.
8. Key Takeaways
- Shor's algorithm factors large numbers exponentially faster than the best known classical methods.
- It works by transforming factoring into a period-finding problem.
- The quantum speedup comes from superposition (evaluating many values at once) and the Quantum Fourier Transform (extracting periodicity from that superposition).
- Its main real-world implication is breaking RSA and similar public-key cryptosystems — which is why post-quantum cryptography is now an active area of research and standardization.
- Practical, large-scale factoring with Shor's algorithm still requires quantum hardware far beyond what exists today.
0 Comments