Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Polynomial time algorithms for discrete logarithms and factoring on a quantum computer

Peter W. Shor

Published Jan 1, 1994• 136 citations
Publisher
DOI
10.1007/3-540-58691-1_68

Related papers

Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers

Martin Ekerå, Johan Håstad

arXiv:1702.00249•Lecture notes in computer science•Jan 1, 2017•74 citations

Extending Regev’s Factoring Algorithm to Compute Discrete Logarithms

Martin Ekerå, Joel Gärtner

arXiv:2311.05545•Lecture notes in computer science•Jan 1, 2024•21 citations

Algorithms for quantum computation: Discrete log and factoring

Peter W. Shor

•Jan 1, 1994•269 citations

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

Peter W. Shor

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.

arXiv:quant-ph/9508027•SIAM Journal on Computing•Oct 1, 1997•9,397 citations

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

Peter W. Shor

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.

SIAM Review•Jan 1, 1999•4,120 citations

Quantum Computational Number Theory

Song Yuan Yan

This chapter gives an account of ef?cient algorithms for solving the three important infeasible problems in computational number theory, including the Integer Factorization Problem (IFP), the Discrete Logarithm Problems (DLP), and the Elliptic Curve Discrete Logarithm Problem (ECDLP). The quantum algorithms for order ?nding and factoring can be used, with some small modi?cations, to solve the Discrete Logarithm Problem (DLP) ef?ciently in polynomial time. Quantum factoring is reportedly in its very earliest stages and will not threaten the security of RSA at least at present, as the current quantum computer can only factor a number with just 2 digits, such as 15, which is essentially hopeless. The Elliptic Curve Method (ECM) factoring algorithm is very well suited to parallel implementation. The Number Field Sieve (NFS) factoring algorithm is also very well suited to parallel implementation.

Wiley eBooks•Nov 27, 2012•5 citations
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.
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.
This chapter gives an account of ef?cient algorithms for solving the three important infeasible problems in computational number theory, including the Integer Factorization Problem (IFP), the Discrete Logarithm Problems (DLP), and the Elliptic Curve Discrete Logarithm Problem (ECDLP). The quantum algorithms for order ?nding and factoring can be used, with some small modi?cations, to solve the Discrete Logarithm Problem (DLP) ef?ciently in polynomial time. Quantum factoring is reportedly in its very earliest stages and will not threaten the security of RSA at least at present, as the current quantum computer can only factor a number with just 2 digits, such as 15, which is essentially hopeless. The Elliptic Curve Method (ECM) factoring algorithm is very well suited to parallel implementation. The Number Field Sieve (NFS) factoring algorithm is also very well suited to parallel implementation.