RSA系列——大質數找尋

01-27

RSA的安全性關鍵在於大整數的分解是十分困難的。本節將討論大質數的尋找辦法。

根據素數定理： $pi(n)sim frac{n}{lnn}$ 。隨機一個數 $n$ ，它是質數的概率是 $frac{1}{lnn}$ （此結論存疑，真實值應該是比這要高的，但足夠了）。

上一章提到過費馬小定理，根據其逆否命題，有：若正整數 $a,n$ 滿足 $a<n$ 且 $a^{n-1}notequiv1$ ，則 $n$ 是合數。但很遺憾此命題的否命題並不成立。數論上存在「偽素數」的概念：若 $a^{n-1}equiv 1(mod n)$ 且 $n$ 為合數，則稱 $n$ 是一個基於 $a$ 的偽素數。研究表明，即使是只取基數 $a=2$ ，檢驗結果的正確率也是很可觀的。但如果要追求完美，想要通過改變基數進行多次檢驗來提高正確率，會有一種叫做卡邁克爾（Carmichael）數的數讓人感到十分尷尬。若 $n$ 是卡邁克爾數，對於任意與 $n$ 互質的 $a$ 有 $a^{n-1}equiv1(mod n)$ （雖說對於與 $n$ 不互質的 $a$ 是可以檢測出來的，但若 $n$ 是大質數的乘積， $varphi(n)$ 幾乎是與 $n$ 處於相同數量級的）。

令人慶幸的是，只需要一個小引理便可以對抗卡邁克爾數：若p為質數，則同餘方程 $x^2equiv1(mod p)$ 在模 $p$ 意義下只有兩解 $xequivpm 1(mod n)$ 。能看懂之前內容的讀者應該很容易就能對此進行證明（不過事實上，若 $p$ 是奇素數， $egeq 1$ ，上述引理對於模 $p^e$ 也成立）。

同餘方程 $x^2equiv1(mod n)$ 除 $xequivpm 1(mod n)$ 的任何根稱為以 $n$ 為模的1的非平凡平方根。根據上述引理的逆否命題，得推論：若 $n$ 存在以 $n$ 為模的1的非平凡平方根，則 $n$ 是合數。它的否命題不成立，但若 $n$ 不是質數或質數的冪就成立了。證明也很簡單。

有了這些事實，我們便可以開始敘述著名的Miller-Rabin演算法（以下簡稱MR）了。注意：偽素數測試並不是MR（筆者身邊有人犯過把偽素數測試當作MR的錯誤）。

MR較偽素數測試區別是，MR增加了非平凡平方根的檢驗。因此當選定了基數 $a$ 之後，在計算 $a^{n-1} mod n$ 時，需要稍微改變快速冪的演算法。令 $n-1=u2^t$ ，其中 $u$ 為奇數那麼 $a^{n-1}=(a^u)^{2^t}$ ，那麼只需先算出 $a^u mod n$ 的值，再將其連續平方 $t$ 次，在此過程中檢驗非平凡平方根即可。

顯然MR是可能出錯的。若我們把可以證明 $n$ 為合數的基數 $a$ 稱為一個「證據」，可以證明，隨機得到一個是證據的基數的概率不小於 $frac{1}{2}$ 。也就是說，隨機選取 $s$ 個基數進行驗證，出錯概率至多為 $2^{-s}$ 。事實上這個概率還可以進行優化，且可以通過構造 $n$ 的方法增加證據的數量。由於所用的界已經足夠了，在此不再贅述。畢竟，經過人們的計算，即便是上述最簡單的MR，取 $s=50$ 個基數進行驗證時，若返回結果為 $n$ 為質數，已足夠令人信服了。

至此算導搬運工作已結束。下次將進入RSA的另一個方面。