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

arXiv:quant-ph/0411184American Journal of PhysicsMay 13, 200576 citations

Quantum Factorization: Shor's Algorithm

Rafael Pereira da Silva

Jan 1, 20240 citations

Using Single Time of Quantum Computer for Shor's Factoring Algorithm

Yousef Alhammadi

Peter Shor's in 1994 developed a factoring algorithm that can factor a composite number $\boldsymbol{n}$ in a polynomial time by using a quantum computer in one step of the algorithm. The algorithm may contain a loop that requires calling a quantum computer many times to find the order of selected number $a, a\in Z_{n}$ . In this paper, the improvement to the Shor's factoring algorithm guarantees the single use of the quantum computer to find the order, where the rest of the algorithm can be implemented by a classical computer. A numerical example for the original and improved version is presented.Peter Shor's in 1994 developed a factoring algorithm that can factor a composite number$\boldsymbol{n}$in a polynomial time by using a quantum computer in one step of the algorithm. The algorithm may contain a loop that requires calling a quantum computer many times to find the order of selected number$a, a\in Z_{n}$. In this paper, the improvement to the Shor's factoring algorithm guarantees the single use of the quantum computer to find the order, where the rest of the algorithm can be implemented by a classical computer. A numerical example for the original and improved version is presented.

International Conference on IT Innovation and Knowledge Discovery (ITIKD)Mar 8, 20230 citations

Shor’s Algorithm for Quantum Factoring

Manisha J. Nene, Gaurav K. Upadhyay

Advances in intelligent systems and computingJan 1, 201614 citations

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

Gerjuoy, E

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

Nov 25, 200450 citations

Study on Implementation of Shor’s Factorization Algorithm on Quantum Computer

Mandeep Kumar, Bhaskar Mondal

SN Computer ScienceApr 8, 202433 citations

Peter Shor's in 1994 developed a factoring algorithm that can factor a composite number

\boldsymbol{n}

in a polynomial time by using a quantum computer in one step of the algorithm. The algorithm may contain a loop that requires calling a quantum computer many times to find the order of selected number

a, a\in Z_{n}

. In this paper, the improvement to the Shor's factoring algorithm guarantees the single use of the quantum computer to find the order, where the rest of the algorithm can be implemented by a classical computer. A numerical example for the original and improved version is presented.

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.