QuantumAlgorithms.aiA citable library

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.

DOIarXivRecord link

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

Updated 7 Oct 2026.