Shor's Algorithm

Shor's algorithm, developed by Peter Shor in 1994, can factor an integer N in polynomial time O((log N)³) using quantum computers. The best known classical algorithm (general number field sieve) runs in sub-exponential time. This is significant because RSA encryption relies on the difficulty of factoring large numbers. Shor's algorithm uses the Quantum Fourier Transform to find the period of a modular exponential function. While the algorithm is theoretically powerful, running it on real hardware to break RSA-2048 would require millions of error-corrected qubits — far beyond current NISQ capabilities (which have at most ~1000 noisy qubits). Shor's algorithm is the primary motivation for post-quantum cryptography research and NIST's post-quantum cryptography standardization effort.