Enjoy Shor's Prime Factorization with a Mobilephone App

This is the English translation of this article.
[Abstract] To fully execute the well-known Shor's Factoring Algorithm, a large-scale fault-tolerant quantum computer is required, and with current quantum computers, this is unlikely to happen. However, when an ideal quantum computer appears, it is believed that this algorithm will have a huge impact on cybersecurity. Here, we created an app to apply Shor's algorithm to small integers (products of two prime numbers). This will allow you to become familiar with Shor's algorithm and deepen your understanding.

🔴 Overview of Shor's Factoring
There are many explanations of Shor's algorithm, but I was drawn to the YouTube video by Elucyda shown in Fig. 1. It takes about 25 minutes, and he explains it clearly and step by step, using only a whiteboard and clearly handwritten. This is great!

Shor's algorithm is said to be difficult to understand, but the outline is on this one page (8 lines). It involves prime factorizing an integer N, which is the product of two prime numbers. If N is small, it is not difficult to create an original program on a classical computer by following the steps in this diagram. However, you should pay attention to the part surrounded by a red frame in Fig. 1, "Find MIN r>0 such that a^r=1 mod N". This finds the smallest integer r (order) such that a^r = 1 mod N when you bring in another integer a for the integer N you want to factorize. This is nothing more than finding the minimum period of the repeating wave of the value of a^r mod N.

For very large N, this order-finding is the core of Shor's algorithm, and this is where quantum computers come into play. (This article is only beginner level. Without a complete understanding of quantum algorithms for order finding, it cannot be called intermediate level or above. I would like to write about this in another article.) Since we are assuming a small N this time, we have realized the entire processing of Fig. 1 as a mobilephoe app. This will help you become familiar with Shor's algorithm, and will also serve as a preparation for creating quantum programs later.

🔴 Creating a mobile phone app

Originally, the search for the above order r would be performed as a quantum algorithm, but since we are creating a mobile phone app here, this part is also a primitive (naive) program that runs on a classical computer. Fig. 2 shows the order calculation function created with MIT App Inventor. It should be noted that there is a risk of overflow when calculating a^r, especially when the value of r becomes large. Therefore, in order to prevent this to a certain extent, we do not calculate a^r mod N directly, but instead use repeated calculations using a small r.

🔴 Review of execution results

Let's start by trying to prime factorize a small integer, for example N=247, with this app. (N is given as the product of two prime numbers p=19 and q=13.) Figure 3 shows two successful examples. In Figure (a), the integer a randomly set in Figure 1 happened to be GCD(q, a)>1, so factorization was completed immediately. This corresponds to Case 1 in Figure 1. On the other hand, Figure (b) corresponds to Case 2 in Figure 1, and factorization was successful as expected.

Figure 4 shows different cases of failure. In Figure 4(a), the order r for a random integer a could not be found within the preset range. Furthermore, in Figure 4(b), the random integer a and the order r were set successfully, but prime factorization failed. This corresponds to Case 3 in Figure 1. Shor's algorithm thus succeeds probabilistically (by heuristics). However, it is known that the success rate is quite high.

🔴Why can this algorithm be used for prime factorization?

This article focuses on how Shor's algorithm works, not on why it can be used for factorization. However, I would like to briefly explain the key points of why below. One of them, which may be surprising, is the following formula (junior high school math!):

      a² - 1 = (a + 1)(a - 1)

Using this, a^r-1 = 0 mod N in the explanation of Fig. 1 becomes (a^r/2 + 1)(a^r/2 - 1) = 0 mod N. In other words, the left side of = is divisible by N. Therefore, one of the prime numbers that make up N divides one of the factors on the left side. From this, GCD(N, a^r/2 + 1) and GCD(N, a^r/2 -1) should be prime factors of N. When we calculate the case of Fig.3(b) (a = 30, r = 6), we see that this is indeed the case, as shown below:

     GCD(30^6/2+1, 247) = GCD(27001, 247) = 13

     GCD(30^6/2 -1, 247) = GCD(26999, 247) = 19

Incidentally, the algorithm for finding the underlying order r turns out to be roughly equivalent to the (precise) quantum phase estimation already described here and here, which makes Shor's algorithm more familiar.

ショアの素因数分解に親しむためのスマホアプリ

 【要旨】著名なShor's Factoring Algorithmの本格的な実行には、大規模な誤り耐性量子コンピュータが必要であり、現時点の量子コンピュータでは、その実現がほとんど望めない。だが、理想的な量子コンピュータが出現した時には、このアルゴリズムが与えるインパクトは、サイバーセキュリティ上、非常に大きいと考えられている。ここでは、小さな整数（２つの素数の積）に対して、このショアのアルゴリズムを適用するためのスマホアプリを作成した。それによって、Shor'sに親しみを持ち、理解を深めることができた。

🔴Shor's Factoringの概要
　ショアのアルゴリズムの解説は多数存在するが、私は、Fig.1に示したElucyda氏によるYoutubeビデオに注目した。約25分で、白板１枚だけを使って、鮮明に手書きしながら、分かりやすくstep by stepで説明している。これは上手、素晴らしい！

　難解と言われるショアのアルゴリムだが、概要はこの１枚（８行）である。２つの素数の積である整数Nを逆に素因数分解するのである。小さなNであれば、この図の手順に従って、パソコンなどで独自にプログラムを作って確かめることは難しくない。ただし、注意すべきは、Fig.1の赤枠で囲った部分、"Find MIN r>0 such that a^r=1 mod N"である。これは、因数分解したい整数Nに対して、別のある整数aをもってきた時に、a^r = 1 mod Nとなる最小の整数r（位数）を求めるのである。これは、a^r mod Nの値の繰り返しの最小周期を求めることに他ならない。

　非常に大きなNに対しては、この位数探索がショアのアルゴリズムの根幹であり、量子コンピュータの出番となるところなのである。（この記事は初級レベルに過ぎない。位数探索のための量子アルゴリズムの完全理解無しでは、中級レベル以上と言えないのである。）今回は、小さなNを想定するので、Fig.1の処理全体をスマホのアプリとして実現した。ショアのアルゴリズムに親しむとともに、この後の量子プログラム作成の準備ともなる。

🔴スマホアプリの作成
　本来は、量子アルゴリズムとして上記の位数rの探索を行うのだが、ここではスマホアプリとして作るので、この部分も古典コンピュータで動く原始的な（ナイーブな）プログラムとした。Fig.2は、MIT App Inventorで作った位数計算関数である。

　注意点として、a^rの計算で、特にrの値が大きくなるとオーバーフローを起こす恐れがある。そこで、一定程度それを抑止するため、a^r mod Nの計算をダイレクトに行わずに、小さなrを使った繰り返し計算で実現している。

🔴実行結果の検討
　早速だが、このスマホアプリで、小さな整数、例えばN=247を素因数分解してみる。（このNは２つの素数p=19とq=13の積として与えた。）成功した２例をFig.3に示す。このうち、図(a)は、Fig.1においてランダムに設定した整数aが、たまたまGCD(q, a)>1となったので、因数分解はすぐに完了した。Fig.1のCase1に該当する。また、図(b)の方はFig.1のCase2に該当し、正常に因数分解ができた。

　一方、失敗した場合をFig.4に示す。このうち図(a)は、当方で適宜設定した、ランダムな整数aと求める位数rの値の制限範囲内においては、値rの探索に失敗した場合である。また、図(b)の方は、ランダムな整数aと位数rは設定できたものの、素因数分解に失敗したケースである。これは、Fig.1でのCase3に該当する。Shorのアルゴリズムは、このように、確率的（発見的）に成功するものである。ただし、その成功確率はかなり高いことが分かっている。

🔴なぜこのアルゴリズムで素因数分解できるのか
　本記事は、なぜショアのアルゴリズムで因数分解できるのか、ではなく、どのように働いているのかを中心に述べている。とはいえ、whyについても以下にポイントを簡単に述べてみたい。意外かもしれないが、その一つは、以下の計算式（中学校数学）にあった。

a² - 1 = (a + 1)(a - 1)

　これを使うと、Fig.1の説明にある、a^r-1 = 0 mod Nは、(a^r/2 + 1)(a^r/2 - 1) = 0 mod Nとなる。すなわち、=の左辺は、Nで割り切れる。だから、Nを構成する一つの素数は左辺のどちらかの因子を割り切る。このことから、GCD(N, a^r/2 + 1)とGCD(N, a^r/2 -1)がNの素因数となるはずである。Fig.3(b)の場合（a = 30, r = 6）を計算してみると、以下の通り

確かにそうなる。

     GCD(30^6/2+1, 247) = GCD(27001, 247) = 13

     GCD(30^6/2 -1, 247) = GCD(26999, 247) = 19

　ところで、根幹をなす位数rを見つけるアルゴリズム（finding the order）は、すでにこことここに述べた（精密な）量子位相推定とほぼ同等であることが分かっている。このことからも、Shor'sアルゴリズムへの親しみは増すのである。