在最終關卡，一行人面對一個龐大的整數除法問題。這其實牽涉到質數、質因數分解，乃至於與當今網路安全習習相關的RSA加密法與Shor演算法。由於本題相對較為複雜，想要看解題全部細節的讀者，請參閱［此連結］。以下僅就概念上解釋本題。

題目內容

數學原理一、質數

要了解這一題，我們需要先回憶一下國高中學過的質數，也就是「除了自己和1以外，沒有其他因數」的數。舉例來說，志書等人在找教室時，便是利用881是質數的性質。

而在這裡，我們需要的只有一個性質：

數學原理二、RSA加密法

RSA加密法是一種非對稱加密法，其特點是加密法只需要使用公開的公開金鑰來加密，但解密方必須使用私密金鑰才能解密。這一個設計，讓私密金鑰永遠不需要在網路上傳遞，他人也就不可能靠攔截金鑰來破解。

更進一步地說，RSA最核心的原理，是利用一句聽起來很廢話的概念：
 

利用這個性質，當我們有兩個超級大的質數p和q，RSA構造了一個加密系統，加密方只需要知道p × q即可加密，但解密方需要知道p和q才能解密。這樣一來，只要p和q夠大，我們把p × q公開在網路上也沒關係，反正對方拿到p × q只能加密，要解密的話，他就必須做一個實務上近乎不可能的質因數分解。

舉例來說，這次題目中，謎底的四位數字是想傳遞的加密前訊息n，e=215887和N = 16973393是公開金鑰，而加密的方法就是把n的e次方除以N後取餘數，因此c=4076就是加密後的訊息。

但對於解密方，就算他知道4076也知道N和e，他也需要以下步驟才能解密：

1. 將N進行質因數分解成p與q
2. 找到一個數字d，使得e × d除以 r=(p-1) × (q-1) 剛好餘1
3. 將c的d次方除以N取餘數，就會還原出加密前的訊息n

至於為什麼這樣就可以還原出n，可以參考這裡的證明。

數學原理三、Shor演算法

由上所知，破解RSA加密法的關鍵，是能不能有效地對N進行因式分解。Shor演算法就提供了這樣的工具。其手段異常單純：

1. 隨便找一個跟N互質的數a
2. 開始算a的1次方，2次方，…直到找到a^2x和a^2y除以N的餘數是相同的
3. 既然a^2x和a^2y除以N的餘數相同，就表示 (a^y-a^x)(a^y+a^x)=a^2y-a^2x被整除
   因此a^y-a^x和a^y+a^x的因數中必定可以找到N的因數。

詳細的過程可參考這篇文章。

解題過程

重複一下，在這個題目中，謎底的四位數字是想傳遞的加密前訊息n，e=215887和N = 16973393是公開金鑰，而加密的方法就是把n的e次方除以N後取餘數，因此c=4076就是加密後的訊息。

首先用Shor演算法對N進行質因數分解。志書在這邊選擇a=2，然後找到2¹⁹²跟2⁴除以N都餘16，因此考慮2^192/2-2^4/2。注意到這個數字除以N的餘數是180520=2³ x 5 x 4513，但志書已經檢查過1000以內的質數了，所以試試看4513，就發現N = 16973393 = 4513 x 3761。故p=4513而q=3761，分解完畢。

備註：在這一步，志書跟米珊其實用了一些數論中的小技巧來加速計算，不然一個一個次方算太慢了。大家可以研究看看他們到底用了什麼小技巧。

分解完N後，剩下就簡單了。先找到讓de除以r=(p-1)(q-1)餘1的d=943。將加密後訊息4076的943次方除以N，得到的餘數9487就是加密前的訊息，也就是本題的謎底。

備註：找d的這一步可以透過找ex+ry=1的整數解(x,y)來找。

延伸閱讀

RSA加密法遇上量子電腦

Shor演算法