10.6 Order and period finding

The next tool we need for Shor’s algorithm is an algorithm to find out when certain types of functions start repeating themselves. algorithm$order-finding

Consider the function k ↦ a^k on whole numbers k for a fixed a in N greater than 1. For example, if a = 3, the first 12 values are

or in Python:

[3**n for n in range(12)]
    

[1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147]
    

As we look at larger exponents k, the values of 3^k will get larger and larger.

If we instead use modular arithmetic, as we saw in section 3.7, 3^k cannot get arbitrarily large. For example, modulo M = 13, the values we get for the function k ↦ a^k mod 13 are number$modular integer integer$modular modulo

[3**n % 13 for n in range(12)]

[1, 3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9]

Here, “%” is the Python “remainder operator,” and it implements...