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.

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

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

aa f(a)=Xa (mod N)f(a)=X^{a}\space (mod\space N)
0{0} 201 (mod 21)2^{0}\equiv1\space (mod \space 21)
1{1} 212 (mod 21)2^{1}\equiv2\space (mod \space 21)
2{2} 224 (mod 21)2^{2}\equiv4\space (mod \space 21)
3{3} 238 (mod 21)2^{3}\equiv8\space (mod \space 21)
4{4} 2416 (mod 21)2^{4}\equiv16\space (mod \space 21)
5{5} 2511 (mod 21)2^{5}\equiv11\space (mod \space 21)
6{6} 261 (mod 21)2^{6}\equiv1\space (mod \space 21)
7{7} 272 (mod 21)2^{7}\equiv2\space (mod \space 21)
8{8} 284 (mod 21)2^{8}\equiv4\space (mod \space 21)
...... ......

Interestingly, after the 252^5 entry, the remainders in the congruence start repeating. This repetition means that the function is periodic. Here, 66 is the period or order rr of the function above. Notice that we can write the first repetition 262^{6} as 26=23×232^6=2^3\times2^3. We can rewrite this as (23)2(2^3)^2 to mimic the form X2X^2. So, this gives us (23)21 (mod 21)(2^3)^2\equiv1\space (mod\space 21). What is 232^3? Yep, 88. How was 88 significant? Well, X=8X=8 was a non-trivial square root of X21 (mod N)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 XX!

Get hands-on with 1200+ tech skills courses.