數(shù)論，數(shù)學中的皇冠，最純粹的數(shù)學。早在古希臘時代，人們就開始癡迷地研究數(shù)字，沉浸于這個幾乎沒有任何實用價值的思維游戲中。直到 計算機誕生之后，幾千年來的數(shù)論研究成果突然有了實際的應(yīng)用，這個過程可以說是最為激動人心的數(shù)學話題之一。最近我在《程序員》雜志上連載了《跨越千年的 RSA 算法》，但受篇幅限制，只有一萬字左右的內(nèi)容。其實，從數(shù)論到 RSA 算法，里面的數(shù)學之美哪里是一萬字能扯完的？在寫作的過程中，我查了很多資料，找到了很多漂亮的例子，也積累了很多個人的思考，但最終都因為篇幅原因沒有 加進《程序員》的文章中。今天，我想重新梳理一下線索，把所有值得分享的內(nèi)容一次性地呈現(xiàn)在這篇長文中，希望大家會有所收獲。需要注意的是，本文有意為了 照顧可讀性而犧牲了嚴謹性。很多具體內(nèi)容都僅作了直觀解釋，一些“顯然如此”的細節(jié)實際上是需要證明的。如果你希望看到有關(guān)定理及其證明的嚴格表述，可以 參見任意一本初等數(shù)論的書。把本文作為初等數(shù)論的學習讀物是非常危險的。最后，希望大家能夠積極指出文章中的缺陷，我會不斷地做出修改。

======= 更新記錄 =======

2012 年 12 月 15 日：發(fā)布全文。
2012 年 12 月 18 日：修改了幾處表達。

======== 目錄 ========

（一）可公度線段
（二）中國剩余定理
（三）擴展的輾轉(zhuǎn)相除
（四）Fermat 小定理
（五）公鑰加密的可能性
（六）RSA 算法

 
 
（一）可公度線段

    Euclid ，中文譯作“歐幾里得”，古希臘數(shù)學家。他用公理化系統(tǒng)的方法歸納整理了當時的幾何理論，并寫成了偉大的數(shù)學著作《幾何原本》，因而被后人稱作“幾何學之 父”。有趣的是，《幾何原本》一書里并不全講的幾何。全書共有十三卷，第七卷到第十卷所討論的實際上是數(shù)論問題——只不過是以幾何的方式來描述的。在《幾 何原本》中，數(shù)的大小用線段的長度來表示，越長的線段就表示越大的數(shù)。很多數(shù)字與數(shù)字之間的簡單關(guān)系，在《幾何原本》中都有對應(yīng)的幾何語言。例如，若數(shù)字 a 是數(shù)字 b 的整倍數(shù)，在《幾何原本》中就表達為，長度為 a 的線段可以用長度為 b 的線段來度量。比方說，黑板的長度是 2.7 米，一支鉛筆的長度是 18 厘米，你會發(fā)現(xiàn)黑板的長度正好等于 15 個鉛筆的長度。我們就說，鉛筆的長度可以用來度量黑板的長度。如果一張課桌的長度是 117 厘米，那么 6 個鉛筆的長度不夠課桌長， 7 個鉛筆的長度又超過了課桌長，因而我們就無法用鉛筆來度量課桌的長度了。哦，當然，實際上課桌長相當于 6.5 個鉛筆長，但是鉛筆上又沒有刻度，我們用鉛筆來度量課桌時，怎么知道最終結(jié)果是 6.5 個鉛筆長呢？因而，只有 a 恰好是 b 的整數(shù)倍時，我們才說 b 可以度量 a 。

    給定兩條長度不同的線段 a 和 b ，如果能夠找到第三條線段 c ，它既可以度量 a ，又可以度量 b ，我們就說 a 和 b 是可公度的（ commensurable ，也叫做可通約的）， c 就是 a 和 b 的一個公度單位。舉個例子： 1 英寸和 1 厘米是可公度的嗎？歷史上，英寸和厘米的換算關(guān)系不斷在變，但現(xiàn)在，英寸已經(jīng)有了一個明確的定義： 1 英寸精確地等于 2.54 厘米。因此，我們可以把 0.2 毫米當作單位長度，它就可以同時用于度量 1 英寸和 1 厘米： 1 英寸將正好等于 127 個單位長度， 1 厘米將正好等于 50 個單位長度。實際上， 0.1 毫米、 0.04 毫米 、 (0.2 / 3) 毫米也都可以用作 1 英寸和 1 厘米的公度單位，不過 0.2 毫米是最大的公度單位。

    等等，我們怎么知道 0.2 毫米是最大的公度單位？更一般地，任意給定兩條線段后，我們怎么求出這兩條線段的最大公度單位呢？在《幾何原本》第七卷的命題 2 當中， Euclid 給出了一種求最大公度單位的通用算法，這就是后來所說的 Euclid 算法。這種方法其實非常直觀。假如我們要求線段 a 和線段 b 的最大公度單位，不妨假設(shè) a 比 b 更長。如果 b 正好能度量 a ，那么考慮到 b 當然也能度量它自身，因而 b 就是 a 和 b 的一個公度單位；如果 b 不能度量 a ，這說明 a 的長度等于 b 的某個整倍數(shù)，再加上一個零頭。我們不妨把這個零頭的長度記作 c 。如果有某條線段能夠同時度量 b 和 c ，那么它顯然也就能度量 a 。也就是說，為了找到 a 和 b 的公度單位，我們只需要去尋找 b 和 c 的公度單位即可。怎樣找呢？我們故技重施，看看 c 是否能正好度量 b 。如果 c 正好能度量 b ，c 就是 b 和 c 的公度單位，從而也就是 a 和 b 的公度單位；如果 c 不能度量 b ，那看一看 b 被 c 度量之后剩余的零頭，把它記作 d ，然后繼續(xù)用 d 度量 c ，并不斷這樣繼續(xù)下去，直到某一步?jīng)]有零頭了為止。

    我們還是來看一個實際的例子吧。讓我們試著找出 690 和 2202 的公度單位。顯然， 1 是它們的一個公度單位， 2 也是它們的一個公度單位。我們希望用 Euclid 的算法求出它們的最大公度單位。首先，用 690 去度量 2202 ，結(jié)果發(fā)現(xiàn) 3 個 690 等于 2070 ，度量 2202 時會有一個大小為 132 的零頭。接下來，我們用 132 去度量 690 ，這將會產(chǎn)生一個 690 - 132 × 5 = 30 的零頭。用 30 去度量 132 ，仍然會有一個大小為 132 - 30 × 4 = 12 零頭。再用 12 去度量 30 ，零頭為 30 - 12 × 2 = 6 。最后，我們用 6 去度量 12 ，你會發(fā)現(xiàn)這回終于沒有零頭了。因此， 6 就是 6 和 12 的一個公度單位，從而是 12 和 30 的公度單位，從而是 30 和 132 的公度單位，從而是 132 和 690 的公度單位，從而是 690 和 2202 的公度單位。

    我們不妨把 Euclid 算法對 a 和 b 進行這番折騰后得到的結(jié)果記作 x 。從上面的描述中我們看出， x 確實是 a 和 b 的公度單位。不過，它為什么一定是最大的公度單位呢？為了說明這一點，下面我們來證明，事實上， a 和 b 的任意一個公度單位一定能夠度量 x ，從而不會超過 x 。如果某條長為 y 的線段能同時度量 a 和 b ，那么注意到，它能度量 b 就意味著它能度量 b 的任意整倍數(shù)，要想讓它也能度量 a 的話，只需而且必需讓它能夠度量 c 。于是， y 也就能夠同時度量 b 和 c ，根據(jù)同樣的道理，這又可以推出 y 一定能度量 d ……因此，最后你會發(fā)現(xiàn)， y 一定能度量 x 。

    用現(xiàn)在的話來講，求兩條線段的最大公度單位，實際上就是求兩個數(shù)的最大公約數(shù)——最大的能同時整除這兩個數(shù)的數(shù)。用現(xiàn)在的話來描述 Euclid 算法也會簡明得多：假設(shè)剛開始的兩個數(shù)是 a 和 b ，其中 a > b ，那么把 a 除以 b 的余數(shù)記作 c ，把 b 除以 c 的余數(shù)記作 d ，c 除以 d 余 e ， d 除以 e 余 f ，等等等等，不斷拿上一步的除數(shù)去除以上一步的余數(shù)。直到某一次除法余數(shù)為 0 了，那么此時的除數(shù)就是最終結(jié)果。因此， Euclid 算法又有一個形象的名字，叫做“輾轉(zhuǎn)相除法”。

    輾轉(zhuǎn)相除法的效率非常高，剛才大家已經(jīng)看到了，計算 690 和 2202 的最大公約數(shù)時，我們依次得到的余數(shù)是 132, 30, 12, 6 ，做第 5 次除法時就除盡了。實際上，我們可以大致估計出輾轉(zhuǎn)相除法的效率。第一次做除法時，我們是用 a 來除以 b ，把余數(shù)記作 c 。如果 b 的值不超過 a 的一半，那么 c 更不會超過 a 的一半（因為余數(shù)小于除數(shù)）；如果 b 的值超過了 a 的一半，那么顯然 c 直接就等于 a - b ，同樣小于 a 的一半。因此，不管怎樣， c 都會小于 a 的一半。下一步輪到 b 除以 c ，根據(jù)同樣的道理，所得的余數(shù) d 會小于 b 的一半。接下來， e 將小于 c 的一半， f 將小于 d 的一半，等等等等。按照這種速度遞減下去的話，即使最開始的數(shù)是上百位的大數(shù)，不到 1000 次除法就會變成一位數(shù)（如果算法沒有提前結(jié)束的話），交給計算機來執(zhí)行的話保證秒殺。用專業(yè)的說法就是，輾轉(zhuǎn)相除法的運算次數(shù)是對數(shù)級別的。

    很長一段時間里，古希臘人都認為，任意兩條線段都是可以公度的，我們只需要做一遍輾轉(zhuǎn)相除便能把這個公度單位給找出來。事實真的如此嗎？輾 轉(zhuǎn)相除法有可能失效嗎？我們至少能想到一種可能：會不會有兩條長度關(guān)系非常特殊的線段，讓輾轉(zhuǎn)相除永遠達不到終止的條件，從而根本不能算出一個“最終結(jié) 果”？注意，線段的長度不一定（也幾乎不可能）恰好是整數(shù)或者有限小數(shù)，它們往往是一些根本不能用有限的方式精確表示出來的數(shù)?？紤]到這一點，兩條線段不 可公度完全是有可能的。

    為了讓兩條線段輾轉(zhuǎn)相除永遠除不盡，我們有一種絕妙的構(gòu)造思路：讓線段 a 和 b 的比值恰好等于線段 b 和 c 的比值。這樣，輾轉(zhuǎn)相除一次后，兩數(shù)的關(guān)系又回到了起點。今后每一次輾轉(zhuǎn)相除，余數(shù)總會占據(jù)除數(shù)的某個相同的比例，于是永遠不會出現(xiàn)除盡的情況。不妨假設(shè) 一種最為簡單的情況，即 a 最多只能包含一個 b 的長度，此時 c 等于 a - b 。解方程 a / b = b / (a - b) 可以得到 a : b = 1 : (√5 - 1) / 2 ，約等于一個大家非常熟悉的比值 1: 0.618 。于是我們馬上得出：成黃金比例的兩條線段是不可公度的。

    更典型的例子則是，正方形的邊長和對角線是不可公度的。讓我們畫個圖來說明這一點。如圖，我們試著用輾轉(zhuǎn)相除求出邊長 AB 和對角線 AC 的最大公度單位。按照規(guī)則，第一步我們應(yīng)該用 AB 去度量 AC ，假設(shè)所得的零頭是 EC 。下一步，我們應(yīng)該用 EC 去度量 AB ，或者說用 EC 去度量 BC （反正正方形各邊都相等）。讓我們以 EC 為邊作一個小正方形 CEFG ，容易看出 F 點將正好落在 BC 上，同時三角形 AEF 和三角形 ABF 將會由于 HL 全等。因此， EC = EF = BF 。注意到 BC 上已經(jīng)有一段 BF 和 EC 是相等的了，因而我們用 EC 去度量 BC 所剩的零頭，也就相當于用 EC 去度量 FC 所剩的零頭。結(jié)果又回到了最初的局面——尋找正方形的邊長和對角線的公度單位。因而，輾轉(zhuǎn)相除永遠不會結(jié)束。線段 AB 的長度和線段 AC 的長度不能公度，它們處于兩個不同的世界中。

    如果正方形 ABCD 的邊長 1 ，正方形的面積也就是 1 。從上圖中可以看到，若以對角線 AC 為邊做一個大正方形，它的面積就該是 2 。因而， AC 就應(yīng)該是一個與自身相乘之后恰好等于 2 的數(shù)，我們通常把這個數(shù)記作 √2 ?！稁缀卧尽返牡谑韺ｉT研究不可公度量，其中就有一段 1 和 √2 不可公度的證明，但所用的方法不是我們上面講的這種，而更接近于課本上的證明：設(shè) √2 = p / q ，其中 p / q 已是最簡分數(shù)，但推著推著就發(fā)現(xiàn)，這將意味著 p 和 q 都是偶數(shù)，與最簡分數(shù)的假設(shè)矛盾。

    用今天的話來講， 1 和 √2 不可公度，實際上相當于是說 √2 是無理數(shù)。因此，古希臘人發(fā)現(xiàn)了無理數(shù)，這確實當屬不爭的事實。奇怪的是，無理數(shù)的發(fā)現(xiàn)常常會幾乎毫無根據(jù)地歸功于一個史料記載嚴重不足的古希臘數(shù)學家 Hippasus 。根據(jù)各種不靠譜的描述， Hippasus 的發(fā)現(xiàn)觸犯了 Pythagoras （古希臘哲學家）的教條，最后被溺死在了海里。

    可公度線段和不可公度線段的概念與有理數(shù)和無理數(shù)的概念非常接近，我們甚至可以說明這兩個概念是等價的——它們之間有一種很巧妙的等價關(guān)系。注意到，即使 a 和 b 本身都是無理數(shù)， a 和 b 還是有可能被公度的，例如 a = √2 并且 b = 2 · √2 的時候。不過，有一件事我們可以肯定： a 和 b 的比值一定是一個有理數(shù)。事實上，可以證明，線段 a 和 b 是可公度的，當且僅當 a / b 是一個有理數(shù)。線段 a 和 b 是可公度的，說明存在一個 c 以及兩個整數(shù) m 和 n ，使得 a = m · c ，并且 b = n · c 。于是 a / b = (m · c) / (n · c) = m / n ，這是一個有理數(shù)。反過來，如果 a / b 是一個有理數(shù)，說明存在整數(shù) m 和 n 使得 a / b = m / n ，等式變形后可得 a / m = b / n ，令這個商為 c ，那么 c 就可以作為 a 和 b 的公度單位。

    有時候，“是否可以公度”的說法甚至比“是否有理”更好一些，因為這是一個相對的概念，不是一個絕對的概念。當我們遇到生活當中的某個物理 量時，我們絕不能指著它就說“這是一個有理的量”或者“這是一個無理的量”，我們只能說，以某某某（比如 1 厘米、 1 英寸、 0.2 毫米或者一支鉛筆的長度等等）作為單位來衡量時，這是一個有理的量或者無理的量?？紤]到所選用的單位長度本身也是由另一個物理量定義出來的（比如 1 米被定義為光在真空中 1 秒走過的路程的 1 / 299792458 ），因而在討論一個物理量是否是有理數(shù)時，我們討論的其實是兩個物理量是否可以被公度。

 
（二）中國剩余定理

    如果兩個正整數(shù)的最大公約數(shù)為 1 ，我們就說這兩個數(shù)是互質(zhì)的。這是一個非常重要的概念。如果 a 和 b 互質(zhì)，這就意味著分數(shù) a / b 已經(jīng)不能再約分了，意味著 a × b 的棋盤的對角線不會經(jīng)過中間的任何交叉點，意味著循環(huán)長度分別為 a 和 b 的兩個周期性事件一同上演，則新的循環(huán)長度最短為 a · b 。

    最后一點可能需要一些解釋。讓我們來舉些例子。假如有 1 路和 2 路兩種公交車，其中 1 路車每 6 分鐘一班，2 路車每 8 分鐘一班。如果你剛剛錯過兩路公交車同時出發(fā)的壯景，那么下一次再遇到這樣的事情是多少分鐘之后呢？當然， 6 × 8 = 48 分鐘，這是一個正確的答案，此時 1 路公交車正好是第 8 班， 2 路公交車正好是第 6 班。不過，實際上，在第 24 分鐘就已經(jīng)出現(xiàn)了兩車再次同發(fā)的情況了，此時 1 路車正好是第 4 班， 2 路車正好是第 3 班。但是，如果把例子中的 6 分鐘和 8 分鐘分別改成 4 分鐘和 7 分鐘，那么要想等到兩車再次同發(fā)，等到第 4 × 7 = 28 分鐘是必需的。類似的，假如某一首歌的長度正好是 6 分鐘，另一首歌的長度正好是 8 分鐘，讓兩首歌各自循環(huán)播放， 6 × 8 = 48 分鐘之后你聽到的“合聲”將會重復，但實際上第 24 分鐘就已經(jīng)開始重復了。但若兩首歌的長度分別是 4 分鐘和 7 分鐘，則必需到第 4 × 7 = 28 分鐘之后才有重復，循環(huán)現(xiàn)象不會提前發(fā)生。

    究其原因，其實就是，對于任意兩個數(shù)，兩個數(shù)的乘積一定是它們的一個公倍數(shù)，但若這兩個數(shù)互質(zhì)，則它們的乘積一定是它們的最小公倍數(shù)。事實上，我們還能證明一個更強的結(jié)論： a 和 b 的最大公約數(shù)和最小公倍數(shù)的乘積，一定等于 a 和 b 的乘積。在第四節(jié)中，我們會給出一個證明。

    很多更復雜的數(shù)學現(xiàn)象也都跟互質(zhì)有關(guān)?！秾O子算經(jīng)》卷下第二十六問：“今有物，不知其數(shù)。三、三數(shù)之，剩二；五、五數(shù)之，剩三；七、七數(shù) 之，剩二。問物幾何？答曰：二十三?！狈g過來，就是有一堆東西，三個三個數(shù)余 2 ，五個五個數(shù)余 3 ，七個七個數(shù)余 2 ，問這堆東西有多少個？《孫子算經(jīng)》給出的答案是 23 個。當然，這個問題還有很多其他的解。由于 105 = 3 × 5 × 7 ，因而 105 這個數(shù)被 3 除、被 5 除、被 7 除都能除盡。所以，在 23 的基礎(chǔ)上額外加上一個 105 ，得到的 128 也是滿足要求的解。當然，我們還可以在 23 的基礎(chǔ)上加上 2 個 105 ，加上 3 個 105 ，等等，所得的數(shù)都滿足要求。除了形如 23 + 105n 的數(shù)以外，還有別的解嗎？沒有了。事實上，不管物體總數(shù)除以 3 的余數(shù)、除以 5 的余數(shù)以及除以 7 的余數(shù)分別是多少，在 0 到 104 當中總存在唯一解；在這個解的基礎(chǔ)上再加上 105 的整倍數(shù)后，可以得到其他所有的正整數(shù)解。后人將其表述為“中國剩余定理”：給出 m 個兩兩互質(zhì)的整數(shù)，它們的乘積為 P ；假設(shè)有一個未知數(shù) M ，如果我們已知 M 分別除以這 m 個數(shù)所得的余數(shù)，那么在 0 到 P - 1 的范圍內(nèi)，我們可以唯一地確定這個 M 。這可以看作是 M 的一個特解。其他所有滿足要求的 M ，則正好是那些除以 P 之后余數(shù)等于這個特解的數(shù)。注意，除數(shù)互質(zhì)的條件是必需的，否則結(jié)論就不成立了。比如說，在 0 到 7 的范圍內(nèi)，除以 4 余 1 并且除以 2 也余 1 的數(shù)有 2 個，除以 4 余 1 并且除以 2 余 0 的數(shù)則一個也沒有。

    從某種角度來說，中國剩余定理幾乎是顯然的。讓我們以兩個除數(shù)的情況為例，來說明中國剩余定理背后的直覺吧。假設(shè)兩個除數(shù)分別是 4 和 7 。下表顯示的就是各自然數(shù)除以 4 和除以 7 的余數(shù)情況，其中 x mod y 表示 x 除以 y 的余數(shù)，這個記號后面還會用到。

    i mod 4 的值顯然是以 4 為周期在循環(huán)， i mod 7 的值顯然是以 7 為周期在循環(huán)。由于 4 和 7 是互質(zhì)的，它們的最小公倍數(shù)是 4 × 7 = 28 ，因而 (i mod 4, i mod 7) 的循環(huán)周期是 28 ，不會更短。因此，當 i 從 0 增加到 27 時， (i mod 4, i mod 7) 的值始終沒有出現(xiàn)重復。但是， (i mod 4, i mod 7) 也就只有 4 × 7 = 28 種不同的取值，因而它們正好既無重復又無遺漏地分給了 0 到 27 之間的數(shù)。這說明，每個特定的余數(shù)組合都在前 28 項中出現(xiàn)過，并且都只出現(xiàn)過一次。在此之后，余數(shù)組合將產(chǎn)生長度為 28 的循環(huán)，于是每個特定的余數(shù)組合都將會以 28 為周期重復出現(xiàn)。這正是中國剩余定理的內(nèi)容。

    中國剩余定理有很多漂亮的應(yīng)用，這里我想說一個我最喜歡的。設(shè)想這樣一個場景：總部打算把一份秘密文件發(fā)送給 5 名特工，但直接把文件原封不動地發(fā)給每個人，很難保障安全性。萬一有特工背叛或者被捕，把秘密泄露給了敵人怎么辦？于是就有了電影和小說中經(jīng)常出現(xiàn)的情 節(jié)：把絕密文件拆成 5 份， 5 名特工各自只持有文件的 1/5 。不過，原來的問題并沒有徹底解決，我們只能祈禱壞人竊取到的并不是最關(guān)鍵的文件片段。因此，更好的做法是對原文件進行加密，每名特工只持有密碼的 1/5 ，這 5 名特工需要同時在場才能獲取文件全文。但這也有一個隱患：如果真的有特工被抓了，當壞人們發(fā)現(xiàn)只拿到其中一份密碼沒有任何用處的同時，特工們也會因為少一 份密碼無法解開全文而煩惱。此時，你或許會想，是否有什么辦法能夠讓特工們?nèi)匀豢梢曰謴驮?，即使一部分特工被抓住了？換句話說，有沒有什么密文發(fā)布方 式，使得只要 5 個人中半數(shù)以上的人在場就可以解開絕密文件？這樣的話，壞人必須要能操縱半數(shù)以上的特工才可能對秘密文件造成實質(zhì)性的影響。這種秘密共享方式被稱為 (3, 5) 門限方案，意即 5 個人中至少 3 人在場才能解開密文。

    利用中國剩余定理，我們可以得到一種巧妙的方案。回想中國剩余定理的內(nèi)容：給定 m 個兩兩互質(zhì)的整數(shù)，它們的乘積為 P ；假設(shè)有一個未知數(shù) M ，如果我們已知 M 分別除以這 m 個數(shù)所得的余數(shù)，那么在 0 到 P - 1 的范圍內(nèi)，我們可以唯一地確定這個 M 。我們可以想辦法構(gòu)造這樣一種情況， n 個數(shù)之中任意 m 個的乘積都比 M 大，但是任意 m - 1 個數(shù)的乘積就比 M 小。這樣，任意 m 個除數(shù)就能唯一地確定 M ，但 m - 1 個數(shù)就不足以求出 M 來。 Mignotte 門限方案就用到了這樣一個思路。我們選取 n 個兩兩互質(zhì)的數(shù)，使得最小的 m 個數(shù)的乘積比最大的 m - 1 個數(shù)的乘積還大。例如，在 (3, 5) 門限方案中，我們可以取 53 、 59 、 64 、 67 、 71 這 5 個數(shù)，前面 3 個數(shù)乘起來得 200128 ，而后面兩個數(shù)相乘才得 4757 。我們把文件的密碼設(shè)為一個 4757 和 200128 之間的整數(shù)，比如 123456 。分別算出 123456 除以上面那 5 個數(shù)的余數(shù)，得到 19 、 28 、 0 、 42 、 58 。然后，把 (53, 19) 、 (59, 28) 、 (64, 0) 、 (67, 42) 、 (71, 58) 分別告訴 5 名特工，也就是說特工 1 只知道密碼除以 53 余 19 ，特工 2 只知道密碼除以 59 余 28 ，等等。這樣，根據(jù)中國剩余定理，任意 3 名特工碰頭后就可以唯一地確定出 123456 ，但根據(jù) 2 名特工手中的信息只能得到成百上千個不定解。例如，假設(shè)我們知道了 x 除以 59 余 28 ，也知道了 x 除以 67 余 42 ，那么我們只能確定在 0 和 59 × 67 - 1 之間有一個解 913 ，在 913 的基礎(chǔ)上加上 59 × 67 的整倍數(shù)，可以得到其他滿足要求的 x ，而真正的 M 則可以是其中的任意一個數(shù)。

    不過，為了讓 Mignotte 門限方案真正可行，我們還需要一種根據(jù)余數(shù)信息反推出 M 的方法。換句話說，我們需要有一種通用的方法，能夠回答《孫子算經(jīng)》中提出的那個問題。我們會在下一節(jié)中講到。

 
（三）擴展的輾轉(zhuǎn)相除

    中國剩余定理是一個很基本的定理。很多數(shù)學現(xiàn)象都可以用中國剩余定理來解釋。背九九乘法口訣表時，你或許會發(fā)現(xiàn)，寫下 3 × 1, 3 × 2, ..., 3 × 9 ，它們的個位數(shù)正好遍歷了 1 到 9 所有的情況。 7 的倍數(shù)、 9 的倍數(shù)也是如此，但 2 、 4 、 5 、 6 、 8 就不行。 3 、 7 、 9 這三個數(shù)究竟有什么特別的地方呢？秘密就在于， 3 、 7 、 9 都是和 10 互質(zhì)的。比如說 3 ，由于 3 和 10 是互質(zhì)的，那么根據(jù)中國剩余定理，在 0 到 29 之間一定有這樣一個數(shù)，它除以 3 余 0 ，并且除以 10 余 1 。它將會是 3 的某個整倍數(shù)，并且個位為 1 。同樣的，在 0 到 29 之間也一定有一個 3 的整倍數(shù)，它的個位是 2 ；在 0 到 29 之間也一定有一個 3 的整倍數(shù)，它的個位是 3 ……而在 0 到 29 之間，除掉 0 以外， 3 的整倍數(shù)正好有 9 個，于是它們的末位就正好既無重復又無遺漏地取遍了 1 到 9 所有的數(shù)字。

    這表明，如果 a 和 n 互質(zhì)，那么 a · x mod n = 1 、 a · x mod n = 2 等所有方程都是有解的。 18 世紀的法國數(shù)學家 étienne Bézout 曾經(jīng)證明了一個基本上與此等價的定理，這里我們姑且把它叫做“ Bézout 定理”。事實上，我們不但知道上述方程是有解的，還能求出所有滿足要求的解來。

    我們不妨花點時間，把方程 a · x mod n = b 和中國剩余定理的關(guān)系再理一下。尋找方程 a · x mod n = b 的解，相當于尋找一個 a 的倍數(shù)使得它除以 n 余 b ，或者說是尋找一個數(shù) M 同時滿足 M mod a = 0 且 M mod n = b 。如果 a 和 n 是互質(zhì)的，那么根據(jù)中國剩余定理，這樣的 M 一定存在，并且找到一個這樣的 M 之后，在它的基礎(chǔ)上加減 a · n 的整倍數(shù)，可以得到所有滿足要求的 M 。因此，為了解出方程 a · x mod n = b 的所有解，我們也只需要解出方程的某個特解就行了。假如我們找到了方程 a · x mod n = b 中 x 的一個解，在這個解的基礎(chǔ)上加上或減去 n 的倍數(shù)（相當于在整個被除數(shù) a · x 的基礎(chǔ)上加上或者減去 a · n 的倍數(shù)，這里的 a · x 就是前面所說的 M ），就能得到所有的解了。

    更妙的是，我們其實只需要考慮形如 a · x mod n = 1 的方程。因為，如果能解出這樣的方程， a · x mod n = 2 、 a · x mod n = 3 也都自動地獲解了。假如 a · x mod n = 1 有一個解 x = 100 ，由于 100 個 a 除以 n 余 1 ，自然 200 個 a 除以 n 就余 2 ， 300 個 a 除以 n 就余 3 ，等等，等式右邊余數(shù)不為 1 的方程也都解開了。

    讓我們嘗試求解 115x mod 367 = 1 。注意，由于 115 和 367 是互質(zhì)的，因此方程確實有解。我們解方程的基本思路是，不斷尋找 115 的某個倍數(shù)以及 367 的某個倍數(shù)，使得它們之間的差越來越小，直到最終變?yōu)? 1 。由于 367 除以 115 得 3 ，余 22 ，因而 3 個 115 只比 367 少 22 。于是， 15 個 115 就要比 5 個 367 少 110 ，從而 16 個 115 就會比 5 個 367 多 5 。好了，真正巧妙的就在這里了： 16 個 115 比 5 個 367 多 5 ，但 3 個 115 比 1 個 367 少 22 ，兩者結(jié)合起來，我們便能找到 115 的某個倍數(shù)和 367 的某個倍數(shù)，它們只相差 2 ： 16 個 115 比 5 個 367 多 5 ，說明 64 個 115 比 20 個 367 多 20 ，又考慮到 3 個 115 比 1 個 367 少 22 ，于是 67 個 115 只比 21 個 367 少 2 ?，F(xiàn)在，結(jié)合“少 2 ”和“多 5 ”兩個式子，我們就能把差距縮小到 1 了： 67 個 115 比 21 個 367 少 2 ，說明 134 個 115 比 42 個 367 少 4 ，而 16 個 115 比 5 個 367 多 5 ，于是 150 個 115 比 47 個 367 多 1 。這樣，我們就解出了一個滿足 115x mod 367 = 1 的 x ，即 x = 150 。大家會發(fā)現(xiàn)，在求解過程，我們相當于對 115 和 367 做了一遍輾轉(zhuǎn)相除：我們不斷給出 115 的某個倍數(shù)和 367 的某個倍數(shù)，通過輾轉(zhuǎn)對比最近的兩個結(jié)果，讓它們的差距從“少 22 ”縮小到“多 5 ”，再到“少 2 ”、“多 1 ”，其中 22, 5, 2, 1 這幾個數(shù)正是用輾轉(zhuǎn)相除法求 115 和 367 的最大公約數(shù)時將會經(jīng)歷的數(shù)。因而，算法的步驟數(shù)仍然是對數(shù)級別的，即使面對上百位上千位的大數(shù)，計算機也毫無壓力。這種求解方程 a · x mod n = b 的算法就叫做“擴展的輾轉(zhuǎn)相除法”。

    注意，整個算法有時也會以“少 1 ”的形式告終。例如，用此方法求解 128x mod 367 = 1 時，最后會得出 43 個 128 比 15 個 367 少 1 。這下怎么辦呢？很簡單， 43 個 128 比 15 個 367 少 1 ，但是 367 個 128 顯然等于 128 個 367 ，對比兩個式子可知， 324 個 128 就會比 113 個 367 多 1 了，于是得到 x = 324 。

    最后還有一個問題：我們最終總能到達“多 1 ”或者“少 1 ”，這正是因為一開始的兩個數(shù)是互質(zhì)的。如果方程 a · x mod n = b 當中 a 和 n 不互質(zhì)，它們的最大公約數(shù)是 d > 1 ，那么在 a 和 n 之間做輾轉(zhuǎn)相除時，算到 d 就直接終止了。自然，擴展的輾轉(zhuǎn)相除也將在到達“多 1 ”或者“少 1 ”之前提前結(jié)束。那怎么辦呢？我們有一種巧妙的處理方法：以 d 為單位重新去度量 a 和 n （或者說讓 a 和 n 都除以 d ），問題就變成我們熟悉的情況了。讓我們來舉個例子吧。假如我們要解方程 24 · x mod 42 = 30 ，為了方便后面的解釋，我們來給這個方程編造一個背景：說一盒雞蛋 24 個，那么買多少盒雞蛋，才能讓所有的雞蛋 42 個 42 個地數(shù)最后正好能余 30 個？我們發(fā)現(xiàn) 24 和 42 不是互質(zhì)的，擴展的輾轉(zhuǎn)相除似乎就沒有用了。不過沒關(guān)系。我們找出 24 和 42 的最大公約數(shù)，發(fā)現(xiàn)它們的最大公約數(shù)是 6 ?，F(xiàn)在，讓 24 和 42 都來除以 6 ，分別得到 4 和 7 。由于 6 已經(jīng)是 24 和 42 的公約數(shù)中最大的了，因此把 24 和 42 當中的 6 除掉后，剩下的 4 和 7 就不再有大于 1 的公約數(shù)，從而就是互質(zhì)的了。好了，現(xiàn)在我們把題目改編一下，把每 6 個雞蛋視為一個新的單位量，比如說“ 1 把”。記住， 1 把雞蛋就是 6 個雞蛋。于是，原問題就變成了，每個盒子能裝 4 把雞蛋，那么買多少盒雞蛋，才能讓所有的雞蛋 7 把 7 把地數(shù)，最后正好會余 5 把？于是，方程就變成了 4 · x mod 7 = 5 。由于此時 4 和 7 是互質(zhì)的了，因而套用擴展的輾轉(zhuǎn)相除法，此方程一定有解?？梢越獬鎏亟?x = 3 ，在它的基礎(chǔ)上加減 7 的整倍數(shù)，可以得到其他所有滿足要求的 x 。這就是改編之后的問題的解。但是，雖說我們對原題做了“改編”，題目內(nèi)容本身卻完全沒變，連數(shù)值都沒變，只不過換了一種說法。改編后的題目里需要買 3 盒雞蛋，改編前的題目里當然也是要買 3 盒雞蛋。 x = 3 ，以及所有形如 3 + 7n 的數(shù)，也都是原方程的解。

    大家或許已經(jīng)看到了，我們成功地找到了 24 · x mod 42 = 30 的解，依賴于一個巧合： 24 和 42 的最大公約數(shù) 6 ，正好也是 30 的約數(shù)。因此，改用“把”作單位重新敘述問題，正好最后的“余 30 個”變成了“余 5 把”，依舊是一個整數(shù)。如果原方程是 24 · x mod 42 = 31 的話，我們就沒有那么走運了，問題將變成“買多少盒才能讓最后數(shù)完余 5 又 1/6 把”。這怎么可能呢？我們是整把整把地買，整把整把地數(shù)，當然余數(shù)也是整把整把的。因此，方程 24 · x mod 42 = 31 顯然無解。

    綜上所述，如果關(guān)于 x 的方程 a · x mod n = b 當中的 a 和 n 不互質(zhì)，那么求出 a 和 n 的最大公約數(shù) d 。如果 b 恰好是 d 的整倍數(shù)，那么把方程中的 a 、 n 、 b 全都除以 d ，新的 a 和 n 就互質(zhì)了，新的 b 也恰好為整數(shù)，用擴展的輾轉(zhuǎn)相除求解新方程，得到的解也就是原方程的解。但若 b 不是 d 的整倍數(shù)，則方程無解。

    擴展的輾轉(zhuǎn)相除法有很多應(yīng)用，其中一個有趣的應(yīng)用就是大家小時候肯定見過的“倒水問題”。假如你有一個 3 升的容器和一個 5 升的容器（以及充足的水源），如何精確地取出 4 升的水來？為了敘述簡便，我們不妨把 3 升的容器和 5 升的容器分別記作容器 A 和容器 B 。一種解法如下：

      1. 將 A 裝滿，此時 A 中的水為 3 升， B 中的水為 0 升；
      2. 將 A 里的水全部倒入 B ，此時 A 中的水為 0 升， B 中的水為 3 升；
      3. 將 A 裝滿，此時 A 中的水為 3 升， B 中的水為 3 升；
      4. 將 A 里的水倒入 B 直到把 B 裝滿，此時 A 中的水為 1 升， B 中的水為 5 升；
      5. 將 B 里的水全部倒掉，此時 A 中的水為 1 升， B 中的水為 0 升；
      6. 將 A 里剩余的水全部倒入 B ，此時 A 中的水為 0 升， B 中的水為 1 升；
      7. 將 A 裝滿，此時 A 中的水為 3 升， B 中的水為 1 升；
      8. 將 A 里的水全部倒入 B ，此時 A 中的水為 0 升， B 中的水為 4 升；

    這樣，我們就得到 4 升的水了。顯然，這類問題可以編出無窮多個來，比如能否用 7 升的水杯和 13 升的水杯量出 5 升的水，能否又用 9 升的水杯和 15 升的水杯量出 10 升的水，等等。這樣的問題有什么萬能解法嗎？有！注意到，前面用 3 升的水杯和 5 升的水杯量出 4 升的水，看似復雜的步驟可以簡單地概括為：不斷將整杯整杯的 A 往 B 里倒，期間只要 B 被裝滿就把 B 倒空。由于 3 × 3 mod 5 = 4 ，因而把 3 杯的 A 全部倒進 B 里，并且每裝滿一個 B 就把水倒掉， B 里面正好會剩下 4 升的水。類似地，用容積分別為 a 和 b 的水杯量出體積為 c 的水，實際上相當于解方程 a · x mod b = c 。如果 c 是 a 和 b 的最大公約數(shù)，或者能被它們的最大公約數(shù)整除，用擴展的輾轉(zhuǎn)相除便能求出 x ，得到對應(yīng)的量水方案。特別地，如果兩個水杯的容積互質(zhì)，問題將保證有解。如果 c 不能被 a 和 b 的最大公約數(shù)整除，方程就沒有解了，怎么辦？不用著急，因為很顯然，此時問題正好也沒有解。比方說 9 和 15 都是 3 的倍數(shù)，那我們就把每 3 升的水視作一個單位，于是你會發(fā)現(xiàn)，在 9 升和 15 升之間加加減減，倒來倒去，得到的量永遠只能在 3 的倍數(shù)當中轉(zhuǎn)，絕不可能弄出 10 升的水來。這樣一來，我們就給出了問題有解無解的判斷方法，以及在有解時生成一種合法解的方法，從而完美地解決了倒水問題。

    最后，讓我們把上一節(jié)留下的一點懸念給補完：怎樣求解《孫子算經(jīng)》中的“今有物，不知其數(shù)”一題。已知有一堆東西，三個三個數(shù)余 2 ，五個五個數(shù)余 3 ，七個七個數(shù)余 2 ，問這堆東西有多少個？根據(jù)中國剩余定理，由于除數(shù) 3 、 5 、 7 兩兩互質(zhì)，因而在 0 到 104 之間，該問題有唯一的答案。我們求解的基本思路就是，依次找出滿足每個條件，但是又不會破壞掉其他條件的數(shù)。我們首先要尋找一個數(shù)，它既是 5 的倍數(shù)，又是 7 的倍數(shù)，同時除以 3 正好余 2 。這相當于是在問， 35 的多少倍除以 3 將會余 2 。于是，我們利用擴展的輾轉(zhuǎn)相除法求解方程 35x mod 3 = 2 。這個方程是一定有解的，因為 5 和 3 、 7 和 3 都是互質(zhì)的，從而 5 × 7 和 3 也是互質(zhì)的（到了下一節(jié)，這一點會變得很顯然）。解這個方程可得 x = 1 。于是， 35 就是我們要找到的數(shù)。第二步，是尋找這么一個數(shù)，它既是 3 的倍數(shù)，又是 7 的倍數(shù)，同時除以 5 余 3 。這相當于求解方程 21x mod 5 = 3 ，根據(jù)和剛才相同的道理，這個方程一定有解?？梢越獾?x = 3 ，因此我們要找的數(shù)就是 63 。最后，我們需要尋找一個數(shù)，它能同時被 3 和 5 整除，但被 7 除余 2 。這相當于求解方程 15x mod 7 = 2 ，解得 x = 2 。我們想要找的數(shù)就是 30 ?，F(xiàn)在，如果我們把 35 、 63 和 30 這三個數(shù)加在一起會怎么樣？它將會同時滿足題目當中的三個條件！它滿足“三個三個數(shù)余 2 ”，因為 35 除以 3 是余 2 的，而后面兩個數(shù)都是 3 的整倍數(shù)，所以加在一起后除以 3 仍然余 2 。類似地，它滿足“五個五個數(shù)余 3 ”，因為 63 除以 5 余 3 ，另外兩個數(shù)都是 5 的倍數(shù)。類似地，它也滿足“七個七個數(shù)余 2 ”，因而它就是原問題的一個解。你可以驗證一下， 35 + 63 + 30 = 128 ，它確實滿足題目的所有要求！為了得出一個 0 到 104 之間的解，我們在 128 的基礎(chǔ)上減去一個 105 ，于是正好得到《孫子算經(jīng)》當中給出的答案， 23 。

    已知 M 除以 m 個兩兩互質(zhì)的數(shù)之后所得的余數(shù)，利用類似的方法總能反解出 M 來。至此，我們也就完成了 Mignotte 秘密共享方案的最后一環(huán)。

 
（四）Fermat 小定理

    很多自然數(shù)都可以被分解成一些更小的數(shù)的乘積，例如 12 可以被分成 4 乘以 3 ，其中 4 還可以繼續(xù)地被分成 2 乘以 2 ，因而我們可以把 12 寫作 2 × 2 × 3 。此時， 2 和 3 都不能再繼續(xù)分解了，它們是最基本、最純凈的數(shù)。我們就把這樣的數(shù)叫做“質(zhì)數(shù)”或者“素數(shù)”。同樣地， 2 、 3 、 5 、 7 、 11 、 13 等等都是不可分解的，它們也都是質(zhì)數(shù)。它們是自然數(shù)的構(gòu)件，是自然數(shù)世界的基本元素。 12 是由兩個 2 和一個 3 組成的，正如水分子是由兩個氫原子和一個氧原子組成的一樣。只不過，和化學世界不同的是，自然數(shù)世界里的基本元素是無限的——質(zhì)數(shù)有無窮多個。

    關(guān)于為什么質(zhì)數(shù)有無窮多個，古希臘的 Euclid 有一個非常漂亮的證明。假設(shè)質(zhì)數(shù)只有有限個，其中最大的那個質(zhì)數(shù)為 p ?，F(xiàn)在，把所有的質(zhì)數(shù)全部乘起來，再加上 1 ，得到一個新的數(shù) N 。也就是說， N 等于 2 · 3 · 5 · 7 · … · p + 1 。注意到， N 除以每一個質(zhì)數(shù)都會余 1 ，比如 N 除以 2 就會商 3 · 5 · 7 · … · p 余 1 ， N 除以 3 就會商 2 · 5 · 7 · … · p 余 1 ，等等。這意味著， N 不能被任何一個質(zhì)數(shù)整除，換句話說 N 是不能被分解的，它本身就是質(zhì)數(shù)。然而這也不對，因為 p 已經(jīng)是最大的質(zhì)數(shù)了，于是產(chǎn)生了矛盾。這說明，我們剛開始的假設(shè)是錯的，質(zhì)數(shù)應(yīng)該有無窮多個。需要額外說明的一點是，這個證明容易讓人產(chǎn)生一個誤解，即把 頭 n 個質(zhì)數(shù)乘起來再加 1 ，總能產(chǎn)生一個新的質(zhì)數(shù)。這是不對的，因為既然我們無法把全部質(zhì)數(shù)都乘起來，那么所得的數(shù)就有可能是由那些我們沒有乘進去的質(zhì)數(shù)構(gòu)成的，比如 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 ，它可以被分解成 59 × 509 。

    從古希臘時代開始，人們就近乎瘋狂地想要認識自然數(shù)的本質(zhì)規(guī)律。組成自然數(shù)的基本元素自然地就成為了一個絕佳的突破口，于是對質(zhì)數(shù)的研究成為了探索自然數(shù)世界的一個永久的話題。這就是我們今天所說的“數(shù)論”。

    用質(zhì)數(shù)理論來研究數(shù)，真的會非常方便。 a 是 b 的倍數(shù)（或者說 a 能被 b 整除， b 是 a 的約數(shù)），意思就是 a 擁有 b 所含的每一種質(zhì)數(shù)，而且個數(shù)不會更少。我們舉個例子吧，比如說 b = 12 ，它可以被分解成 2 × 2 × 3 ， a = 180 ，可以被分解成 2 × 2 × 3 × 3 × 5 。 b 里面有兩個 2 ，這不稀罕， a 里面也有兩個 2 ； b 里面有一個 3 ，這也沒什么， a 里面有兩個 3 呢。況且， a 里面還包含有 b 沒有的質(zhì)數(shù)， 5 。對于每一種質(zhì)數(shù)， b 里面所含的個數(shù)都比不過 a ，這其實就表明了 b 就是 a 的約數(shù)。

    現(xiàn)在，假設(shè) a = 36 = 2 × 2 × 3 × 3 ， b = 120 = 2 × 2 × 2 × 3 × 5 。那么， a 和 b 的最大公約數(shù)是多少？我們可以依次考察，最大公約數(shù)里面可以包含哪些質(zhì)數(shù)，每個質(zhì)數(shù)都能有多少個。這個最大公約數(shù)最多可以包含多少個質(zhì)數(shù) 2 ？顯然最多只能包含兩個，否則它就不能整除 a 了；這個最大公約數(shù)最多可以包含多少個質(zhì)數(shù) 3 ？顯然最多只能包含一個，否則它就不能整除 b 了；這個最大公約數(shù)最多可以包含多少個質(zhì)數(shù) 5 ？顯然一個都不能有，否則它就不能整除 a 了。因此， a 和 b 的最大公約數(shù)就是 2 × 2 × 3 = 12 。

    在構(gòu)造 a 和 b 的最小公倍數(shù)時，我們希望每種質(zhì)數(shù)在數(shù)量足夠的前提下越少越好。為了讓這個數(shù)既是 a 的倍數(shù)，又是 b 的倍數(shù)，三個 2 是必需的；為了讓這個數(shù)既是 a 的倍數(shù)，又是 b 的倍數(shù)，兩個 3 是必需的；為了讓這個數(shù)既是 a 的倍數(shù)，又是 b 的倍數(shù)，那一個 5 也是必不可少的。因此， a 和 b 的最小公倍數(shù)就是 2 × 2 × 2 × 3 × 3 × 5 = 360 。

    你會發(fā)現(xiàn)， 12 × 360 = 36 × 120 ，最大公約數(shù)乘以最小公倍數(shù)正好等于原來兩數(shù)的乘積。這其實并不奇怪。在最大公約數(shù)里面，每種質(zhì)數(shù)各有多少個，取決于 a 和 b 當中誰所含的這種質(zhì)數(shù)更少一些。在最小公倍數(shù)里面，每種質(zhì)數(shù)各有多少個，取決于 a 和 b 當中誰所含的這種質(zhì)數(shù)更多一些。因此，對于每一種質(zhì)數(shù)而言，最大公約數(shù)和最小公倍數(shù)里面一共包含了多少個這種質(zhì)數(shù)， a 和 b 里面也就一共包含了多少個這種質(zhì)數(shù)。最大公約數(shù)和最小公倍數(shù)乘在一起，也就相當于是把 a 和 b 各自所包含的質(zhì)數(shù)都乘了個遍，自然也就等于 a 與 b 的乘積了。這立即帶來了我們熟悉的推論：如果兩數(shù)互質(zhì)，這兩數(shù)的乘積就是它們的最小公倍數(shù)。

    第三節(jié)里，我們曾說到，“因為 5 和 3 、 7 和 3 都是互質(zhì)的，從而 5 × 7 和 3 也是互質(zhì)的”。利用質(zhì)數(shù)的觀點，這很容易解釋。兩個數(shù)互質(zhì)，相當于是說這兩個數(shù)不包含任何相同的質(zhì)數(shù)。如果 a 與 c 互質(zhì)， b 與 c 互質(zhì)，顯然 a · b 也與 c 互質(zhì)。另外一個值得注意的結(jié)論是，如果 a 和 b 是兩個不同的質(zhì)數(shù)，則這兩個數(shù)顯然就直接互質(zhì)了。事實上，只要知道了 a 是質(zhì)數(shù)，并且 a 不能整除 b ，那么不管 b 是不是質(zhì)數(shù)，我們也都能確定 a 和 b 是互質(zhì)的。我們后面會用到這些結(jié)論。

    在很多場合中，質(zhì)數(shù)都扮演著重要的角色。 1640 年，法國業(yè)余數(shù)學家 Pierre de Fermat （通常譯作“費馬”）發(fā)現(xiàn)，如果 n 是一個質(zhì)數(shù)的話，那么對于任意一個數(shù) a ， a 的 n 次方減去 a 之后都將是 n 的倍數(shù)。例如， 7 是一個質(zhì)數(shù)，于是 2⁷ - 2 、 3⁷ - 3 ， 4⁷ - 4 ，甚至 100⁷ - 100 ，統(tǒng)統(tǒng)都能被 7 整除。但 15 不是質(zhì)數(shù)（它可以被分解為 3 × 5 ），于是 a¹⁵ - a 除以 15 之后就可能會出現(xiàn)五花八門的余數(shù)了。這個規(guī)律在數(shù)論研究中是如此基本如此重要，以至于它有一個專門的名字—— Fermat 小定理。作為一個業(yè)余數(shù)學家， Fermat 發(fā)現(xiàn)了很多數(shù)論中精彩的結(jié)論， Fermat “小”定理只是其中之一。雖然與本文無關(guān)，但有一點不得不提：以 Fermat 的名字命名的東西里，最著名的要數(shù) Fermat 大定理了（其實譯作“ Fermat 最終定理”更貼切）。如果你沒聽說過，上網(wǎng)查查，或者看看相關(guān)的書籍。千萬不要錯過與此相關(guān)的一系列激動人心的故事。

    言歸正傳。 Fermat 小定理有一個非常精彩的證明。我們不妨以“ 3⁷ - 3 能被 7 整除”為例進行說明，稍后你會發(fā)現(xiàn)，對于其他的情況，道理是一樣的。首先，讓我來解釋一下“循環(huán)移位”的意思。想象一個由若干字符所組成的字符串，在一塊 大小剛好合適的 LED 屏幕上滾動顯示。比方說， HELLOWORLD 就是一個 10 位的字符串，而我們的 LED 屏幕不多不少正好容納 10 個字符。剛開始，屏幕上顯示 HELLOWORLD 。下一刻，屏幕上的字母 H 將會移出屏幕，但又會從屏幕右邊移進來，于是屏幕變成了 ELLOWORLDH 。下一刻，屏幕變成了 LLOWORLDHE ，再下一刻又變成了 LOWORLDHEL 。移動到第 10 次，屏幕又會回到 HELLOWORLD 。在此過程中，屏幕上曾經(jīng)顯示過的 ELLOWORLDH, LLOWORLDHE, LOWORLDHEL, ... ，都是由初始的字符串 HELLOWORLD 通過“循環(huán)移位”得來的?，F(xiàn)在，考慮所有僅由 A 、 B 、 C 三個字符組成的長度為 7 的字符串，它們一共有 3⁷ 個。如果某個字符串循環(huán)移位后可以得到另一個字符串，我們就認為這兩個字符串屬于同一組字符串。比如說， ABBCCCC 和 CCCABBC 就屬于同一組字符串，并且該組內(nèi)還有其他 5 個字符串。于是，在所有 3⁷ 個字符串當中，除了 AAAAAAA 、 BBBBBBB 、 CCCCCCC 這三個特殊的字符串以外，其他所有的字符串正好都是每 7 個一組。這說明， 3⁷ - 3 能被 7 整除。

    在這個證明過程中，“ 7 是質(zhì)數(shù)”這個條件用到哪里去了？仔細想想你會發(fā)現(xiàn)，正因為 7 是質(zhì)數(shù)，所以每一組里才恰好有 7 個字符串。如果字符串的長度不是 7 而是 15 的話，有些組里將會只含 3 個或者 5 個字符串。比方說， ABCABCABCABCABC 所在的組里就只有 3 個字符串，循環(huán)移動 3 個字符后，字符串將會和原來重合。

    Fermat 小定理有一個等價的表述：如果 n 是一個質(zhì)數(shù)的話，那么對于任意一個數(shù) a ，隨著 i 的增加， a 的 i 次方除以 n 的余數(shù)將會呈現(xiàn)出長度為 n - 1 的周期性（下表所示的是 a = 3 、 n = 7 的情況）。這是因為，根據(jù)前面的結(jié)論， aⁿ 與 a 的差能夠被 n 整除，這說明 aⁿ 和 a 分別都除以 n 之后將會擁有相同的余數(shù)。這表明，依次計算 a 的 1 次方、 2 次方、 3 次方除以 n 的余數(shù)，算到 a 的 n 次方時，余數(shù)將會變得和最開始相同。另一方面， aⁱ 除以 n 的余數(shù)，完全由 a^i-1 除以 n 的余數(shù)決定。比方說，假如我們已經(jīng)知道 3³ 除以 7 等于 3 余 6 ，這表明 3³ 里包含 3 個 7 以及 1 個 6 ；因此， 3⁴ 里就包含 9 個 7 以及 3 個 6 ，或者說 9 個 7 以及 1 個 18 。為了得到 3⁴ 除以 7 的余數(shù)，只需要看看 18 除以 7 余多少就行了。可見，要想算出 a^i-1 · a 除以 n 的余數(shù)，我們不需要完整地知道 a^i-1 的值，只需要知道 a^i-1 除以 n 的余數(shù)就可以了。反正最后都要對乘積取余，相乘之前事先對乘數(shù)取余不會對結(jié)果造成影響（記住這一點，后面我們還會多次用到）。既然第 n 個余數(shù)和第 1 個余數(shù)相同，而余數(shù)序列的每一項都由上一項決定，那么第 n + 1 個、第 n + 2 個余數(shù)也都會跟著和第 2 個、第 3 個余數(shù)相同，余數(shù)序列從此處開始重復，形成長為 n - 1 的周期。

    需要注意的是， n - 1 并不見得是最小的周期。下表所示的是 2ⁱ 除以 7 的余數(shù)情況，余數(shù)序列確實存在長度為 6 的周期現(xiàn)象，但實際上它有一個更小的周期， 3 。

    那么，如果除數(shù) n 不是質(zhì)數(shù)，而是兩個質(zhì)數(shù)的乘積（比如 35 ），周期的長度又會怎樣呢？讓我們試著看看， 3ⁱ 除以 35 的余數(shù)有什么規(guī)律吧。注意到 5 和 7 是兩個不同的質(zhì)數(shù)，因而它們是互質(zhì)的。根據(jù)中國剩余定理，一個數(shù)除以 35 的余數(shù)就可以唯一地由它除以 5 的余數(shù)和除以 7 的余數(shù)確定出來。因而，為了研究 3ⁱ 除以 35 的余數(shù)，我們只需要觀察 (3ⁱ mod 5, 3ⁱ mod 7) 即可。由 Fermat 小定理可知，數(shù)列 3ⁱ mod 5 有一個長為 4 的周期，數(shù)列 3ⁱ mod 7 有一個長為 6 的周期。 4 和 6 的最小公倍數(shù)是 12 ，因此 (3ⁱ mod 5, 3ⁱ mod 7) 存在一個長為 12 的周期。到了 i = 13 時， (3ⁱ mod 5, 3ⁱ mod 7) 將會和最開始重復，于是 3ⁱ 除以 35 的余數(shù)將從此處開始發(fā)生循環(huán)。

    類似地，假如某個整數(shù) n 等于兩個質(zhì)數(shù) p 、 q 的乘積，那么對于任意一個整數(shù) a ，寫出 aⁱ 依次除以 n 所得的余數(shù)序列， p - 1 和 q - 1 的最小公倍數(shù)將成為該序列的一個周期。事實上， p - 1 和 q - 1 的任意一個公倍數(shù)，比如表達起來最方便的 (p - 1) × (q - 1) ，也將成為該序列的一個周期。這個規(guī)律可以用來解釋很多數(shù)學現(xiàn)象。例如，大家可能早就注意過，任何一個數(shù)的乘方，其個位數(shù)都會呈現(xiàn)長度為 4 的周期（這包括了周期為 1 和周期為 2 的情況）。其實這就是因為， 10 等于 2 和 5 這兩個質(zhì)數(shù)的乘積，而 (2 - 1) × (5 - 1) = 4，因此任意一個數(shù)的乘方除以 10 的余數(shù)序列都將會產(chǎn)生長為 4 的周期。

    1736 年，瑞士大數(shù)學家 Leonhard Euler （通常譯作“歐拉”）對此做過進一步研究，討論了當 n 是更復雜的數(shù)時推導余數(shù)序列循環(huán)周期的方法，得到了一個非常漂亮的結(jié)果：在 1 到 n 的范圍內(nèi)有多少個數(shù)和 n 互質(zhì)（包括 1 在內(nèi)）， a 的 i 次方除以 n 的余數(shù)序列就會有一個多長的周期。這個經(jīng)典的結(jié)論就叫做“ Euler 定理”。作為歷史上最高產(chǎn)的數(shù)學家之一， Euler 的一生當中發(fā)現(xiàn)的定理實在是太多了。為了把上述定理和其他的“ Euler 定理”區(qū)別開來，有時也稱它為“ Fermat - Euler 定理”。這是一個非常深刻的定理，它有一些非常具有啟發(fā)性的證明方法。考慮到在后文的講解中這個定理不是必需的，因此這里就不詳說了。

    這些東西有什么用呢？沒有什么用。幾千年來，數(shù)論一直沒有任何實際應(yīng)用，數(shù)學家們研究數(shù)論的動力完全來源于數(shù)字本身的魅力。不過，到了 1970 年左右，情況有了戲劇性的變化。

    有的朋友可能要說了，你怎么賴皮呢，“沒有任何實際應(yīng)用”，那剛才的 Mignotte 秘密共享方案算什么？其實， Mignotte 秘密共享方案已經(jīng)是很后來的事了。秘密共享本來遠沒那么復雜，為了使得只要 5 個人中半數(shù)以上的人在場就可以解開絕密文件，總部可以把絕密文件鎖進一個特殊的機械裝置里，裝置上有三個一模一樣的鎖孔，并配有 5 把完全相同且不可復制的鑰匙。只有把其中任意 3 把鑰匙同時插進鑰匙孔并一起轉(zhuǎn)動，才能打開整個裝置。把 5 把鑰匙分發(fā)給 5 名特工，目的就直接達到了。因而，通常情況下我們并不需要動用 Mignotte 秘密共享方案。那么，利用中國剩余定理費盡周折弄出的 Mignotte 秘密共享方案，意義究竟何在呢？這種新的秘密共享方案直到 1983 年才被提出，想必是為了解決某個以前不曾有過的需求。 20 世紀中后期究竟出現(xiàn)了什么？答案便是——計算機網(wǎng)絡(luò)。鎖孔方案只適用于物理世界，不能用于網(wǎng)絡(luò)世界。為了在網(wǎng)絡(luò)世界中共享秘密，我們需要一種純信息層面 的、只涉及數(shù)據(jù)交換的新方法， Mignotte 秘密共享方案才應(yīng)運而生。

    數(shù)論知識開始煥發(fā)新生，一切都是因為這該死的計算機網(wǎng)絡(luò)。

 
（五）公鑰加密的可能性

    計算機網(wǎng)絡(luò)的出現(xiàn)無疑降低了交流的成本，但卻給信息安全帶來了難題。在計算機網(wǎng)絡(luò)中，一切都是數(shù)據(jù)，一切都是數(shù)字，一切都是透明的。假如你 的朋友要給你發(fā)送一份絕密文件，你如何阻止第三者在你們的通信線路的中間節(jié)點上竊走信息？其中一種方法就是，讓他對發(fā)送的數(shù)據(jù)進行加密，密碼只有你們兩人 知道。但是，這個密碼又是怎么商定出來的呢？直接叫對方編好密碼發(fā)給你的話，密碼本身會有泄漏的風險；如果讓對方給密碼加個密再發(fā)過來呢，給密碼加密的方 式仍然不知道該怎么確定。如果是朋友之間的通信，把兩人已知的小秘密用作密鑰（例如約定密鑰為 A 的生日加上 B 的手機號）或許能讓人放心許多；但對于很多更常見的情形，比方說用戶在郵件服務(wù)提供商首次申請郵箱時，會話雙方完全沒有任何可以利用的公共秘密。此時，我 們需要一個絕對邪的辦法……如果說我不告訴任何人解密的算法呢？這樣的話，我就可以公開加密的方法，任何人都能夠按照這種方法對信息進行加密，但是只有我 自己才知道怎樣給由此得到的密文解密。然后，讓對方用這種方法給文件加密傳過來，問題不就解決了嗎？這聽上去似乎不太可能，因為直覺上，知道加密的方法也 就知道了解密的方法，只需要把過程反過來做就行了。加密算法和解密算法有可能是不對稱的嗎？

    有可能。小時候我經(jīng)常在朋友之間表演這么一個數(shù)學小魔術(shù)：讓對方任意想一個三位數(shù)，把這個三位數(shù)乘以 91 的乘積的末三位告訴我，我便能猜出對方原來想的數(shù)是多少。如果對方心里想的數(shù)是 123 ，那么對方就計算出 123 × 91 等于 11193 ，并把結(jié)果的末三位 193 告訴我?？雌饋?，這么做似乎損失了不少信息，讓我沒法反推出原來的數(shù)。不過，我仍然有辦法：只需要把對方告訴我的結(jié)果再乘以 11 ，乘積的末三位就是對方剛開始想的數(shù)了。你可以驗證一下， 193 × 11 = 2123 ，末三位正是對方所想的秘密數(shù)字！其實道理很簡單， 91 乘以 11 等于 1001 ，而任何一個三位數(shù)乘以 1001 后，末三位顯然都不變（例如 123 乘以 1001 就等于 123123 ）。先讓對方在他所想的數(shù)上乘以 91 ，假設(shè)乘積為 X ；我再在 X 的基礎(chǔ)上乘以 11 ，其結(jié)果相當于我倆合作把原數(shù)乘以了 1001 ，自然末三位又變了回去。然而， X 乘以 11 后的末三位是什么，只與 X 的末三位有關(guān)。因此，對方只需要告訴我 X 的末三位就行了，這并不會丟掉信息。站在數(shù)論的角度來看，上面這句話有一個更好的解釋：反正最后都要取除以 1000 的余數(shù)，在中途取一次余數(shù)不會有影響（還記得嗎，“反正最后都要對乘積取余，相乘之前事先對乘數(shù)取余不會對結(jié)果造成影響”）。知道原理后，我們可以構(gòu)造一 個定義域和值域更大的加密解密系統(tǒng)。比方說，任意一個數(shù)乘以 500000001 后，末 8 位都不變，而 500000001 = 42269 × 11829 ，于是你來乘以 42269 ，我來乘以 11829 ，又一個加密解密不對稱的系統(tǒng)就構(gòu)造好了。這是一件很酷的事情，任何人都可以按照我的方法加密一個數(shù)，但是只有我才知道怎么把所得的密文變回去。在現(xiàn)代密 碼學中，數(shù)論漸漸地開始有了自己的地位。

    不過，加密和解密的過程不對稱，并不妨礙我們根據(jù)加密方法推出解密方法來，雖然這可能得費些功夫。比方說，剛才的加密算法就能被破解：猜出 對方心里想的數(shù)相當于求解形如 91x mod 1000 = 193 的方程，這可以利用擴展的輾轉(zhuǎn)相除法很快求解出來，根本不需要其他的雕蟲小技（注意到 91 和 1000 是互質(zhì)的，根據(jù) Bézout 定理，方程確實保證有解）。為了得到一個可以公開加密鑰匙的算法，我們還需要從理論上說服自己，在只知道加密鑰匙的情況下構(gòu)造出解密鑰匙是非常非常困難 的。

    1970 年左右，科學家們開始認真地思考“公鑰加密系統(tǒng)”的可能性。 1977 年，來自 MIT 的 Ron Rivest 、 Adi Shamir 和 Leonard Adleman 三個人合寫了一篇論文，給出了一種至今仍然安全的公鑰加密算法。隨后，該算法以三人名字的首字母命名，即 RSA 算法。

    RSA 算法為什么會更加安全呢？因為 RSA 算法用到了一種非常犀利的不對稱性——大數(shù)分解難題。

    為了判斷一個數(shù)是不是質(zhì)數(shù)，最笨的方法就是試除法——看它能不能被 2 整除，如果不能的話再看它能不能被 3 整除，這樣不斷試除上去。直到除遍了所有比它小的數(shù)，都還不能把它分解開來，它就是質(zhì)數(shù)了。但是，試除法的速度太慢了，我們需要一些高效的方法。 Fermat 素性測試就是一種比較常用的高效方法，它基于如下原理： Fermat 小定理對一切質(zhì)數(shù)都成立?；叵?Fermat 小定理的內(nèi)容：如果 n 是一個質(zhì)數(shù)的話，那么對于任意一個數(shù) a ， a 的 n 次方減去 a 之后都將是 n 的倍數(shù)。為了判斷 209 是不是質(zhì)數(shù)，我們隨便選取一個 a ，比如 38 。結(jié)果發(fā)現(xiàn)，38²⁰⁹ - 38 除以 209 余 114 （稍后我們會看到，即使把 209 換成上百位的大數(shù)，利用計算機也能很快算出這個余數(shù)來），不能被 209 整除。于是， 209 肯定不是質(zhì)數(shù)。我們再舉一個例子。為了判斷 221 是不是質(zhì)數(shù)，我們隨機選擇 a ，比如說還是 38 吧。你會發(fā)現(xiàn) 38²²¹ - 38 除以 221 正好除盡。那么， 221 是否就一定是質(zhì)數(shù)了呢？麻煩就麻煩在這里：這并不能告訴我們 221 是質(zhì)數(shù)，因為 Fermat 小定理畢竟只說了對一切質(zhì)數(shù)都成立，但沒說對其他的數(shù)成不成立。萬一 221 根本就不是質(zhì)數(shù)，但 a = 38 時碰巧也符合 Fermat 小定理呢？為了保險起見，我們不妨再選一個不同的 a 值。比方說，令 a = 26 ，可以算出 26²²¹ - 26 除以 221 余 169 ，因而 221 果然并不是質(zhì)數(shù)。這個例子告訴了我們，如果運氣不好的話，所選的 a 值會讓不是質(zhì)數(shù)的數(shù)也能騙過檢測，雖然這個概率其實并不大。因此，我們通常的做法便是，多選幾個不同的 a ，只要有一次沒通過測試，被檢測的數(shù)一定不是質(zhì)數(shù)，如果都通過測試了，則被檢測的數(shù)很可能是質(zhì)數(shù)。沒錯， Fermat 素性測試的效率非常高，但它是基于一定概率的，有誤報的可能。如果發(fā)現(xiàn)某個數(shù) n 不滿足 Fermat 小定理，它一定不是質(zhì)數(shù)；但如果發(fā)現(xiàn)某個數(shù) n 總能通過 Fermat 小定理的檢驗，只能說明它有很大的幾率是質(zhì)數(shù)。

    Fermat 素性測試真正麻煩的地方就是，居然有這么一種極其特殊的數(shù)，它不是質(zhì)數(shù)，但對于任意的 a 值，它都能通過測試。這樣的數(shù)叫做 Carmichael 數(shù)，最小的一個是 561 ，接下來的幾個則是 1105, 1729, 2465, 2821, 6601, 8911… 雖然不多，但很致命。因此，在實際應(yīng)用時，我們通常會選用 Miller-Rabin 素性測試算法。這個算法以 Gary Miller 的研究成果為基礎(chǔ)，由 Michael Rabin 提出，時間大約是 1975 年。它可以看作是對 Fermat 素性測試的改良。如果選用了 k 個不同的 a 值，那么 Miller-Rabin 素性測試算法出現(xiàn)誤判的概率不會超過 1 / 4^k ，足以應(yīng)付很多現(xiàn)實需要了。

    有沒有什么高效率的、確定性的質(zhì)數(shù)判定算法呢？有，不過這已經(jīng)是很后來的事情了。 2002 年， Manindra Agrawal 、 Neeraj Kayal 和 Nitin Saxena 發(fā)表了一篇重要的論文 PRIMES is in P ，給出了第一個高效判斷質(zhì)數(shù)的確定性算法，并以三人名字的首字母命名，叫做 AKS 素性測試。不過，已有的質(zhì)數(shù)判斷算法已經(jīng)做得很好了，因此對于 AKS 來說，更重要的是它的理論意義。

    有了判斷質(zhì)數(shù)的算法，要想生成一個很大的質(zhì)數(shù)也并不困難了。一種常見的做法是，先選定一串連續(xù)的大數(shù)，然后去掉其中所有能被 2 整除的數(shù)，再去掉所有能被 3 整除的數(shù)，再去掉所有能被 5 整除的數(shù)……直到把某個范圍內(nèi)（比如說 65000 以內(nèi)）的所有質(zhì)數(shù)的倍數(shù)全都去掉。剩下的數(shù)就不多了，利用判斷質(zhì)數(shù)的算法對它們一一進行測試，不久便能找出一個質(zhì)數(shù)來。

    怪就怪在，我們可以高效地判斷一個數(shù)是不是質(zhì)數(shù)，我們可以高效地生成一個很大的質(zhì)數(shù)，但我們卻始終找不到高效的大數(shù)分解方法。任意選兩個比 較大的質(zhì)數(shù)，比如 19394489 和 27687937 。我們能夠很容易計算出 19394489 乘以 27687937 的結(jié)果，它等于 536993389579193 ；但是，除了試除法以外，目前還沒有什么本質(zhì)上更有效的方法（也很難找到更有效的方法）能夠把 536993389579193 迅速分解成 19394489 乘以 27687937 。這種不對稱性很快便成了現(xiàn)代密碼學的重要基礎(chǔ)。讓我們通過一個有趣的例子來看看，大數(shù)分解的困難性是如何派上用場的吧。

    假如你和朋友用短信吵架，最后決定拋擲硬幣來分勝負，正面表示你獲勝，反面表示對方獲勝。問題來了——兩個人如何通過短信公平地拋擲一枚硬 幣？你可以讓對方真的拋擲一枚硬幣，然后將結(jié)果告訴你，不過前提是，你必須充分信任對方才行。在雙方互不信任的情況下，還有辦法模擬一枚虛擬硬幣嗎？在我 們生活中，有一個常見的解決方法：考你一道題，比如“明天是否會下雨”、“地球的半徑是多少”或者“《新華字典》第 307 頁的第一個字是什么”，猜對了就算你贏，猜錯了就算你輸。不過，上面提到的幾個問題顯然都不是完全公平的。我們需要一類能快速生成的、很難出現(xiàn)重復的、解 答不具技巧性的、猜對猜錯幾率均等的、具有一個確鑿的答案并且知道答案后很容易驗證答案正確性的問題。大數(shù)分解為我們構(gòu)造難題提供了一個模板。比方說，讓 對方選擇兩個 90 位的大質(zhì)數(shù)，或者三個 60 位的大質(zhì)數(shù)，然后把乘積告訴你。無論是哪種情況，你都會得到一個大約有 180 位的數(shù)。你需要猜測這個數(shù)究竟是兩個質(zhì)數(shù)乘在一起得來的，還是三個質(zhì)數(shù)乘在一起得來的。猜對了就算正面，你贏；猜錯了就算反面，對方贏。宣布你的猜測后， 讓對方公開他原先想的那兩個數(shù)或者三個數(shù)，由你來檢查它們是否確實都是質(zhì)數(shù)，乘起來是否等于之前給你的數(shù)。

    大數(shù)分解難題成為了 RSA 算法的理論基礎(chǔ)。

 
（六）RSA 算法

    所有工作都準備就緒，下面我們可以開始描述 RSA 算法了。

    首先，找兩個質(zhì)數(shù)，比如說 13 和 17 。實際使用時，我們會選取大得多的質(zhì)數(shù)。把它們乘在一起，得 221 。再計算出 (13 - 1) × (17 - 1) = 192。根據(jù)前面的結(jié)論，任選一個數(shù) a ，它的 i 次方除以 221 的余數(shù)將會呈現(xiàn)長度為 192 的周期（雖然可能存在更短的周期）。換句話說，對于任意的一個 a，a, a¹⁹³, a³⁸⁵, a⁵⁷⁷, ... 除以 221 都擁有相同的余數(shù)。注意到， 385 可以寫成 11 × 35 ……嘿嘿，這下我們就又能變數(shù)學小魔術(shù)了。叫一個人隨便想一個不超過 221 的數(shù)，比如 123 。算出 123 的 11 次方除以 221 的余數(shù)，把結(jié)果告訴你。如果他的計算是正確的，你將會得到 115 這個數(shù)?？瓷先?，我們似乎很難把 115 還原回去，但實際上，你只需要計算 115 的 35 次方，它除以 221 的余數(shù)就會變回 123 。這是因為，對方把他所想的數(shù) 123 連乘了 11 次，得到了一個數(shù) X ；你再把這個 X 乘以自身 35 次，這相當于你們合作把 123 連乘了 385 次，根據(jù)周期性現(xiàn)象，它除以 221 的余數(shù)仍然是 123 。然而，計算 35 個 X 連乘時，反正我們要取乘積除以 221 的余數(shù)，因此我們不必完整地獲知 X 的值，只需要知道 X 除以 221 的余數(shù)就夠了。因而，讓對方只告訴你 X 取余后的結(jié)果，不會造成信息的丟失。

    不過這一次，只知道加密方法后，構(gòu)造解密方法就難了。容易看出， 35 之所以能作為解密的鑰匙，是因為 11 乘以 35 的結(jié)果在數(shù)列 193, 385, 577, ... 當中，它除以 192 的余數(shù)正好是 1 。因此，攻擊者可以求解 11x mod 192 = 1 ，找出滿足要求的密鑰 x 。但關(guān)鍵是，他怎么知道 192 這個數(shù)？要想得到 192 這個數(shù)，我們需要把 221 分解成 13 和 17 的乘積。當最初所選的質(zhì)數(shù)非常非常大時，這一點是很難辦到的。

    根據(jù)這個原理，我們可以選擇兩個充分大的質(zhì)數(shù) p 和 q ，并算出 n = p · q 。接下來，算出 m = (p - 1)(q - 1) 。最后，找出兩個數(shù) e 和 d ，使得 e 乘以 d 的結(jié)果除以 m 余 1 。怎么找到這樣的一對 e 和 d 呢？很簡單。首先，隨便找一個和 m 互質(zhì)的數(shù)（這是可以做到的，比方說，可以不斷生成小于 m 的質(zhì)數(shù)，直到找到一個不能整除 m 的為止），把它用作我們的 e 。然后，求解關(guān)于 d 的方程 e · d mod m = 1（就像剛才攻擊者想要做的那樣，只不過我們有 m 的值而他沒有）。 Bézout 定理將保證這樣的 d 一定存在。

    好了，現(xiàn)在， e 和 n 就可以作為加密鑰匙公之于眾， d 和 n 則是只有自己知道的解密鑰匙。因而，加密鑰匙有時也被稱作公鑰，解密鑰匙有時也被稱作私鑰。任何知道公鑰的人都可以利用公式 c = a^e mod n 把原始數(shù)據(jù) a 加密成一個新的數(shù) c ；私鑰的持有者則可以計算 c^d mod n ，恢復出原始數(shù)據(jù) a 來。不過這里還有個大問題： e 和 d 都是上百位的大數(shù)，怎么才能算出一個數(shù)的 e 次方或者一個數(shù)的 d 次方呢？顯然不能老老實實地算那么多次乘法，不然效率實在太低了。好在，“反復平方”可以幫我們快速計算出一個數(shù)的乘方。比方說，計算 a³⁵ 相當于計算 a³⁴ · a ，也即 (a¹⁷)² · a ，也即 (a¹⁶ · a)² · a，也即 ((a⁸)² · a)² · a……最終簡化為 ((((a²)²)²)² · a)² · a ，因而 7 次乘法操作就夠了。在簡化的過程中， a 的指數(shù)以成半的速度遞減，因而在最后的式子當中，所需的乘法次數(shù)也是對數(shù)級別的，計算機完全能夠承受。不過，減少了運算的次數(shù)，并沒有減小數(shù)的大小。 a 已經(jīng)是一個數(shù)十位上百位的大數(shù)了，再拿 a 和它自己多乘幾次，很快就會變成一個計算機內(nèi)存無法容納的超級大數(shù)。怎么辦呢？別忘了，“反正最后都要對乘積取余，相乘之前事先對乘數(shù)取余不會對結(jié)果造成 影響”，因此我們可以在運算過程中邊算邊取余，每做一次乘法都只取乘積除以 n 的余數(shù)。這樣一來，我們的每次乘法都是兩個 n 以內(nèi)的數(shù)相乘了。利用這些小竅門，計算機才能在足夠短的時間里完成 RSA 加密解密的過程。

    RSA 算法實施起來速度較慢，因此在運算速度上的任何一點優(yōu)化都是有益的。利用中國剩余定理，我們還能進一步加快運算速度。我們想要求的是 a³⁵ 除以 n 的余數(shù)，而 n 是兩個質(zhì)數(shù) p 和 q 的乘積。由于 p 和 q 都是質(zhì)數(shù)，它們顯然也就互質(zhì)了。因而，如果我們知道 a³⁵ 分別除以 p 和 q 的余數(shù)，也就能夠反推出它除以 n 的余數(shù)了。因此，在反復平方的過程中，我們只需要保留所得的結(jié)果除以 p 的余數(shù)和除以 q 的余數(shù)即可，運算時的數(shù)字規(guī)模進一步降低到了 p 和 q 所在的數(shù)量級上。到最后，我們再借助“今有物，不知其數(shù)”的求解思路，把這兩條余數(shù)信息恢復成一個 n 以內(nèi)的數(shù)。更神的是，別忘了， aⁱ 除以 p 的余數(shù)是以 p - 1 為周期的，因此為了計算 a³⁵ mod p ，我們只需要計算 a^{35 mod (p-1)} mod p 就可以了。類似地，由于余數(shù)的周期性現(xiàn)象，計算 a³⁵ mod q 就相當于計算 a^{35 mod (q-1)} mod q 。這樣一來，連指數(shù)的數(shù)量級也減小到了和 p 、 q 相同的水平， RSA 運算的速度會有明顯的提升。

    需要注意的是， RSA 算法的安全性并不完全等價于大數(shù)分解的困難性（至少目前我們還沒有證明這一點）。已知 n 和 e 之后，不分解 n 確實很難求出 d 來。但我們并不能排除，有某種非常巧妙的方法可以繞過大數(shù)分解，不去求 p 和 q 的值，甚至不去求 m 的值，而直接求出一個滿足要求的 d 來。不過，即使考慮到這一點，目前人們也沒有破解密鑰 d 的好辦法。 RSA 算法經(jīng)受住了實踐的考驗，并逐漸成為了行業(yè)標準。如果 A 、 B 兩個人想要建立會話，那么我們可以讓 A 先向 B 索要公鑰，然后想一個兩人今后通話用的密碼，用 B 的公鑰加密后傳給 B ，這將只能由 B 解開。因此，即使竊聽者完全掌握了雙方約定密碼時傳遞的信息，也無法推出這個密碼是多少來。

    上述方案讓雙方在不安全的通信線路上神奇地約定好了密碼，一切看上去似乎都很完美了。然而，在這個漂亮的解決方案背后，有一個讓人意想不到 的、頗有些喜劇色彩的漏洞——中間人攻擊。在 A 、 B 兩人建立會話的過程中，攻擊者很容易在線路中間操縱信息，讓 A 、 B 兩人誤以為他們是在直接對話。讓我們來看看這具體是如何操作的吧。建立會話時， A 首先呼叫 B 并索要 B 的公鑰，此時攻擊者注意到了這個消息。當 B 將公鑰回傳給 A 時，攻擊者截獲 B 的公鑰，然后把他自己的公鑰傳給 A 。接下來， A 隨便想一個密碼，比如說 314159 ，然后用他所收到的公鑰進行加密，并將加密后的結(jié)果傳給 B 。 A 以為自己加密時用的是 B 的公鑰，但他其實用的是攻擊者的公鑰。攻擊者截獲 A 傳出來的信息，用自己的私鑰解出 314159 ，再把 314159 用 B 的公鑰加密后傳給 B 。 B 收到信息后不會發(fā)現(xiàn)什么異樣，因為這段信息確實能用 B 的私鑰解開，而且確實能解出正確的信息 314159 。今后， A 、 B 將會用 314159 作為密碼進行通話，而完全不知道有攻擊者已經(jīng)掌握了密碼。

    怎么封住這個漏洞呢？我們得想辦法建立一個獲取對方公鑰的可信渠道。一個簡單而有效的辦法就是，建立一個所有人都信任的權(quán)威機構(gòu)，由該權(quán)威 機構(gòu)來儲存并分發(fā)大家的公鑰。這就是我們通常所說的數(shù)字證書認證機構(gòu)，英文是 Certificate Authority ，通常簡稱 CA 。任何人都可以申請把自己的公鑰放到 CA 上去，不過 CA 必須親自檢查申請者是否符合資格。如果 A 想要和 B 建立會話，那么 A 就直接從 CA 處獲取 B 的公鑰，這樣就不用擔心得到的是假的公鑰了。

    新的問題又出來了：那么，怎么防止攻擊者冒充 CA 呢？ CA 不但需要向 A 保證“這個公鑰確實是 B 的”，還要向 A 證明“我確實就是 CA ”。

    把加密鑰匙和解密鑰匙稱作“公鑰”和“私鑰”是有原因的——有時候，私鑰也可以用來加密，公鑰也可以用來解密。容易看出，既然 a 的 e 次方的 d 次方除以 n 的余數(shù)就回到了 a ，那么當然， a 的 d 次方的 e 次方除以 n 的余數(shù)也會變回 a 。于是，我們可以讓私鑰的持有者計算 a 的 d 次方除以 n 的余數(shù)，對原文 a 進行加密；然后公鑰的持有者取加密結(jié)果的 e 次方除以 n 的余數(shù)，這也能恢復出原文 a 。但是，用我自己的私鑰加密，然后大家都可以解密，這有什么用處呢？不妨來看看這樣“加密”后的效果吧：第一，貌似是最荒謬的，大家都可以用我的公鑰解出 它所對應(yīng)的原始文件；第二，很關(guān)鍵的，大家只能查看它背后的原文件，不能越過它去修改它背后的原文件；第三，這樣的東西是別人做不出來的，只有我能做出 來。

    這些性質(zhì)正好完美地描述出“數(shù)字簽名”的實質(zhì)，剛才的 CA 難題迎刃而解。 CA 首先生成一個自己的公鑰私鑰對，然后把公鑰公之于眾。之后， CA 對每條發(fā)出去的消息都用自己的私鑰加個密作為簽名，以證明此消息的來源是真實的。收到 CA 的消息后，用 CA 的公鑰進行解密，如果能恢復出 CA 的原文，則說明對方一定是正宗的 CA 。因為，這樣的消息只有私鑰的持有者才能做出來，它上面的簽名是別人無法偽造的。至此為止，建立安全的通信線路終于算是有了一個比較完美的方案。

    實際應(yīng)用中，建立完善的安全機制更加復雜。并且，這還不足以解決很多其他形式的網(wǎng)絡(luò)安全問題。隨便哪個簡單的社交活動，都包含著非常豐富的 協(xié)議內(nèi)涵，在互聯(lián)網(wǎng)上實現(xiàn)起來并不容易。比方說，如何建立一個網(wǎng)絡(luò)投票機制？這里面的含義太多了：我們需要保證每張選票確實都來自符合資格的投票人，我們 需要保證每個投票人只投了一票，我們需要保證投票人的選票內(nèi)容不會被泄露，我們需要保證投票人的選票內(nèi)容不會被篡改，我們還需要讓唱票環(huán)節(jié)足夠透明，讓每 個投票人都確信自己的票被算了進去。作為密碼學與協(xié)議領(lǐng)域的基本模塊， RSA 算法隨時準備上陣。古希臘數(shù)學家對數(shù)字執(zhí)著的研究，直到今天也仍然綻放著光彩。