Chapter 3 Integer Factorization and RSA3.1 Euler’s Formula and Roots Modulo pq
在 2.3 和 2.4 一節中我們介紹的 Diffie-Hellman 密鑰交換協議和 Elgamal 公鑰加密方案依賴於計算冪次是簡單的但是根據和恢復指數項是困難的這一事實。在分析 Diffie-Hellman 和 Elgamal 的安全性時，我們用到了費馬小定理：
費馬小定理揭示了素數的一個很漂亮的性質。很自然的我們會考慮，如果我們把替換成一個不是素數的整數，那麼仍然成立麼？1.4 一節中的例 1.28 給出了一個否定的答案。在這一節中，我們將研究費馬小定理的推廣形式，當，由兩個不同的素數乘積而來。這也是密碼學應用中一個重要情形。其他更一般的情況留在練習 3.4 和 3.5了。
如往常一樣，我們從一個例子開始。那麼在模 15 下的冪次會是什麼樣的。模 15 下的元素的二次冪和三次冪，他們看起來沒什麼有趣的地方。但是元素的四次冪中有很多是等於 1 的，更準確點，我們發現
那麼和有什麼區別呢？可以發現的是，和都有非平凡公因子，而都是和互素的。這表明，如果與模數是互素的，那麼費馬小定理的某些部分也是正確的，就是指數不一定非得是。
對於，我們發現指數是，為什麼是呢？我們可以簡單地檢查的每一個值，但一個更具啟發性的論點會更好。為了使得，檢查下述兩個同餘式就足夠了
因為（3.1）式意味着
因此有
並且，（3.1）式的模數都是素數，於是我們可以用費馬小定理，因此有
考慮這兩個同餘，會發現指數 4 的關鍵性質是對於來說，它是的倍數。注意到若指數為 14 則並非如此。通過這一觀察，我們將描述 RSA公鑰密碼體制 中的一條基本公式。
定理 3.1（對於 pq 的歐拉定理）設為兩個不同素數，並且有
那麼有
通常，為奇素數，所以
證明：假設我們一直，所以我們計算
指數運算法則
費馬小定理
同理我們易得
因此我們證明了同時被整除，因此也被整除。證畢。
Diffile-Hellman 密鑰交換協議和 Elgamal 公鑰密碼系統安全性依賴於解決下述方程的困難性
其中為公開參數，為素數，而為未知變量。而我們下一節將要學習的 RSA 公鑰密碼系統的安全性則依賴於解決下述方程的困難性
其中為公開參數，為未知變量。換句話說RSA 公鑰密碼系統的安全性基於在模下求次根是困難的。
這是合理的假設嗎？如果模是素數，那麼計算模的次根就相對容易，如下一個命題所述。
命題 3.2設素數，整數滿足。根據性質 1.13在模下存在逆元，即存在滿足
因此同餘式
有解
證明：如果，那麼為方程的解。如果，那麼應用費馬小定理。同餘式意味着有
接下來我們驗證為的根：
指數運算法則
因為
指數運算法則
費馬小定理
因此為的根。
為了確認這個解是唯一的，我們設均為（3.2）式的解。前面我們已經證明對於任意非零元素有：，於是
因此模同餘，所以（3.2）式最多僅有一解。證畢。
例 3.3我們嘗試解同餘式
其中是一個素數，由命題 3.2 可知，我們首先需要找到滿足
使用歐幾里得拓展算法我們可以得到，那麼根據命題 3.2，對於上述同餘式我們有解
注 3.4命題 3.2 基於假設，如果沒有這個假設，那麼同餘式中對於有的可能會不存在解。若有解，那麼就會有不止一個解。更多細節可見練習 3.2 。
命題 3.2提到，如果模數為素數，那麼計算次根是容易的。對於合數模數來說似乎也類似，但是有一個關鍵區別。如果我們知道的因此，那麼計算次根是容易的。下述命題將解釋當為兩個素數的乘積時該如何計算次根，剩下其他的情況留作練習 3.6。
命題 3.5設為兩個不同素數，滿足
由命題 1.13 我們知道模下存在逆元，即
那麼同餘式
有解
證明：我麼你假設（其他情況見練習 3.3），命題 3.5的證明和命題 3.2的證明類似，但是這裡不用費馬小定理，這裡我們用歐拉定理。同餘式意味着存在整數滿足
接下來我們檢查是否為的根
，指數運算法則
，因為
指數運算法則
，歐拉定理
因此為 （3.3）式的根。接下來我們證明解的唯一性，假設為 （3.3） 式的根，那麼
因為
，歐拉定理
因為是（）式的解
因此（3.3）式的每一個解都與在模下同餘，因此其為唯一解，證畢
注 3.6命題 3.5 給出了解同餘式的算法，其中第一步是計算滿足的，然後計算。為了加快計算速度，我們可以使用更小的值。設並且假設能夠解出下述同餘式的值
由歐拉定理有，因此命題 3.5 的證明中，我們可以記，那麼
因此，我們使用了個更小的，找到了同餘式的解
例 3.7解下列同餘式
其中模數是兩個素數的積。
第一步我們需要計算滿足
其中，用拓展歐幾里得算法可以得到，由命題 3.5，上述同餘式的有解
根據注 3.6，我們也可以節省一點比特
所以，這意味着我們可以需按照滿足下列同餘式的
計算得到，因此有
注意到，兩次計算我們都得到了同一個答案，當然，這也是應該的。但是我們只需要給 43927 升 5629 次冪，而根據命題 3.5 我們需要升 53509 次冪。因此這節省了些許時間，儘管不上看起來那麼多。回顧一下我們計算的時間複雜度是，因此大約會加速，因為
例 3.8Alice 讓 Eve 解同餘式
因為模數不是素數，因此
是兩個素數的乘積，但如果 Eve 不知道這兩個素數因子，他就沒法使用命題 3.5 描述的算法解決 Alice 的這個問題。在接受了 Eve 對失敗的讓步後，Alice 告訴 Eve。有了這些條件，Alice的問題就變得容易了。Eve計算，計算同餘式計算得到，並計算解
留言列表