Shor's Factoring Algorithm and Modern Cryptography. An Illustration of the Capabilities Inherent in Quantum Computers

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 (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.

References in corpus (5)

• Quantum Cryptography
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• From Cbits to Qbits: Teaching computer scientists quantum mechanics
• Quantum Computing

Cited by in corpus (16)

• Demonstration of Shor's quantum factoring algorithm using photonic qubits
• Quantum simulation of the single-particle Schrodinger equation
• A scalable network for simultaneous pairwise quantum key distribution via entanglement-based time-bin coding
• On the Role of Coherence in Shor's Algorithm
• What Quantum Measurements Measure
• Experimental simulation of quantum tunneling in small systems
• Large-Scale Simulation of Shor's Quantum Factoring Algorithm
• Qcmpi: A Parallel Environment for Quantum Computing
• Qdensity - a Mathematica Quantum Computer Simulation
• Versatile Configuration and Control Framework for Real Time Data Acquisition Systems
• Effects of imperfections for Shor's factorization algorithm
• Classical realization of the quantum Deutsch algorithm
• Popper's Experiment and Superluminal Communication
• Expected Optimal Time for the NMR Implementation of Shor's Algorithm for Factorising 15
• On the success probability of quantum order finding
• Tight Success Probabilities for Quantum Period Finding and Phase Estimation