The Shor Factoring Algorithm

We are now ready to look at the Shor factoring algorithm and how it allows us to break the RSA encryption. The key feature is finding the two prime factors of $N$. That would seem to be a relatively straightforward thing to do. We just go through the list of prime numbers less than $N$ and find those that divide $N$ exactly. Once we have found two factors that are prime numbers, we are done; we could use that information to break the RSA encryption. But, if you think about how many numbers you need to check for large values of $N$, you should be able to convince yourself that the task is hopeless even with today’s supercomputers to help you out. For example, if $N$ has $300$ digits, we have about $\sqrt{10^{300}} = 10^{150}$ prime numbers to try (this is just a rough estimate based on the fact that one of the factors of $N$ will be less than $\sqrt N$. Let’s say that your computer can check one number in $10^{−8}$ seconds. It would then take about $10^{142}$ seconds to complete the factoring. Of course, you might get lucky and find a factor early on, but on average, it’s going to take a long time.