Shor's Algorithm

Peter Shor's 1994 quantum algorithm that factors integers and computes discrete logarithms in polynomial time, breaking RSA, ECC, and Diffie-Hellman.

Core Principles & Analysis

• The single result that made post-quantum cryptography necessary — every deployed public-key system falls to it.
• Requires a fault-tolerant quantum computer with millions of physical qubits; none yet exists.
• Reduces factoring to period-finding, which the quantum Fourier transform solves exponentially faster than any known classical method.

Specifications & Metrics

• TYPE: Quantum algorithm
• STATUS: Awaiting hardware
• YEAR: 1994