The DOI matches its Crossref record; 118 of the 118 references it cites were found in a registry or an index.
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
Abstract
A digital computer is generally believed to be an efficient universal computing device; that is, it is believed to be able to simulate any physical computing device with an increase in computation time by at most a polynomial factor. This may not be true when quantum mechanics is taken into consideration. This paper considers factoring integers and finding discrete logarithms, two problems that are generally thought to be hard on classical computers and that have been used as the basis of several proposed cryptosystems. Efficient randomized algorithms are given for these two problems on a hypothetical quantum computer. These algorithms take a number of steps polynomial in the input size, for example, the number of digits of the integer to be factored.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Further, in the presently employed cryptography algorithms, this algorithm [52] has potential use in performing cryptanalysis where public-key cryptography could be broken.”
From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [52]
In the citing paper
“Researchers developed the algorithm to determine the prime factors of an integer N and executed it in polynomial time.”
From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [52]
In the citing paper
“challenged this theory and demonstrated a quantum algorithm with polynomial time.”
From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [52]
In the citing paper
“we know of problems that are believed to be hard for classical computers, but for which quantum algorithms have been discovered that could solve these problems easily.”
From Quantum Computing in the NISQ era and beyond (2018) · cites this paper as [1]
In the citing paper
“In practice, attackers can harvest encrypted traffic today and defer decryption until future computational breakthroughs render current schemes obsolete [1,2].”
From Harvest-Now, Decrypt-Later: A Temporal Cybersecurity Risk in the Quantum Transition (2025) · cites this paper as [2]
4 more claims about this paper
Create a free account to see every claim other papers make about this one.
Citations
Cites
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,337
Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels
Bennett, C. H., Brassard, G., Crépeau, C., Jozsa, R., Peres, A., & Wootters, W. K. (1993) · Physical Review Letters · doi:10.1103/physrevlett.70.1895 · Cited by 13,703
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1983) · Communications of the ACM · doi:10.1145/357980.358017 · Cited by 13,012
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
Self-citationQuantum cryptography: Public key distribution and coin tossing
Bennett, C. H., & Brassard, G. (2020) · arXiv · doi:10.48550/arxiv.2003.06557 · Cited by 8,299
Quantum cryptography: Public key distribution and coin tossing
Bennett, C. H., & Brassard, G. (2014) · Theoretical Computer Science · doi:10.1016/j.tcs.2014.05.025 · Cited by 8,299
On computable numbers, with an application to the entscheidungsproblem
Turing, A. M. (1937) · Proceedings of the London Mathematical Society · doi:10.1112/plms/s2-42.1.230 · Cited by 8,283
Simulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691
Fault-tolerant quantum computation by anyons
Kitaev, A. Y. (2003) · Annals of Physics · doi:10.1016/s0003-4916(02)00018-0 · Cited by 7,238
Research works printed but not linked: 10
- Brassard G., 1993, SIGACT News, 24, 16
- R. Cleve (1994), A note on computing Fourier transforms by quantum programs , preprint.
- originally published in Optics News (February 1985), pp. 11–20.
- Karatsuba A., 1962, Dokl. Akad. Nauk SSSR, 145, 293
- 1963, Sov. Phys. Dokl., 7, 595
- R. Landauer (1997), Is quantum mechanically coherent computation useful? , in Proc. Drexel‐4 Symposium on Quantum Nonintegrability—Quantum Classical Correspondence, D. H. Feng and B‐L. Hu, eds., International Press, Cambridge, MA, to appear.
- Lecerf Y., 1963, C. R. Acad. Française Sci., 257, 2597
- N. Margolus (1990), Parallel quantum computation , in Complexity, Entropy and the Physics of Information, Santa Fe Institute Studies in the Sciences of Complexity, Vol. VIII, W. H. Zurek, ed., Addison‐Wesley, Reading, MA, pp. 273–287.
- P. W. Shor (1998) Quantum computing Documenta Mathematica, Extra Volume Proceedings ICM, Vol. I, pp. 305–324.
- 10.1112/plms/s2-43.6.544 · DOI · Paper page
Cited by
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 2,231
Advances in quantum cryptography
Pirandola, S., Andersen, U. L., Banchi, L., Berta, M., Bunandar, D., Colbeck, R., Englund, D., Gehring, T., Lupo, C., Ottaviani, C., et al. (2020) · Advances in Optics and Photonics · doi:10.1364/aop.361502 · Cited by 2,033
Quantum random walks: An introductory overview
Kempe, J. (2003) · Contemporary Physics · doi:10.1080/00107151031000110776 · Cited by 1,413
Suppressing quantum errors by scaling a surface code logical qubit
Google Quantum, A. I., Acharya, R., Aleiner, I., Allen, R., Andersen, T. I., Ansmann, M., Arute, F., Arya, K., Asfaw, A., Atalaya, J., et al. (2023) · Nature · doi:10.1038/s41586-022-05434-1 · Cited by 1,103
Metadata
- Authors
- Shor, P. W.
- Corresponding author
- Shor, Peter W.
- ORCID
- Shor, Peter W.
- Venue
- SIAM Review
- Published
- 1999-01
- Volume
- 41
- Issue
- 2
- Pages
- 303-332
- ISSN
- 0036-1445 (ISSN-L)
- 1095-7200
- OpenAlex
- W2137147061
- Cited by
- 3,904
- References
- 115
- Citations by year
- 2026: 326 · 2025: 550 · 2024: 481 · 2023: 463 · 2022: 405 · 2021: 355 · 2020: 271 · 2019: 195 · 2018: 151 · 2017: 124 · 2016: 70 · 2015: 47 · 2014: 40 · 2013: 56 · 2012: 44
- FWCI
- 21.03
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Review (publishedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Keywords
- quantum computing, integer factorization, discrete logarithm problem, polynomial-time algorithms, randomized algorithms, ciphers, computational complexity, quantum algorithms
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. https://app.cochat.ai/papers/10.1137/s0036144598347011
- The paper
- Shor, P. W. (1999). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Review. https://doi.org/10.1137/s0036144598347011
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.