我謹代表 Ron Rivest、Adi Shamir 以及我自己，感謝 ACM、Intel Corporation、研究人員社群、我們的朋友、我們的老師，給予我們這份巨大的榮譽。這個獎項對我們有著特殊的意義，因為它與 Turing 本人的研究生涯歷程息息相關。回想 Turing 在 1936 年，年僅 24 歲時，發表了他關於 Hilbert 判定問題 (Entscheidungsproblem) 的著名論文。他在那裡介紹了 圖靈機 (Turing machine)。這是一個驚人簡單卻能執行驚人任務的裝置。事實上，它似乎精確地捕捉到了「計算」這個概念的含義。因此，1936 年的這篇論文可說是我們學科的開端。令人驚訝的是，僅僅兩年後，在 1938 年，似乎是預見了即將到來的戰爭，Turing 前往為英國政府從事密碼學工作。戰爭開始後，他去了 Bletchley Park，在那裡開始研究 Enigma 機器，並運用他關於計算本質的新思想，成功地破解了它，建造了一個被稱為「bomb」的機電裝置。這種將理論數學與密碼學結合的方式，在這條道路上多次出現，也在我們自己的工作中以微小的方式有所體現。

演講概述

以下是我們這次演講的概述。

Speaker Topic
Leonard Adleman RSA 之前的時期 (理論和密碼學發展)
Ron Rivest RSA 和早期情況
Adi Shamir 密碼學現狀報告

首先，我想簡要回顧一下數論的歷史。

數論簡史

這一切似乎始於大約 2,300 年前，當時希臘人顯然發現了某種形式的算術基本定理 (fundamental theorem of arithmetic)，即每個數字都可以寫成唯一一組素數 (primes) 的乘積。這是數論中的一個門檻概念。素數對於數論，就像元素對於化學一樣。除非你通過這個門檻，否則你無法嚴肅地進行數學上的數論研究，而希臘人似乎是第一個做到的。這是 Eratosthenes 的一幅畫像，他是第一個提出用於測試素數和因數分解的演算法的人。那就是他著名的篩法 (sieve)。不幸的是，從那以後，事情發展得並不快。直到大約 1200 年，Fibonacci 才開始撰寫關於數論的文章，並指出當達到目標數字的平方根時，就可以停止篩選了。到了 19 世紀，區分素數和合數、尋找素數判定演算法的問題，實際上是所有數學中最著名的問題之一。它吸引了許多偉大數學家的注意，包括其中最偉大的一位，數學王子 Carl Friedrich Gauss。在他 1801 年的傑作《Disquisiciones Arithmetica》中，他提出了幾種素數判定演算法。順帶一提，據我所知，他是第一個說素數判定問題和因數分解問題不是同一個問題的人，這個區別後來對 RSA 變得非常重要。他提出了兩種素數判定演算法，他說這些演算法會讓熱愛算術的人感到愉快。確實如此，如果你喜歡令人難以置信的美妙數學思想，它們會讓你非常愉快。但是，如果你正在尋找一個快速的通用演算法，你可能會不太高興，因為這些不是。在 Gauss 之後的大約 200 年裡，人們做了很多工作。

現在我想談談密碼學。

密碼學起源

密碼學的起源則更為模糊。秘密書寫似乎在許多不同的時間和地點產生。但至少大約 2,700 年前，斯巴達人就已經發展出了我們現在稱為換位密碼 (transposition ciphers) 的東西。特別是他們有一種稱為 scytale 的工具，它由一條捲在棍子上的莎草紙帶組成。感興趣的訊息寫在棍子周圍。然後當紙帶展開時，結果是字母的位置被換位了。據推測，你只有擁有與原始棍子相同直徑的棍子再次捲上莎草紙時，才能讀取訊息。到了 Caesar 的時代，出現了第二種類型的密碼，即所謂的替換密碼 (substitution cipher)，其中原始訊息中的每個字母都被替換成一個新的字母。替換密碼的這個想法隨著時間被不斷推廣和普遍化。到了 16 世紀，Vigenère 創造了所謂的多表替換 (polyalphabetic substitutions)。到了 20 世紀，Vernam 開發了所謂的一次性密碼本 (one-time pad)。有趣的是，Vigenère 密碼似乎抵擋了密碼分析攻擊約 300 年，最終被破解，有人知道是誰嗎？結果是 Charles Babbage 破解的，他是發明分析機的人，或許可以說是電腦科學之父。然後在 1948 年，發生了一個巨大的突破，那就是 Claude Shannon 發表了他著名的論文《A Mathematical Theory of Communication》，他在其中創立了資訊理論 (information theory) 領域。次年，他在他的新資訊理論中發表了一項結果，證明 Vernam 密碼，即一次性密碼本，實際上是絕對不可破解的，這是第一個關於不可破解性的證明。

所以我們有了這兩個領域，它們積累了人類數千年來的智慧結晶。但如果我們回顧 1970 年，我們可以發現有些東西是缺失的。例如，在 1973 年，如果你問什麼是素數判定的最快通用演算法，答案是沒有比 Fibonacci 所描述的演算法更快的了。而他的也只是對 Eratosthenes 最初提出的演算法進行了小幅改進。那麼，缺失的是什麼？需要什麼來釋放所有這些智力潛能，並帶來一系列新的發明？缺失的是俗話說的那隻扇動翅膀的蝴蝶。這發生在 1960 年代中期，隨著一個新領域的發明，即計算複雜性 (computational complexity)。

缺乏的要素與計算複雜性的興起

如今，計算複雜性可能是自 Turing 最初思想以來，計算領域中最傑出的想法。計算複雜性領域有許多奠基者 (fathers)，不是所有人都列在這裡。他們包括 Michael Rabin、Leonid Levin、Edmund Fisher、Ullman、Hopcroft、Aho，等等。但這個領域得名於 Hartmanis 和 Stearns 在 1965 年發表的一篇關於演算法計算複雜性的論文。1967 年，Manuel Blum 發表了他的博士論文《A Machine-Independent Theory of the Complexity of Recursive Functions》，這將計算複雜性置於更廣泛的理論框架中。隨後是 Stephen Cook，他在 1970 年發表了論文《The Complexity of Theory-Improving Procedures》，該論文描述了 NP 類別和 NP完全性 (NP completeness) 的概念，Levin 也獨立地描述了這個概念。僅僅一年後，是 Karp 的傑出論文《Reducibility Among Combinatorial Problems》，其中明確指出這個概念，這種看待計算的方式，對於我們的學科至關重要。

這隻扇動翅膀的蝴蝶對數論和密碼學這兩個領域都產生了巨大的影響。在數論中，我們突然有了工具來審視問題，並試圖根據它們的複雜性進行分類。我們可以審視演算法，並歷史上首次準確分析它們的執行速度。對於數論和理論電腦科學領域的年輕研究人員，例如我自己和這裡的 Gary Miller 來說，這就像獲得了「竊取的許可證」。因為我們可以回顧幾千年來偉大的智力努力，審視我們前輩的思想，從他們的所有思想中提取具有計算複雜性潛力的那些，並拒絕那些，無論在數學上多麼美妙，但似乎沒有計算複雜性潛力的。我們可以將它們剪貼成新的、高效的演算法。這催生了演算法數論的黃金時代。事實上，我會說這催生了人類歷史上演算法數論的最高峰，而且至今仍在繼續。總之，到了 1975 年，我們有了 Solovey 和 Strassen 的結果，它們表明合數 (composites) 可以在隨機多項式時間 (random polynomial time) 內被識別出來。這在實際操作上意味著我們現在可以快速區分素數和合數。到了 1975 年，我們也審視了因數分解的演算法，查看了所有現有的思想並進行了分析，意識到因數分解的多項式時間演算法並不存在。不是說它們將來可能不存在，而是當時不存在。

領域匯流與公開金鑰密碼系統

現在，在密碼學領域，計算複雜性的這個想法也產生了巨大的影響。除其他外，它指出一個概念，一個新的概念，可以被理解。這個概念是，一個密碼的不可破解性，並非因為 Shannon 所說的缺乏足夠資訊，而是因為沒有足夠的「時間」來破解它。所以這是一個全新的想法。而在與密碼學的另一次互動中，這個想法與三位對電子時代密碼學未來感興趣的研究人員產生了交集，他們是 Stanford Group 的 Whit Diffie、Marty Hellman 和 Ralph Merkle，也是我們的朋友。因此，他們在 1976 年提出了公開金鑰密碼系統 (public key cryptosystem) 的概念，這可說是密碼學史上最偉大的想法。所以我們看到這三個學科——數論、計算複雜性以及密碼學——全都匯流在一起。演算法數論和密碼學領域的新思想層出不窮。這基本上為我同事們將要進行的演講奠定了基礎。但在我結束這個話題之前，我想感謝這些先生們。最近有消息指出，在英國的密碼機構 GCHQ (繼承 Bletchley Park 的機構) 中，這些研究人員 Clifford Cox、James Ellis 和 Malcolm Williamson，顯然也獨立地發展了許多公開金鑰的概念。