10.7 Shor’s factoring algorithm

We now have the tools we need for Shor’s factoring algorithm to factor integers in polynomial time on a sufficiently large quantum computer. The is a near-exponential improvement over the best known classical methods we described in section 10.2. algorithm$Shor’s factoring Shor’s factoring algorithm factoring$Shor’s algorithm

The complete algorithm has both classical and quantum components. Work is done on both kinds of machines to get to the answer. The quantum portion drops us down to polynomial complexity in the number of gates using phase estimation, order finding, modular exponentiation, and the QFT.

Let odd M in Z be greater than 3 for which you have already tried the basic tricks from section 10.2.3 to check that it is not a multiple of 3, 5, 7, and so on. So that you don’t waste your time, you should also try trial division using a small list of primes, although this is not necessary...