Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

Peter W. Shor

SIAM Journal on Computing 1997

Time bound

poly(log N) quantum and classical work

Space bound

Not extracted from the source

Source / version date

30 Aug 1995

Comparison variant

Quantum · polynomial-time expressions

Cost scale

Expression only

historicalPredecessor

FOCS 1994, pp. 124–134; different paper title.

Assumptions and source notes

Unconditional polynomial-time quantum factorization. The cited full-paper preprint dates from 1995; the preliminary FOCS paper Algorithms for quantum computation: Discrete logarithms and factoring appeared in November 1994. No exponential coefficient is assigned.

Source location

Abstract; introduction
Version: Version available at the cited URL; bibliographic metadata and stated bound checked on 2026-11-08

Primary source ↗

@misc{shor95,
  author = {Peter W. Shor},
  title = {{Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer}},
  journal = {SIAM Journal on Computing 26(5), 1484–1509},
  year = {1997},
  doi = {10.1137/S0097539795293172},
  url = {https://arxiv.org/abs/quant-ph/9508027},
  keywords = {quantum, factoring, discrete logarithms},
  cr_date = {1995-08-30},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {SIAM Journal on Computing 26(5), 1484–1509},
  cr_author_ids = {peter-w-shor}
}