Implementation of Shor's Algorithm and Reliability of Quantum Computing Devices

Abstract

The process to find the prime factors of a large number, the "factoring problem"is believed to be a very hard problem. For this reason, it is the cornerstone of modern cryptographic schemes, like RSA cryptosystem. In 1994, Professor Peter Shor proposed a new polynomial-time quantum algorithm that finds the prime factors of a number with many digits. This was a bolt from the blue for the security of transactions and electronic communications and became an example of how quantum computing changes our perception of security and safety. In this paper Shor's Algorithm is presented and an implementation, a way to factor number 21 is described. In addition, some reliability issues of quantum devices were considered in order to explore the potentiality of Shor's algorithm. © 2021 ACM.