Shor's algorithm – classical implementation

Now. let's look at the classical subroutine. We know that to find the period of f(x) = a^x (mod N), we just need to find the points along x that are the closest together for which the function repeats itself. We know f(0) = a⁰ (mod N) = 1, so starting there, let's find the smallest x where the function is one again. In code this is as follows:

import itertools
def period_finding_classical(a,N):
    for r in itertools.count(start=1):
         if a**r % N == 1:
             return r

This algorithm assumes a is greater than zero. Note that the code only reaches this subroutine if the GCD of the random number we chose a and the number we wish to factor N isn't one and N isn't one. If a is zero, gcd(a,N) will always be N and thus this period-finding algorithm will never be reached.

Let's run the algorithm in classical mode a few times for our examples N = 7, 15, 2257, and 837:

print(shors_algorithm_classical(7))
print(shors_algorithm_classical(15))
print(shors_algorithm_classical(2257))
print(shors_algorithm_classical(837))

One example run gives us the following output:

(7, 1)
(3, 5)
(37, 61)
(3, 279)

Running it again, we can see that, because 837 isn't the product of primes, the two factors the algorithm returns can be different. For example, another run may produce the following output:

(7, 1)
(5, 3)
(37, 61)
(9, 93)