RSA Encryption and Factoring

The Shor factoring algorithm is perhaps the most famous of the “classic” quantum computing algorithms. The problem Shor wanted to solve is how to factor large numbers. This is an interesting problem because factoring large numbers allows you to break many encryption codes. Bob and I want to alert you, Cardy, (and our dedicated readers) that this chapter is rather challenging. It uses results from number theory and some more advanced math called the Fourier transform. We have worked hard to explain all the steps without the advanced math, but there are many steps. We provide examples and graphs to help build intuition about the results, but we know from our own experience it takes time to get your head wrapped around these ideas.

Once we get to the quantum part of what Shor did, we will see familiar tools from other quantum algorithms: superposition states, quantum function gates, and measurement devices. Nevertheless, expect to spend more time on this chapter than you did on the others. We hope that the results of your efforts will be satisfying in providing more insight into how encryption works and how quantum algorithms are engineered to take advantage of the nature of quantum states. But given the length of the arguments, I suggest that you feel free to try out the algorithms without going through all the details of the justifications for the steps. Once you see what the algorithm does, you can come back later to look at the detailed explanations.