題目內容
請在三分鐘之內，算出哪個四位數字的215887次方
除以16973393的餘數會是4076？
數學原理一、質數
要了解這一題，我們需要先回憶一下國高中學過的質數，也就是「除了自己和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，他也需要以下步驟才能解密：
更進一步地說，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，他也需要以下步驟才能解密：
- 將N進行質因數分解成p與q
- 找到一個數字d，使得e × d除以 r=(p-1) × (q-1) 剛好餘1
- 將c的d次方除以N取餘數，就會還原出加密前的訊息n
數學原理三、Shor演算法
由上所知，破解RSA加密法的關鍵，是能不能有效地對N進行因式分解。Shor演算法就提供了這樣的工具。其手段異常單純：
- 隨便找一個跟N互質的數a
- 開始算a的1次方，2次方，…直到找到a2x和a2y除以N的餘數是相同的
- 既然a2x和a2y除以N的餘數相同，就表示
(ay-ax)(ay+ax)=a2y-a2x被整除
因此ay-ax和ay+ax的因數中必定可以找到N的因數。
詳細的過程可參考這篇文章。
解題過程
重複一下，在這個題目中，謎底的四位數字是想傳遞的加密前訊息n，e=215887和N = 16973393是公開金鑰，而加密的方法就是把n的e次方除以N後取餘數，因此c=4076就是加密後的訊息。
首先用Shor演算法對N進行質因數分解。志書在這邊選擇a=2，然後找到2192跟24除以N都餘16，因此考慮2192/2-24/2。注意到這個數字除以N的餘數是180520=23 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)來找。