## Want to keep learning?

This content is taken from the Keio University's online course, Understanding Quantum Computers. Join the course to learn more.
3.8

# The Period of a Function

A lot of mathematical functions are periodic. That is, if you start in some place and move forward, eventually the sequence of values repeats itself. The time it takes for that repetition to occur is called the period.

Written in mathematical terms, we can say that a function $$f(x)$$ is periodic with period $$r$$ if

$f(x + r) = f(x)$

for all of the possible values of $$x$$.

For example, consider $$f(x) = 3^x \bmod 10$$, where $$\bmod$$ is the modulo operator. The modulo operator gives you the remainder when you divide the two numbers, or equivalently, the last digit of the number rewritten in that base (here, ten):

$$f(0) = 3^0 \mod 10 = 1 \bmod 10 = 1$$ $$f(1) = 3^1 \mod 10 = 3 \bmod 10 = 3$$ $$f(2) = 3^2 \mod 10 = 9 \bmod 10 = 9$$ $$f(3) = 3^3 \mod 10 = 27 \bmod 10 = 7$$ $$f(4) = 3^4 \mod 10 = 81 \bmod 10 = 1$$ $$f(5) = 3^5 \mod 10 = 243 \bmod 10 = 3$$

We can see the cycle $$1\rightarrow 3\rightarrow 9\rightarrow 7\rightarrow 1$$, so the period $$r = 4$$: $$f(0) = f(4) = f(8) = f(12) = 1$$. This period does not change depending on where you start; we can see that the period is still four if we look at $$f(1) = f(5) = f(9) = 3$$.

To be clear about the modulo arithmetic as well as the cycle, let us look at a second example, $$f(x) = 5^x \mod 7$$:

$$f(0) = 5^0 \mod 7 = 1 \bmod 7 = 1$$
$$f(1) = 5^1 \mod 7 = 5 \bmod 7 = 5$$
$$f(2) = 5^2 \mod 7 = 25 \bmod 7 = 4$$
$$f(3) = 5^3 \mod 7 = 125 \bmod 7 = 6$$
$$f(4) = 5^4 \mod 7 = 625 \bmod 7 = 2$$
$$f(5) = 5^5 \mod 7 = 3125 \bmod 7 = 3$$
$$f(6) = 5^6 \mod 7 = 15625 \bmod 7 = 1$$

We can see a period of $$r = 6$$: $$1\rightarrow 5\rightarrow 4\rightarrow 6\rightarrow 2\rightarrow 3 \rightarrow 1$$. Thus, $$f(4) = f(10) = f(16) = f(22) = 2$$.

As with many problems we are discussing, these examples are not hard when the problem size is small, but as the problem size grows, the difficulty of determining that period $$r$$ increases quickly.

# 関数の周期性

$$f(0) = 3^0 \mod 10 = 1 \bmod 10 = 1$$ $$f(1) = 3^1 \mod 10 = 3 \bmod 10 = 3$$ $$f(2) = 3^2 \mod 10 = 9 \bmod 10 = 9$$ $$f(3) = 3^3 \mod 10 = 27 \bmod 10 = 7$$ $$f(4) = 3^4 \mod 10 = 81 \bmod 10 = 1$$ $$f(5) = 3^5 \mod 10 = 243 \bmod 10 = 3$$

モジュロ演算と循環については、以下の例$$f(x) = 5^x \mod 7$$を見てみましょう。

$$f(0) = 5^0 \mod 7 = 1 \bmod 7 = 1$$
$$f(1) = 5^1 \mod 7 = 5 \bmod 7 = 5$$
$$f(2) = 5^2 \mod 7 = 25 \bmod 7 = 4$$
$$f(3) = 5^3 \mod 7 = 125 \bmod 7 = 6$$
$$f(4) = 5^4 \mod 7 = 625 \bmod 7 = 2$$
$$f(5) = 5^5 \mod 7 = 3125 \bmod 7 = 3$$
$$f(6) = 5^6 \mod 7 = 15625 \bmod 7 = 1$$

ここで$$r = 6$$: $$1\rightarrow 5\rightarrow 4\rightarrow 6\rightarrow 2\rightarrow 3 \rightarrow 1$$という周期になることがわかります。したがって、$$f(4) = f(10) = f(16) = f(22) = 2$$なります。 大抵の問題はそうですが、小規模の処理のの場合は問題なく周期を発見することができますが、これが大規模になると周期$$r$$を決定するのが困難になってきます。