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$.

$a$	$f(a)=X^{a}\space (mod\space N)$
${0}$	$2^{0}\equiv1\space (mod \space 21)$
${1}$	$2^{1}\equiv2\space (mod \space 21)$
${2}$	$2^{2}\equiv4\space (mod \space 21)$
${3}$	$2^{3}\equiv8\space (mod \space 21)$
${4}$	$2^{4}\equiv16\space (mod \space 21)$
${5}$	$2^{5}\equiv11\space (mod \space 21)$
${6}$	$2^{6}\equiv1\space (mod \space 21)$
${7}$	$2^{7}\equiv2\space (mod \space 21)$
${8}$	$2^{8}\equiv4\space (mod \space 21)$
$...$	$...$

Interestingly, after the $2^5$ entry, the remainders in the congruence start repeating. This repetition means that the function is periodic. Here, $6$ is the period or order $r$ of the function above. Notice that we can write the first repetition $2^{6}$ as $2^6=2^3\times2^3$. We can rewrite this as $(2^3)^2$ to mimic the form $X^2$. So, this gives us $(2^3)^2\equiv1\space (mod\space 21)$. What is $2^3$? Yep, $8$. How was $8$ significant? Well, $X=8$ was a non-trivial square root of $X^{2}\equiv1\space (mod \space N)$. This is exactly what we set out to find! And this right here is the procedure for finding $X$!