TL;DR: Shor's algorithm (1994) can factor large integers exponentially faster than any known classical algorithm. This threatens RSA-2048 and ECC, the backbone of internet security. Requires ~4,000 logical q
Shor's algorithm (1994) can factor large integers exponentially faster than any known classical algorithm. This threatens RSA-2048 and ECC, the backbone of internet security. Requires ~4,000 logical qubits (millions of physical qubits with error correction). NIST has standardized post-quantum cryptography (CRYSTALS-Kyber, CRYSTALS-Dilithium) in response.
Type
Number theory / Cryptography
Complexity
O((log N)³) vs classical O(exp((log N)^(1/3)))
Application
Integer factorization - breaks RSA, ECC encryption