Peter Shor invented the quantum algorithm that can factor large numbers exponentially faster than the best known classical factoring methods. He developed the factoring algorithm in 1994 while working at Bell Labs, and it became known as Shor’s algorithm.
The algorithm turns factoring into a quantum period-finding problem. A quantum computer creates a superposition of many possible inputs, evaluates modular arithmetic across those possibilities, and uses the quantum Fourier transform to extract a hidden period. Classical number-theory techniques then convert that period into factors of the original integer.
This result matters because the security of widely used public-key systems such as RSA depends on the practical difficulty of factoring very large numbers on conventional computers. A sufficiently large, fault-tolerant quantum computer running Shor’s algorithm could undermine that assumption, motivating the development of post-quantum cryptography.
Shor’s algorithm is often described as exponentially faster, though real hardware has not yet factored cryptographically relevant numbers. The first experimental demonstration, by an IBM-led team in 2001, factored 15 into 3 × 5 using a seven-qubit nuclear-magnetic-resonance system.