The DOI matches its Crossref record; 63 of the 63 references it cites were found in a registry or an index.
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
Open accessAbstract
A digital computer is generally believed to be an efficient universal computing device; that is, it is believed 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 which are generally thought to be hard on a classical computer and which 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, e.g., 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
“The emergence of large-scale quantum computing presents an imminent threat to contemporary public-key cryptosystems, with quantum algorithms such as Shor's algorithm capable of efficiently breaking RSA and elliptic curve cryptography (ECC).”
From A Practical Performance Benchmark of Post-Quantum Cryptography Across Heterogeneous Computing Environments (2025) · cites this paper as [1]
In the citing paper
“Shor ' s algorithm solves the case G= ℤ .”
From Quantum algorithms: an overview (2016) · cites this paper as [11]
In the citing paper
“Shor’s algorithm19 could be used to break public-key cryptography protocols.”
From Quantum-resistance in blockchain networks (2023) · cites this paper as [19]
In the citing paper
“The advent of quantum computing threatens blockchain protocols and networks because they utilize non-quantum resistant cryptographic algorithms.”
From Quantum-resistance in blockchain networks (2023) · cites this paper as [19]
In the citing paper
“When quantum computers become robust enough to run Shor’s algorithm on a large scale, the most used asymmetric algorithms, utilized for digital signatures and message encryption, such as RSA, (EC)DSA, and (EC)DH, will be no longer secure.”
From Quantum-resistance in blockchain networks (2023) · cites this paper as [19]
4 more claims about this paper
Create a free account to see every claim other papers make about this one.
Citations
Cites
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
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-citationSimulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691
Quantum theory, the Church–Turing principle and the universal quantum computer
Deutsch, D. (1985) · Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · doi:10.1098/rspa.1985.0070 · Cited by 4,597
Scheme for reducing decoherence in quantum computer memory
Shor, P. W. (1995) · Physical Review A · doi:10.1103/physreva.52.r2493 · Cited by 4,479
Self-citationElementary gates for quantum computation
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., & Weinfurter, H. (1995) · Physical Review A · doi:10.1103/physreva.52.3457 · Cited by 4,311
Self-citationQuantum Computations with Cold Trapped Ions
Cirac, J. I., & Zoller, P. (1995) · Physical Review Letters · doi:10.1103/physrevlett.74.4091 · Cited by 3,733
Logical Reversibility of Computation
Bennett, C. H. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.176.0525 · Cited by 3,679
Purification of Noisy Entanglement and Faithful Teleportation via Noisy Channels
Bennett, C. H., Brassard, G., Popescu, S., Schumacher, B., Smolin, J. A., & Wootters, W. K. (1996) · Physical Review Letters · doi:10.1103/physrevlett.76.722 · Cited by 2,961
Rapid solution of problems by quantum computation
Deutsch, D., & Jozsa, R. (1992) · Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences · doi:10.1098/rspa.1992.0167 · Cited by 2,700
Research works printed but not linked: 11
- R. Cleve (1994), A note on computing Fourier transforms by quantum programs , preprint.
- Niven Ivan, 1991, An introduction to the theory of numbers
- Karatsuba A., 1962, Dokl. Akad. Nauk SSSR, 145, 293
- 1963, Sov. Phys. Dokl., 7, 595
- D. E. Knuth (1981), The Art of Computer Programming, Vol. 2: Seminumerical Algorithms , 2nd ed., Addison‐Wesley, Reading, MA.
- Rolf Landauer, Is quantum mechanically coherent computation useful? Internat. Press, Cambridge, MA, 1997, 37–551610259
- Lecerf Yves, 1963, C. R. Acad. Sci. Paris, 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.
- Simon (1994) D., 1997, SIAM J. Comput., 26, 1340
- 10.1112/plms/s2-43.6.544 · DOI · Paper page
- Andrew Yao, Quantum circuit complexity, IEEE Comput. Soc. Press, Los Alamitos, CA, 1993, 352–3611328432
Cited by
A scheme for efficient quantum computation with linear optics
Knill, E., Laflamme, R., & Milburn, G. J. (2001) · Nature · doi:10.1038/35051009 · Cited by 5,880
Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., & Lloyd, S. (2017) · Nature · doi:10.1038/nature23474 · Cited by 4,779
The security of practical quantum key distribution
Scarani, V., Bechmann-Pasquinucci, H., Cerf, N. J., Dušek, M., Lütkenhaus, N., & Peev, M. (2009) · Reviews of Modern Physics · doi:10.1103/revmodphys.81.1301 · Cited by 3,726
Weedbrook, C., Pirandola, S., García-Patrón, R., Cerf, N. J., Ralph, T. C., Shapiro, J. H., & Lloyd, S. (2012) · Reviews of Modern Physics · doi:10.1103/revmodphys.84.621 · Cited by 3,664
Charge-insensitive qubit design derived from the Cooper pair box
Koch, J., Yu, T. M., Gambetta, J., Houck, A. A., Schuster, D. I., Majer, J., Blais, A., Devoret, M. H., Girvin, S. M., & Schoelkopf, R. J. (2007) · Physical Review A · doi:10.1103/physreva.76.042319 · Cited by 3,351
Metadata
- Authors
- Shor, P. W.
- Corresponding author
- Shor, Peter W.
- ORCID
- Shor, Peter W.
- Venue
- SIAM Journal on Computing
- Published
- 1997-10
- Volume
- 26
- Issue
- 5
- Pages
- 1484-1509
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W3023478445
- Cited by
- 8,472
- References
- 45
- Citations by year
- 2026: 483 · 2025: 594 · 2024: 555 · 2023: 474 · 2022: 478 · 2021: 490 · 2020: 520 · 2019: 469 · 2018: 339 · 2017: 367 · 2016: 321 · 2015: 341 · 2014: 315 · 2013: 273 · 2012: 227
- FWCI
- 105.98
- Type
- journal article
- Language
- en
- Open access
- green
- doi.org
- Locations
- SIAM Journal on Computing (publishedVersion)
- arXiv (Cornell University)
- 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/s0097539795293172
- The paper
- Shor, P. W. (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing. https://doi.org/10.1137/s0097539795293172
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.