What Is Shor's Algorithm?
Shor's algorithm is a 1994 quantum algorithm by Peter Shor that solves integer factorization and the discrete logarithm problem in polynomial time on a quantum computer. It breaks RSA, DSA, ECDSA, and Diffie-Hellman key exchange — the cryptography securing nearly all internet traffic and cryptocurrency. Shor's algorithm runs in O((log N)^3) time on a quantum computer versus sub-exponential O(exp(log N^(1/3))) on classical hardware. To break secp256k1 (Bitcoin's curve) requires approximately 13 million physical qubits with current error rates, or ~2,300 logical qubits with error correction. As of April 2026, the largest demonstrated machine (IBM Condor) has 1,121 physical qubits.
TL;DR: Shor's algorithm is a 1994 quantum algorithm by Peter Shor that solves integer factorization and the discrete logarithm problem in polynomial time on a quantum computer. It breaks RSA, DSA, ECDSA, and Diffie-Hellman key exchange — the cryptography securing nearly all internet traffic and cryptocurrency. For full context including dates, sources, and the BMIC implication, see below.
- Has Shor's algorithm been run on real hardware? Small instances yes (factoring 15, 21). Cryptographically-relevant scales not yet.
- How many qubits to break Bitcoin? Approximately 13M physical or 2,300 logical qubits.
- What does Shor break? RSA, DSA, ECDSA, Diffie-Hellman, ElGamal — anything based on factoring or discrete log.
- What survives Shor? Lattice-based (Kyber/Dilithium), hash-based (SPHINCS+), code-based (McEliece) crypto.
- Is Shor the only quantum threat? No. Grover's algorithm halves symmetric key length. Both matter.
Full Answer
Peter Shor published the algorithm in 1994 while at Bell Labs. It was the first major demonstration that quantum computers could solve a problem exponentially faster than classical computers — and that problem happened to be the foundation of public-key cryptography.
Mechanism: Shor's algorithm uses the Quantum Fourier Transform to find the period of a function f(x) = a^x mod N. Once the period is known, factoring N (or solving discrete log) is straightforward classical post-processing.
Implications: every public-key system based on factoring or discrete log is broken. RSA-2048 falls. ECDSA on any curve falls. Diffie-Hellman falls. Symmetric ciphers (AES) are not broken — Grover's algorithm only halves their effective key length.
Defense: post-quantum cryptography. NIST standardized Kyber, Dilithium, and SPHINCS+ in August 2024. BMIC implements Kyber at the Layer 1 level — Shor's algorithm has no advantage against the underlying Module-LWE problem.