Reference · 1997
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
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.
- Authors
- Peter W. Shor
- Venue
- SIAM Journal on Computing 26(5), 1484–1509
The source for the factoring bound quoted on Shor's algorithm: asymptotically O((log n)^2 (log log n) (log log log n)) steps on a quantum computer, plus classical post-processing polynomial in log n, where n is the integer. Also the source for the gate-array model, the discrete-logarithm algorithm in the multiplicative group modulo a prime, and the discussion of precision and decoherence.
Cited by
- A noise threshold for Shor's Fourier transformdigest
- Cryptographytopic
- Quantum algorithms tabletable
- Quantum Fourier transformglossary
- Quantum gateglossary
- Quantum phase estimationalgorithm
- Shor's algorithmalgorithm
- What the source papers claimdigest
Updated 7 Oct 2026.