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.
Keywords
Quantum computerInteger factorizationDiscrete logarithmPrime factorLogarithmQuantum algorithmPolynomialInteger (computer science)Time complexityPost-quantum cryptographyCryptosystemAlgorithmComputationFactorizationComputer sciencePrime (order theory)MathematicsDiscrete mathematicsAlgebra over a fieldQuantumCryptographyCombinatoricsPure mathematics
Related Publications
Algorithms for quantum computation: discrete logarithms and factoring
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 tim...
Efficient networks for quantum factoring
We consider how to optimize memory use and computation time in operating a quantum computer. In particular, we estimate the number of memory quantum bits (qubits) and the number...
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...
On the Power of Quantum Computation
The quantum model of computation is a model, analogous to the probabilistic Turing machine (PTM), in which the normal laws of chance are replaced by those obeyed by particles on...
Quantum Computation
If the bits of computers are someday scaled down to the size of individual atoms, quantum mechanical effects may profoundly change the nature of computation itself. The wave fun...
Publication Info
- Year
- 1999
- Type
- article
- Volume
- 41
- Issue
- 2
- Pages
- 303-332
- Citations
- 3541
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
3541
OpenAlex
Cite This
Peter W. Shor
(1999).
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.
SIAM Review
, 41
(2)
, 303-332.
https://doi.org/10.1137/s0036144598347011
Identifiers
- DOI
- 10.1137/s0036144598347011