Shor’s algorithm is the quantum algorithm proposed by Peter Shor in 1994 for rapidly factoring large integers.
The algorithm uses quantum computation to find the period of a modular arithmetic function. A quantum Fourier transform extracts information about that period, after which classical number theory can recover factors of the original integer. Its running time is polynomial in the number of digits, giving an exponential speed advantage over the best known general-purpose classical factoring methods.
This matters because widely used public-key systems, especially RSA, rely on the practical difficulty of factoring large numbers. A sufficiently powerful fault-tolerant quantum computer running Shor’s algorithm could threaten those systems. That possibility is one reason researchers are developing post-quantum cryptography.
Shor’s algorithm is often confused with Grover’s algorithm. Grover’s algorithm provides a quadratic speedup for unstructured search, whereas Shor’s algorithm addresses factoring and related number-theory problems. Shor’s proposal was theoretical; implementing it at cryptographically relevant scale remains a major engineering challenge.