Generic DLP / Quantum · abelian groups

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

Peter W. Shor

SIAM Journal on Computing 1997

PublishedSource checked

Time bound: poly(log r) quantum work with efficient coherent group arithmetic
Space bound: Not extracted from the source

Source / version date: 30 Aug 1995
Comparison variant: Quantum · abelian groups
Cost scale: Expression only

Assumptions and source notes

Quantum discrete logarithm algorithm. The efficient coherent group-operation model is essential; no claim about classical generic algorithms follows.

Source location

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

Primary source ↗

BibTeXDownload .bib

@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}
}