Example implementation on a quantum computer, N = 15, a = 2

In this section, we will sketch the process for implementing Shor's algorithm, including the quantum computing sections, to factor N = 15. The steps for designing the preceding quantum circuit f(x) = a^x (mod N) involves designing a special quantum circuit for each a < N that the classical algorithm might randomly choose. To simplify our example, we will assume that the classical portion of the algorithm randomly chooses a = 2.

Let's say N = 15. Let's trace through the an example, beginning by doing the following on a classical computer:

1. Pick a random integer a, so that a < 15. Our code picked 2 in this example.
2. Compute g = gcd(a,N) = gcd(2,15) = 1:
   3. Since g = 1, we have to keep going!
   4. Dispatch the problem of finding the period of f(x) = a^x (mod N) = 2^x (mod 15) to a quantum computer.