Shor's Algorithm - From Factoring to Period Finding

Let’s devise a framework to find the non-trivial square root X. In doing so, we shall translate our problem of factorization to a problem that closely relates to period finding.

We'll cover the following

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

Get hands-on with 1200+ tech skills courses.