10.6 Shor’s algorithm

We now have the tools we need to sketch Shor’s algorithm for factoring integers in polynomial time on a sufficiently large quantum computer.

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

Let odd M in Z be greater than 3 for which you have already tried the basic tricks from subsection 10.2.3 M is not a power of a prime number, and you can use Newton’s method to test this.

So M is an odd positive number in Z that is not a power of a prime. It has a reasonable chance of being composite.

The following is the general approach to Shor’s algorithm given M as above:

1. Choose a random number a such that 1 < a < M. Keep track of...