Physics – Quantum Physics
Scientific paper
2004-11-25
Physics
Quantum Physics
Scientific paper
10.1119/1.1891170
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 (i.e., conventional) computers. In 1994, however, Peter Shor showed that for sufficiently large N a quantum computer would be expected to perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the non-expert readers of this journal: (i) the RSA encryption protocol; (ii) the various quantum computer manipulations constituting the Shor algorithm; (iii) how the Shor algorithm performs the factoring; and (iv) 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 can. It is made apparent that factoring $N$ generally requires many successive runs of the algorithm. The careful analysis herein reveals, however, that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.
No associations
LandOfFree
Shor's Factoring Algorithm and Modern Cryptography. An Illustration of the Capabilities Inherent in Quantum Computers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Shor's Factoring Algorithm and Modern Cryptography. An Illustration of the Capabilities Inherent in Quantum Computers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shor's Factoring Algorithm and Modern Cryptography. An Illustration of the Capabilities Inherent in Quantum Computers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-353565