RSA factoring / Balanced semiprimes · quantum

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 N) quantum and classical work
Space bound: Not extracted from the source

Source / version date: 30 Aug 1995
Comparison variant: Balanced semiprimes · quantum
Cost scale: Expression only

Assumptions and source notes

Polynomial-time quantum factorization applies to RSA-type semiprimes. No physical qubit or wall-clock estimate follows from this asymptotic record.

Source location

Abstract; introduction
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}
}