Shor's Algorithm
Break RSA encryption with quantum factorization
1. What is Shor's Algorithm?
Shor's algorithm is the quantum algorithm that could break RSA encryption - the security protecting your bank accounts, passwords, and private communications. Discovered by Peter Shor in 1994, it can factor large numbers exponentially faster than any known classical algorithm, threatening the foundation of modern cryptography.
💡 Core Concept
RSA encryption relies on the fact that factoring large numbers is extremely hard for classical computers. A 2048-bit number would take billions of years to factor classically. Shor's algorithm uses quantum superposition and the Quantum Fourier Transform to find periods in modular arithmetic, reducing factoring from exponential to polynomial time - breaking RSA in hours instead of eons.
🔓 Why This Matters
When quantum computers become powerful enough to run Shor's algorithm on 2048-bit numbers, most of today's internet security will be broken. Banks, governments, and tech companies are racing to develop post-quantum cryptography before "Q-Day" arrives - the day quantum computers threaten global cybersecurity.
2. The Factoring Problem
🔐 Why Factoring Large Numbers Is Hard
The Asymmetry Problem
Factoring exhibits a profound computational asymmetry:
Takes milliseconds, even for huge numbers (1000+ digits)
Can take billions of years for large numbers (2048 bits)
Key insight: This asymmetry is a one-way function—easy in one direction, practically impossible in reverse. It's the foundation of modern cryptography!
How RSA Exploits This
RSA encryption relies on the difficulty of factoring:
Example: 1024-bit primes (hundreds of digits each)
Takes microseconds even for 2048-bit numbers
N is public. If attacker can factor N = p × q, they break encryption. But classically, factoring takes longer than age of universe for 2048-bit N!
Real-world scale: RSA-2048 means N is a 2048-bit number (~617 digits). Current record for classical factoring: 829-bit number in 2020, took ~2700 CPU-years. 2048 bits? Infeasible!
Classical Factoring Algorithms
Best known classical approaches:
For 2048-bit N: ~10^308 operations. Completely impractical.
For 2048-bit N: ~2^117 operations. Still ~10^35 times longer than age of universe!
For 2048-bit N: ~2^33 operations. Doable in hours on a large quantum computer!
Why Quantum Computers Break This
Must check possibilities sequentially or in limited parallelism. The search space grows exponentially with bit length. No amount of Moore's Law can overcome exponential growth.
Quantum computers can evaluate the function f(x) = a^x mod N for all x simultaneously using superposition. Instead of trying 2^2048 values sequentially, quantum superposition processes them in parallel.
The Quantum Fourier Transform uses interference to extract the hidden period from the superposition. Wrong answers cancel (destructive interference), correct answer amplifies (constructive). This is impossible classically!
The paradigm shift: Shor's algorithm doesn't factor directly. It reduces factoring to period finding, which quantum computers can do exponentially faster through QFT. This clever reduction + quantum mechanics = RSA broken.
The Cryptographic Crisis
RSA has protected internet security for 40+ years. Online banking, HTTPS, VPNs, code signing—all rely on factoring being hard. Shor's algorithm makes factoring polynomial instead of exponential, destroying this assumption. The difference is astronomical: what takes 10^35 years classically takes 8 hours quantumly. This isn't gradual progress—it's a catastrophic break. The entire edifice of public-key cryptography crumbles when large quantum computers arrive. That's why governments and corporations are urgently deploying post-quantum algorithms that don't rely on factoring. The race is on: deploy new crypto before quantum computers reach critical scale (~4,000 logical qubits needed for RSA-2048).
🔢 Interactive: Choose a Number to Factor
Problem:
Computational Complexity:
🎲 Interactive: Choose a Random Base
Step 1: Pick Random a (1 < a < N):
Check GCD:
3. Quantum Period Finding
🔄 Period Finding: The Key to Factoring
What Is Period Finding?
Given a function f(x) = a^x mod N, find the period r—the smallest positive integer where:
Meaning: a^r mod N = 1, and r is the smallest such exponent
Why this matters: The function repeats every r steps. This periodicity is hidden in the exponents but reveals the factors of N!
How Period Leads to Factors
Once we find the period r, classical algebra extracts the factors:
This means: a^r - 1 is divisible by N
Both factors share divisors with N!
With high probability, p and q are non-trivial factors of N!
Concrete example: N=15, a=7, r=4 → a^(r/2)=7^2=49 → gcd(49-1, 15)=gcd(48,15)=3, gcd(49+1, 15)=gcd(50,15)=5 → 15 = 3 × 5 ✓
Why Classical Period Finding Is Hard
Compute a^1, a^2, a^3, ... mod N until finding a^r = 1
• For 2048-bit N: ~10^617 computations
• Each modular exponentiation is slow for large numbers
Use Fast Fourier Transform to detect periodicity
• Need 2^n samples for n-bit number
• Exponential time complexity: O(2^n)
The bottleneck: Classically, you must evaluate f(x) = a^x mod N for exponentially many x values. No clever classical algorithm can avoid this exponential cost.
Quantum Superposition: The Game Changer
Quantum computers solve period finding exponentially faster:
Use Hadamard gates to create superposition: |0⟩ + |1⟩ + |2⟩ + ... + |2^n-1⟩
Apply f(x) = a^x mod N to the superposition
Measuring |a^x mod N⟩ collapses to one value, say y
These x values are evenly spaced by the period r!
Quantum Fourier Transform reveals the spacing (period r)
Measurement gives r with high probability
Time complexity: O((log N)³) quantum operations vs O(2^(log N)) = O(N) classical. For N=2^2048, this is 2^33 vs 2^2048 operations—astronomical difference!
Shor's Algorithm: The Complete Picture
Choose 1 < a < N. Check if gcd(a, N) > 1 (lucky factor). Time: O(log N)
Use quantum algorithm to find period of f(x) = a^x mod N. Time: O((log N)³)
If r is odd or a^(r/2) ≡ -1 (mod N), restart. Success probability: ~50%
Compute p = gcd(a^(r/2)-1, N) and q = gcd(a^(r/2)+1, N). Time: O(log N)
Total time: O((log N)³) dominated by quantum period finding (step 2). Classical steps are negligible. Expected ~O(1) repetitions due to 50% success rate.
The Elegant Reduction
Shor's brilliance wasn't just using quantum mechanics—it was reducing factoring to period finding, a problem where quantum computers have exponential advantage. The reduction is pure number theory (known for centuries), but period finding was classically hard. Quantum superposition + QFT makes period finding efficient, and the factoring reduction comes along for the ride. This clever transformation is why Shor's algorithm works: it exploits quantum interference patterns in modular arithmetic. The period is encoded in the phase relationships of the superposition, and QFT reads it out through measurement. Classical computers can't access these phase relationships—they're fundamentally quantum mechanical. That's the magic: math + quantum physics = broken cryptography.
🔄 Interactive: Run Shor's Algorithm
🌊 Quantum Fourier Transform: Reading Quantum Interference
What Is the Quantum Fourier Transform?
The Quantum Fourier Transform (QFT) is the quantum analog of the discrete Fourier transform. It converts between two representations of a quantum state: the computational basis (position/time domain) and the Fourier basis (momentum/frequency domain). In Shor's algorithm, QFT extracts the hidden period from a quantum superposition by converting periodic patterns into sharp frequency peaks.
QFT vs Classical FFT
Exponential speedup: For n=2048 qubits, classical FFT needs 2^2048 × 2048 ≈ 10^620 operations. QFT needs ~2048² ≈ 4 million operations. That's the quantum advantage!
How QFT Reveals the Period
After quantum modular exponentiation, the state contains periodic structure:
Superposition of states evenly spaced by period r. The period is implicit in the spacing between non-zero amplitudes.
Peaks appear at multiples of N/r. The period r is explicit in the peak spacing! Measuring gives k×(N/r) for some integer k, from which we extract r.
Mathematical magic: Time-domain periodicity with spacing r transforms to frequency-domain peaks with spacing N/r. This is the discrete Fourier transform duality—QFT exploits quantum interference to compute it efficiently!
The Circuit Implementation
For n qubits, QFT uses Hadamard gates + controlled phase rotations:
Controlled phase gates: R_k = diag(1, e^(2πi/2^k)) adds phase based on qubit position. These phases encode the Fourier transform—quantum interference does the heavy lifting!
Why QFT Is Essential for Shor's
The period is hidden in the phase relationships of the superposition. Direct measurement would just give random x values. QFT rotates to the basis where period is observable as frequency peaks.
Multiple quantum paths interfere constructively at frequencies that are multiples of N/r, and destructively elsewhere. This selective amplification is impossible classically—it requires quantum phase coherence.
Without QFT, we'd need to measure the superposition many times and classically analyze the pattern—exponential time. QFT does it in one shot with O(n²) gates by processing the entire superposition coherently.
Measurement & Post-Processing
After QFT, measurement collapses to a peak value:
Success probability: Single measurement has ~40% chance of yielding correct r. Usually need 2-3 measurements. Still polynomial time overall!
The Heart of Quantum Advantage
QFT is where Shor's algorithm becomes truly quantum. Everything before (superposition, modular exponentiation) prepares a state with periodic structure. But QFT is what reads that structure out exponentially faster than any classical method. It exploits quantum interference at a massive scale—2^n paths interfering coherently to amplify the period signal. Classical computers must sample these paths sequentially (exponential time). Quantum computers process them in parallel through superposition, then use constructive/destructive interference via QFT to extract the answer (polynomial time). This is the essence of quantum computing: use interference to solve problems where classical approaches drown in exponentially large spaces. QFT isn't just faster—it's fundamentally different, accessing information encoded in quantum phases that have no classical analog.
🌊 Interactive: Quantum Fourier Transform
How QFT Works:
Time Domain (Before QFT)
4. Breaking RSA Encryption
🔐 Interactive: RSA Key Sizes
🏁 Interactive: The Factoring Race
🔬 Interactive: Quantum Resources Needed
5. Key Takeaways
Exponential Speedup
Shor's algorithm solves integer factorization in polynomial time O((log N)³), compared to exponential time for classical algorithms. This is one of the most dramatic quantum advantages known.
Quantum Fourier Transform
The QFT is the quantum analog of the classical Fast Fourier Transform, but exponentially faster. It's the key ingredient that enables Shor's algorithm to extract periods from quantum superpositions.
Threat to Cryptography
RSA, Diffie-Hellman, and elliptic curve cryptography will all be broken by Shor's algorithm. The race is on to deploy post-quantum cryptography before large-scale quantum computers arrive.
Still Years Away
Breaking RSA-2048 requires ~4 million error-corrected qubits. Today's quantum computers have ~1,000 noisy qubits. But progress is rapid - some estimate Q-Day could arrive by 2030-2035.
Post-Quantum Solutions
NIST has standardized post-quantum algorithms (lattice-based, hash-based, code-based) that are believed to be secure against quantum attacks. Migration is already beginning.
Beyond Factoring
Shor's algorithm also solves the discrete logarithm problem and can be adapted for other cryptographic systems. It showcases the true power of quantum computing for specific problems.