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

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

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

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

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

 
 
（一）可公度線段

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 
（二）中國(guó)剩余定理

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

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

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

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

    從某種角度來(lái)說(shuō)，中國(guó)剩余定理幾乎是顯然的。讓我們以?xún)蓚€(gè)除數(shù)的情況為例，來(lái)說(shuō)明中國(guó)剩余定理背后的直覺(jué)吧。假設(shè)兩個(gè)除數(shù)分別是 4 和 7 。下表顯示的就是各自然數(shù)除以 4 和除以 7 的余數(shù)情況，其中 x mod y 表示 x 除以 y 的余數(shù)，這個(gè)記號(hào)后面還會(huì)用到。

    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 ，不會(huì)更短。因此，當(dāng) i 從 0 增加到 27 時(shí)， (i mod 4, i mod 7) 的值始終沒(méi)有出現(xiàn)重復(fù)。但是， (i mod 4, i mod 7) 也就只有 4 × 7 = 28 種不同的取值，因而它們正好既無(wú)重復(fù)又無(wú)遺漏地分給了 0 到 27 之間的數(shù)。這說(shuō)明，每個(gè)特定的余數(shù)組合都在前 28 項(xiàng)中出現(xiàn)過(guò)，并且都只出現(xiàn)過(guò)一次。在此之后，余數(shù)組合將產(chǎn)生長(zhǎng)度為 28 的循環(huán)，于是每個(gè)特定的余數(shù)組合都將會(huì)以 28 為周期重復(fù)出現(xiàn)。這正是中國(guó)剩余定理的內(nèi)容。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 
（四）Fermat 小定理

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

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

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

    用質(zhì)數(shù)理論來(lái)研究數(shù)，真的會(huì)非常方便。 a 是 b 的倍數(shù)（或者說(shuō) a 能被 b 整除， b 是 a 的約數(shù)），意思就是 a 擁有 b 所含的每一種質(zhì)數(shù)，而且個(gè)數(shù)不會(huì)更少。我們舉個(gè)例子吧，比如說(shuō) b = 12 ，它可以被分解成 2 × 2 × 3 ， a = 180 ，可以被分解成 2 × 2 × 3 × 3 × 5 。 b 里面有兩個(gè) 2 ，這不稀罕， a 里面也有兩個(gè) 2 ； b 里面有一個(gè) 3 ，這也沒(méi)什么， a 里面有兩個(gè) 3 呢。況且， a 里面還包含有 b 沒(méi)有的質(zhì)數(shù)， 5 。對(duì)于每一種質(zhì)數(shù)， b 里面所含的個(gè)數(shù)都比不過(guò) a ，這其實(shí)就表明了 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ù)，每個(gè)質(zhì)數(shù)都能有多少個(gè)。這個(gè)最大公約數(shù)最多可以包含多少個(gè)質(zhì)數(shù) 2 ？顯然最多只能包含兩個(gè)，否則它就不能整除 a 了；這個(gè)最大公約數(shù)最多可以包含多少個(gè)質(zhì)數(shù) 3 ？顯然最多只能包含一個(gè)，否則它就不能整除 b 了；這個(gè)最大公約數(shù)最多可以包含多少個(gè)質(zhì)數(shù) 5 ？顯然一個(gè)都不能有，否則它就不能整除 a 了。因此， a 和 b 的最大公約數(shù)就是 2 × 2 × 3 = 12 。

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

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

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

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

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

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

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

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

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

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

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

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

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

    數(shù)論知識(shí)開(kāi)始煥發(fā)新生，一切都是因?yàn)檫@該死的計(jì)算機(jī)網(wǎng)絡(luò)。

 
（五）公鑰加密的可能性

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

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

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

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

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

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

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

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

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

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

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

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

 
（六）RSA 算法

    所有工作都準(zhǔn)備就緒，下面我們可以開(kāi)始描述 RSA 算法了。

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

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

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

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

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

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

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

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

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

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

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

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