Shor's algorithm gives a quantum computer a speedup for solving integer factorization.
Peter Shor introduced the algorithm in 1994. It factors a composite integer by reducing the task to finding the period of a modular arithmetic function. A quantum computer uses a quantum Fourier transform to extract information about that period, after which classical number theory can usually recover a nontrivial factor.
For integers of large size, the best known general-purpose classical factoring methods are believed to require sub-exponential time, while Shor’s algorithm runs in polynomial time under its standard complexity analysis. This distinction is why large fault-tolerant quantum computers could threaten widely used public-key systems such as RSA.
Shor’s algorithm is not the same as the quantum Fourier transform: the transform is an important subroutine, whereas Shor’s algorithm is the complete factoring procedure. It also does not instantly factor every number; practical performance depends on error correction, circuit size, and the number of reliable logical qubits available.