Shor's Algorithm - From Factoring to Period Finding

As a refresher, when we want to factor an integer $N$, we want to find the non-trivial square root $X$ of the congruence $X^{2}\equiv1\space (mod \space N)$. Then we feed the obtained $X$ into an efficient algorithm that calculates the greatest common divisor of two numbers to obtain two factors of $N$ with $gcd(N, X\pm1)$. Now, the agenda of this lesson is to find $X$. So, let’s get started.

Let’s revisit our problem from the previous lesson. We want to factor $N=21$. Let’s pick an $X$ at random, where $1 < X < N-1$. The inequality exists as we are not interested in obtaining $1$ or $N$ itself as its own factor, defeating the purpose of our original problem. Let’s say we pick $N=2$. Now, we create a table with two columns and multiple rows. In the first column, we have $a$, which is the number to which we shall be raising $X=2$. In the second column, we have a function $f(a)=X^{a}\space (mod\space N)$, which shows us the remainder we get after raising $X=2$ to that $a$ and then dividing it by $N=21$.