Abstract
A computer is generally considered to be a universal computational device; i.e., it is believed able to simulate any physical computational device with a cost in computation time of at most a polynomial factor: It is not clear whether this is still true when quantum mechanics is taken into consideration. Several researchers, starting with David Deutsch, have developed models for quantum mechanical computers and have investigated their computational properties. This paper gives Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer that take a number of steps which is polynomial in the input size, e.g., the number of digits of the integer to be factored. These two problems are generally considered hard on a classical computer and have been used as the basis of several proposed cryptosystems. We thus give the first examples of quantum cryptanalysis.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Keywords
Discrete logarithmQuantum computerPost-quantum cryptographyComputer scienceCryptosystemComputationCryptanalysisLogarithmPolynomialFactoringLas vegasComputational problemTheoretical computer scienceDiscrete mathematicsQuantum algorithmQuantumAlgorithmCryptographyMathematicsEncryptionPublic-key cryptographyQuantum mechanics
Affiliated Institutions
Related Publications
On the power of quantum computation
The quantum model of computation is a probabilistic model, similar to the probabilistic Turing Machine, in which the laws of chance are those obeyed by particles on a quantum me...
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
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 incr...
Reducing elliptic curve logarithms to logarithms in a finite field
Elliptic curve cryptosystems have the potential to provide relatively small block size, high-security public key schemes that can be efficiently implemented. As with other known...
A subexponential-time algorithm for computing discrete logarithms overGF(p^2)
An algorithm for computing discrete logarithms over GF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(p^{2})</tex> , where <tex ...
An improved algorithm for computing logarithms overGF(p)and its cryptographic significance (Corresp.)
A cryptographic system is described which is secure if and only if computing logarithms over <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1...
Publication Info
- Year
- 2002
- Type
- article
- Pages
- 124-134
- Citations
- 7902
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
7902
OpenAlex
Cite This
Peter W. Shor
(2002).
Algorithms for quantum computation: discrete logarithms and factoring.
, 124-134.
https://doi.org/10.1109/sfcs.1994.365700
Identifiers
- DOI
- 10.1109/sfcs.1994.365700