跨越千年的rsa演算法
數論，數學中的皇冠，最純粹的數學。早在古希臘時代，人們就開始痴迷地研究數字，沉浸於這個幾乎沒有任何實用價值的思維遊戲中。直到計算機誕生之後，幾千年來的數論研究成果突然有了實際的應用，這個過程可以說是最為激動人心的數學話題之一。
最近我在《程式設計師》雜誌上**了《跨越千年的 rsa 演算法》，但受篇幅限制，只有一萬字左右的內容。其實，從數論到 rsa 演算法，裡面的數學之美**是一萬字能扯完的？在寫作的過程中，我查了很多資料，找到了很多漂亮的例子，也積累了很多個人的思考，但最終都因為篇幅原因沒有加進《程式設計師》的文章中。
今天，我想重新梳理一下線索，把所有值得分享的內容一次性地呈現在這篇長文中，希望大家會有所收穫。需要注意的是，本文有意為了照顧可讀性而犧牲了嚴謹性。很多具體內容都僅作了直觀解釋，一些「顯然如此」的細節實際上是需要證明的。
如果你希望看到有關定理及其證明的嚴格表述，可以參見任意一本初等數論的書。把本文作為初等數論的學習讀物是非常危險的。最後，希望大家能夠積極指出文章中的缺陷，我會不斷地做出修改。
*****== 更新記錄 *****==
2012 年 12 月 15 日：發布全文。
2012 年 12 月 18 日：修改了幾處表達。
*****=== 目錄 *****===
（一）可公度線段
（二）中國剩餘定理
（三）擴充套件的輾轉相除
（四）fermat 小定理
（五）公鑰加密的可能性
（六）rsa 演算法
（一）可公度線段
euclid ，中文譯作「歐幾里得」，古希臘數學家。他用公理化系統的方法歸納整理了當時的幾何理論，並寫成了偉大的數學著作《幾何原本》，因而被後人稱作「幾何學之父」。有趣的是，《幾何原本》一書裡並不全講的幾何。
全書共有十三卷，第七卷到第十卷所討論的實際上是數論問題——只不過是以幾何的方式來描述的。在《幾何原本》中，數的大小用線段的長度來表示，越長的線段就表示越大的數。很多數字與數字之間的簡單關係，在《幾何原本》中都有對應的幾何語言。
例如，若數字 a 是數字 b 的整倍數，在《幾何原本》中就表達為，長度為 a 的線段可以用長度為 b 的線段來度量。比方說，黑板的長度是 2.7 公尺，一支鉛筆的長度是 18 厘公尺，你會發現黑板的長度正好等於 15 個鉛筆的長度。
我們就說，鉛筆的長度可以用來度量黑板的長度。如果一張課桌的長度是 117 厘公尺，那麼 6 個鉛筆的長度不夠課桌長， 7 個鉛筆的長度又超過了課桌長，因而我們就無法用鉛筆來度量課桌的長度了。哦，當然，實際上課桌長相當於 6.
5 個鉛筆長，但是鉛筆上又沒有刻度，我們用鉛筆來度量課桌時，怎麼知道最終結果是 6.5 個鉛筆長呢？因而，只有 a 恰好是 b 的整數倍時，我們才說 b 可以度量 a 。
給定兩條長度不同的線段 a 和 b ，如果能夠找到第三條線段 c ，它既可以度量 a ，又可以度量 b ，我們就說 a 和 b 是可公度的（ commensurable ，也叫做可通約的）， c 就是 a 和 b 的乙個公度單位。舉個例子： 1 英吋和 1 厘公尺是可公度的嗎？
歷史上，英吋和厘公尺的換算關係不斷在變，但現在，英吋已經有了乙個明確的定義： 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 的最大公度單位，不妨假設 a 比 b 更長。
如果 b 正好能度量 a ，那麼考慮到 b 當然也能度量它自身，因而 b 就是 a 和 b 的乙個公度單位；如果 b 不能度量 a ，這說明 a 的長度等於 b 的某個整倍數，再加上乙個零頭。我們不妨把這個零頭的長度記作 c 。如果有某條線段能夠同時度量 b 和 c ，那麼它顯然也就能度量 a 。
也就是說，為了找到 a 和 b 的公度單位，我們只需要去尋找 b 和 c 的公度單位即可。怎樣找呢？我們故技重施，看看 c 是否能正好度量 b 。
如果 c 正好能度量 b ，c 就是 b 和 c 的公度單位，從而也就是 a 和 b 的公度單位；如果 c 不能度量 b ，那看一看 b 被 c 度量之後剩餘的零頭，把它記作 d ，然後繼續用 d 度量 c ，並不斷這樣繼續下去，直到某一步沒有零頭了為止。
我們還是來看乙個實際的例子吧。讓我們試著找出 690 和 2202 的公度單位。顯然， 1 是它們的乙個公度單位， 2 也是它們的乙個公度單位。
我們希望用 euclid 的演算法求出它們的最大公度單位。首先，用 690 去度量 2202 ，結果發現 3 個 690 等於 2070 ，度量 2202 時會有乙個大小為 132 的零頭。接下來，我們用 132 去度量 690 ，這將會產生乙個 690 - 132 × 5 = 30 的零頭。
用 30 去度量 132 ，仍然會有乙個大小為 132 - 30 × 4 = 12 零頭。再用 12 去度量 30 ，零頭為 30 - 12 × 2 = 6 。最後，我們用 6 去度量 12 ，你會發現這回終於沒有零頭了。
因此， 6 就是 6 和 12 的乙個公度單位，從而是 12 和 30 的公度單位，從而是 30 和 132 的公度單位，從而是 132 和 690 的公度單位，從而是 690 和 2202 的公度單位。
我們不妨把 euclid 演算法對 a 和 b 進行這番折騰後得到的結果記作 x 。從上面的描述中我們看出， x 確實是 a 和 b 的公度單位。不過，它為什麼一定是最大的公度單位呢？
為了說明這一點，下面我們來證明，事實上， a 和 b 的任意乙個公度單位一定能夠度量 x ，從而不會超過 x 。如果某條長為 y 的線段能同時度量 a 和 b ，那麼注意到，它能度量 b 就意味著它能度量 b 的任意整倍數，要想讓它也能度量 a 的話，只需而且必需讓它能夠度量 c 。於是， y 也就能夠同時度量 b 和 c ，根據同樣的道理，這又可以推出 y 一定能度量 d ……因此，最後你會發現， y 一定能度量 x 。
用現在的話來講，求兩條線段的最大公度單位，實際上就是求兩個數的最大公約數——最大的能同時整除這兩個數的數。用現在的話來描述 euclid 演算法也會簡明得多：假設剛開始的兩個數是 a 和 b ，其中 a > b ，那麼把 a 除以 b 的餘數記作 c ，把 b 除以 c 的餘數記作 d ，c 除以 d 餘 e ， d 除以 e 餘 f ，等等等等，不斷拿上一步的除數去除以上一步的餘數。
直到某一次除法餘數為 0 了，那麼此時的除數就是最終結果。因此， euclid 演算法又有乙個形象的名字，叫做「輾轉相除法」。
輾轉相除法的效率非常高，剛才大家已經看到了，計算 690 和 2202 的最大公約數時，我們依次得到的餘數是 132, 30, 12, 6 ，做第 5 次除法時就除盡了。實際上，我們可以大致估計出輾轉相除法的效率。第一次做除法時，我們是用 a 來除以 b ，把餘數記作 c 。
如果 b 的值不超過 a 的一半，那麼 c 更不會超過 a 的一半（因為餘數小於除數）；如果 b 的值超過了 a 的一半，那麼顯然 c 直接就等於 a - b ，同樣小於 a 的一半。因此，不管怎樣， c 都會小於 a 的一半。下一步輪到 b 除以 c ，根據同樣的道理，所得的餘數 d 會小於 b 的一半。
接下來， e 將小於 c 的一半， f 將小於 d 的一半，等等等等。按照這種速度遞減下去的話，即使最開始的數是上百位的大數，不到 1000 次除法就會變成一位數（如果演算法沒有提前結束的話），交給計算機來執行的話保證秒殺。用專業的說法就是，輾轉相除法的運算次數是對數級別的。
很長一段時間裡，古希臘人都認為，任意兩條線段都是可以公度的，我們只需要做一遍輾轉相除便能把這個公度單位給找出來。事實真的如此嗎？輾轉相除法有可能失效嗎？
我們至少能想到一種可能：會不會有兩條長度關係非常特殊的線段，讓輾轉相除永遠達不到終止的條件，從而根本不能算出乙個「最終結果」？注意，線段的長度不一定（也幾乎不可能）恰好是整數或者有限小數，它們往往是一些根本不能用有限的方式精確表示出來的數。
考慮到這一點，兩條線段不可公度完全是有可能的。
全球最美麗的王冠
作者 寧良凌 決策與資訊 2012年第03期 配飾的焦點往往在 頂上 也因此各國王室都擁有 關注度很高的 話題王冠 英國伊利沙伯二世被稱為 王冠第一人 她擁有各式各樣價值不菲的王冠。英國 英國及愛爾蘭女孩王冠 1893年瑪麗和喬治五世成婚，她收到的結婚禮物就是這頂以 英國及愛爾蘭女孩 命名的王冠。最...
《血染的王冠》讀後感
自然之道 血染的王冠 讀後感 在2014年讀書節裡，我讀了一本很感人的動物 相信大家讀了也會喜歡。這本書講了在一群滇金絲猴中 黑披風 雄猴搶奪 麻子 猴王的王位，但由於 我 的干預，黑披風 雄猴未能將 麻子 猴王趕入 葬王灘 淹死，也就是說 王冠沒有被鮮血染紅 新生的政權埋下了被顛覆的危機。黑披風 ...
老虎的王冠不見了
這天，老虎大王一覺醒來，發現王冠不見了，啊！我的王冠不見了！一聲震耳欲聾的怒吼傳遍了森林。老虎大王把森林裡的動物全部召集起來，乙個個盤問，發誓要查出偷王冠的賊。一來到王宮，狐狸馬上屁顛屁顛的跑上來，對著七竅生煙 鼻孔冒氣的虎大王一邊捶背一邊嬌聲嬌氣的說 老虎大王，您如一片寬闊的天空，如一朵白色的雲，...