← All research spotlights

Research spotlight · Unit 15

Peter Shor

Massachusetts Institute of Technology

Research field
Quantum algorithms, quantum error correction, quantum information theory

Peter Shor found in 1994, while working at Bell Labs, that a quantum computer could factor whole numbers and compute discrete logarithms in a time that grows only as a power of the number of digits, where the best classical methods grow much faster. The result turned quantum computing from a curiosity into a field, because the security of internet encryption rests on the difficulty of exactly these problems. A year later he showed that quantum information can be protected by error-correcting codes. The unit follows the journal version of his algorithm from 1997: the reduction of factoring to finding a period, the quantum Fourier transform that finds it, and the number 15 as the worked case.

In the masterclass

Section 5, after the worked examples that factor 15 and 21 with the order-finding method his paper introduced.

The research is presented in Unit 15: Quantum Algorithms, in a research spotlight box that explains the result at the level of the unit and links it to what you have just learned.

The paper

Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484‑1509. https://doi.org/10.1137/S0097539795293172

The scientists named here are not contributors to the QM Masterclass, are not affiliated with it, and have not endorsed it. The program presents and explains their published research, with references to the original papers.