Shor’s Algorithm

In this chapter, we will discuss the famous Shor’s algorithm. Shor’s algorithm is famous for having the potential to break the currently widely used encryption (e.g., RSA), and it was the invention of Shor’s algorithm that ignited the widespread interest in quantum computing in the late 1990s. The quantum computing part of Shor’s algorithm is only for period finding. It is then combined with a classical algorithm to perform integer factorization in order to break the classical encryption. We will discuss the background of prime integer factorization but will not go deep into the theory. And then we will show how Shor’s algorithm can help to find the period of a function that is the essential part of prime integer factorization.