Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
Open accessThe DOI matches its Crossref record; 64 of the 64 references it cites were found in a registry or an index.
Abstract
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
An index to quantify an individual’s scientific research output
Hirsch, J. E. (2005) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0507655102 · Cited by 11,669
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
Fredkin, E., & Toffoli, T. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf01857727 · Cited by 1,896
Feynman, R. P. (1986) · Foundations of Physics · doi:10.1007/bf01886518 · Cited by 1,770
An Unsolvable Problem of Elementary Number Theory
Church, A. (1936) · American Journal of Mathematics · doi:10.2307/2371045 · Cited by 1,763
Toffoli, T. (1980) · Lecture Notes in Computer Science · doi:10.1007/3-540-10003-2_104 · Cited by 1,523
Bernstein, E., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300921 · Cited by 1,503
Strengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300933 · Cited by 1,470
Quantum computation and Shor's factoring algorithm
Ekert, A., & Jozsa, R. (1996) · Reviews of Modern Physics · doi:10.1103/revmodphys.68.733 · Cited by 1,354
Quantum computational networks
Deutsch, D. E. (1989) · Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · doi:10.1098/rspa.1989.0099 · Cited by 1,270
Benioff, P. (1980) · Journal of Statistical Physics · doi:10.1007/bf01011339 · Cited by 1,244
Schnelle Multiplikation großer Zahlen
Schönhage, A., & Strassen, V. (1971) · Computing · doi:10.1007/bf02242355 · Cited by 1,107
Two-bit gates are universal for quantum computation
DiVincenzo, D. P. (1995) · Physical Review A · doi:10.1103/physreva.51.1015 · Cited by 1,069
Conditional Quantum Dynamics and Logic Gates
Barenco, A., Deutsch, D., Ekert, A., & Jozsa, R. (1995) · Physical Review Letters · doi:10.1103/physrevlett.74.4083 · Cited by 971
Quantum computers and dissipation
(1996) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1996.0029 · Cited by 899
Riemann's hypothesis and tests for primality
Miller, G. L. (1976) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(76)80043-8 · Cited by 856
Almost Any Quantum Logic Gate is Universal
Lloyd, S. (1995) · Physical Review Letters · doi:10.1103/physrevlett.75.346 · Cited by 690
A Potentially Realizable Quantum Computer
Lloyd, S. (1993) · Science · doi:10.1126/science.261.5128.1569 · Cited by 649
Quantum lower bounds by polynomials
Beals, R., Buhrman, H., Cleve, R., Mosca, M., & de Wolf, R. (2001) · Journal of the ACM · doi:10.1145/502090.502097 · Cited by 639
On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction
Turing, A. M. (1938) · Proceedings of the London Mathematical Society · doi:10.1112/plms/s2-43.6.544 · Cited by 600
Maintaining coherence in quantum computers
Unruh, W. G. (1995) · Physical Review A · doi:10.1103/physreva.51.992 · Cited by 594
The development of the number field sieve
(1993) · Lecture Notes in Mathematics · doi:10.1007/bfb0091534 · Cited by 574
New lower bound techniques for robot motion planning problems
Canny, J., & Reif, J. (1987) · 28th Annual Symposium on Foundations of Computer Science (sfcs 1987) · doi:10.1109/sfcs.1987.42 · Cited by 538
Finite combinatory processes—formulation
Post, E. L. (1936) · Journal of Symbolic Logic · doi:10.2307/2269031 · Cited by 516
Realizable Universal Quantum Logic Gates
Sleator, T., & Weinfurter, H. (1995) · Physical Review Letters · doi:10.1103/physrevlett.74.4087 · Cited by 515
Chuang, I. L., & Yamamoto, Y. (1995) · Physical Review A · doi:10.1103/physreva.52.3489 · Cited by 434
Semiclassical Fourier Transform for Quantum Computation
Griffiths, R. B., & Niu, C.-S. (1996) · Physical Review Letters · doi:10.1103/physrevlett.76.3228 · Cited by 431
Time/Space Trade-Offs for Reversible Computation
Bennett, C. H. (1989) · SIAM Journal on Computing · doi:10.1137/0218053 · Cited by 405
Quantum mechanical Hamiltonian models of Turing machines
Benioff, P. (1982) · Journal of Statistical Physics · doi:10.1007/bf01342185 · Cited by 402
Universality in quantum computation
Deutsch, D. E., Barenco, A., & Ekert, A. (1995) · Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences · doi:10.1098/rspa.1995.0065 · Cited by 346
Discrete Logarithms in $GF ( P )$ Using the Number Field Sieve
Gordon, D. M. (1993) · SIAM Journal on Discrete Mathematics · doi:10.1137/0406010 · Cited by 322
Quantum Mechanical Models of Turing Machines That Dissipate No Energy
Benioff, P. (1982) · Physical Review Letters · doi:10.1103/physrevlett.48.1581 · Cited by 295
Quantum Computers, Factoring, and Decoherence
Chuang, I. L., Laflamme, R., Shor, P. W., & Zurek, W. H. (1995) · Science · doi:10.1126/science.270.5242.1633 · Cited by 289
Self-citationLenstra, A. K., Lenstra, H. W., Manasse, M. S., & Pollard, J. M. (1990) · Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 · doi:10.1145/100216.100295 · Cited by 285
Efficient networks for quantum factoring
Beckman, D., Chari, A. N., Devabhaktuni, S., & Preskill, J. (1996) · Physical Review A · doi:10.1103/physreva.54.1034 · Cited by 268
Machine Models and Simulations
van EMDE BOAS, P. (1990) · Algorithms and Complexity · doi:10.1016/b978-0-444-88071-0.50006-0 · Cited by 248
The complexity of analog computation
Vergis, A., Steiglitz, K., & Dickinson, B. (1986) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(86)90105-9 · Cited by 183
Quantum Cryptanalysis of Hidden Linear Functions
Boneh, D., & Lipton, R. J. (1995) · Lecture Notes in Computer Science · doi:10.1007/3-540-44750-4_34 · Cited by 161
On the power of multiplication in random access machines
Hartmanis, J., & Šimon, J. (1974) · Annual Symposium on Switching & Automata Theory · doi:10.1109/swat.1974.20 · Cited by 126
Landauer, R. (1995) · Philosophical Transactions of the Royal Society of London. Series A: Physical and Engineering Sciences · doi:10.1098/rsta.1995.0106 · Cited by 124
Berthiaume, A., & Brassard, G. (1994) · Journal of Modern Optics · doi:10.1080/09500349414552351 · Cited by 99
Fast, Rigorous Factorization and Discrete Logarithm Algorithms
Pomerance, C. B. (1987) · Elsevier eBooks · doi:10.1016/b978-0-12-386870-1.50014-9 · Cited by 97
Schönhage, A. (1982) · Lecture notes in computer science · doi:10.1007/3-540-11607-9_1 · Cited by 93
Open problems in number theoretic complexity, II
Adleman, L. M., & McCurley, K. S. (1994) · Lecture notes in computer science · doi:10.1007/3-540-58691-1_70 · Cited by 89
Digital simulation of analog computation and Church's thesis
Rubel, L. A. (1989) · Journal of Symbolic Logic · doi:10.2307/2274761 · Cited by 79
Approximate Euclidean shortest path in 3-space
Choi, J., Sellen, J., & Yap, C.-K. (1994) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/177424.177501 · Cited by 77
The quantum challenge to structural complexity theory
Berthiaume, A., & Brassard, G. (2003) · [1992] Proceedings of the Seventh Annual Structure in Complexity Theory Conference · doi:10.1109/sct.1992.215388 · Cited by 73
A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
Levine, R. Y., & Sherman, A. T. (1990) · SIAM Journal on Computing · doi:10.1137/0219046 · Cited by 71
Structural basis of multistationary quantum systems. II. Effective few-particle dynamics
Teich, W. G., Obermayer, K., & Mahler, G. (1988) · Physical Review B · doi:10.1103/physrevb.37.8111 · Cited by 64
Envisioning a Quantum Supercomputer
Lloyd, S. (1994) · Science · doi:10.1126/science.263.5147.695 · Cited by 60
MARGOLUS, N. (1986) · Annals of the New York Academy of Sciences · doi:10.1111/j.1749-6632.1986.tb12451.x · Cited by 38
The stabilisation of quantum computations
Berthiaume, A., Deutsch, D., & Jozsa, R. (2002) · Workshop on Physics and Computation (PhysComp) · doi:10.1109/phycmp.1994.363698 · Cited by 35
Algorithmic number theory-the complexity contribution
Adleman, L. M. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365702 · Cited by 22
Can quantum computers have simple Hamiltonians?
Biafore, M. (2002) · Workshop on Physics and Computation (PhysComp) · doi:10.1109/phycmp.1994.363697 · Cited by 14
Two Non-Standard Paradigms for Computation: Analog Machines and Cellular Automata
Steiglitz, K. (1988) · Springer eBooks · doi:10.1007/978-94-009-2794-0_11 · Cited by 3
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
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.