Shor’s factoring algorithm and modern cryptography. An illustration of the capabilities inherent in quantum computers
Author:
- 13 May 2005
- journal article
- Published by American Association of Physics Teachers (AAPT) in American Journal of Physics
- Vol. 73 (6) , 521-540
Abstract
The security of messages encoded via the widely used RSA public key encryption system rests on the enormous computational effort required to find the prime factors of a large number N using classical (conventional) computers. In 1994 Peter Shor showed that for sufficiently large N, a quantum computer could perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the nonexpert, the RSA encryption protocol; the various quantum computer manipulations constituting the Shor algorithm; how the Shor algorithm performs the factoring; and the precise sense in which a quantum computer employing Shor’s algorithm can be said to accomplish the factoring of very large numbers with less computational effort than a classical computer. It is made apparent that factoring N generally requires many successive runs of the algorithm. Our analysis reveals that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- From Cbits to Qbits: Teaching computer scientists quantum mechanicsAmerican Journal of Physics, 2002
- Quantum cryptographyReviews of Modern Physics, 2002
- Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonanceNature, 2001
- From Schrödinger’s equation to the quantum search algorithmAmerican Journal of Physics, 2001
- Discrete Logarithms: The Past and the FutureDesigns, Codes and Cryptography, 2000
- Quantum computingAmerican Journal of Physics, 1998
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997
- Quantum computation and Shor's factoring algorithmReviews of Modern Physics, 1996
- Selling PrimesMathematics Magazine, 1995
- Selling PrimesMathematics Magazine, 1995