🔢 Shor's Factoring Algorithm
Exponential quantum speedup that threatens modern cryptography
Your Progress
0 / 5 completed💥 The Cryptography Breaker
In 1994, Peter Shor discovered a quantum algorithm that shook the cryptography world. While classical computers need exponential time to factor large numbers, Shor's algorithm does it in polynomial time. This threatens RSA encryption, which protects most of today's internet communications.
🚨 The RSA Problem
RSA encryption relies on one key fact: factoring large numbers is hard. It's easy to multiply two primes (e.g., 61 × 53 = 3,233), but extremely hard to factor the result back. A 2048-bit RSA key would take classical computers billions of years to crack. Shor's algorithm could do it in hours.
🌟 Why It's Revolutionary
- •Exponential Speedup: First practical quantum algorithm with exponential advantage over classical
- •Cryptographic Impact: Breaks RSA, Diffie-Hellman, and elliptic curve cryptography
- •Quantum Fourier Transform: Introduces QFT, now used in many quantum algorithms
- •Post-Quantum Era: Drove development of quantum-resistant encryption standards
🔑 Key Components
Period Finding
Find the period of modular exponentiation using quantum parallelism
Quantum Fourier Transform
Extract period from superposition through phase estimation
Classical Reduction
Convert period-finding to factoring using number theory
Polynomial Time
Runs in O((log N)³) time versus exponential classical time