Abstract

The advancement of quantum computing in recent years poses severe threats to the RSA public-key cryptosystem. The RSA cryptosystem fundamentally relies its security on the computational hardness of number theory problems: prime factorization (integer factoring). Shor’s quantum factoring algorithm could theoretically solve the computational problem in polynomial time. This paper contributes to the experiment and demonstration of Shor’s quantum factoring algorithm for RSA prime factorization using IBM Qiskit. The performance of the implementation is evaluated based on the speed of user time and the success probability. The results show that a larger N improves factorization’s computational hardness, which forces the use of more qubits to solve. A further enhancement is also required to increase the algorithm’s success probability and reduce the number of shots.