A quantum computer does not factor integers by searching for divisors. Factoring is first reduced, by a randomized classical argument, to finding the multiplicative order of a random element modulo the target, and order finding is a period-finding problem, which is exactly what a Fourier transform answers. The quantum machine prepares a uniform superposition, computes modular exponentiation reversibly into a second register, and transforms the first, so that amplitudes interfere constructively only near multiples of the reciprocal period; a continued-fraction expansion of the measured value recovers the period classically. The lesson generalises beyond the algorithm: the speedup comes from choosing a reduction that turns the problem into one whose structure a superposition can expose all at once, and it delivers polynomial time where the number field sieve is exponential in the input length.
Peter W. Shor (AT&T Research, Murray Hill), arXiv quant-ph/9508027v2, quant-ph, 28 pages, expanded and minor-revised in January 1996 from the version presented at the 35th Annual Symposium on Foundat…