20年未解的MIT密碼難題，被自學(xué)成才的程序員破解了，比預(yù)計早15年
本文經(jīng)AI新媒體量子位（公眾號ID:QbitAI）授權(quán)轉(zhuǎn)載，轉(zhuǎn)載請聯(lián)系出處。
誕生在 1999 年的 MIT 密碼難題，被一個自學(xué)成才的程序員破解了。
當(dāng)年，出題人按照摩爾定律估計，完成計算要35 年。
結(jié)局的到來，足足提前了 15 年。
而交卷的人類只用了 i7 電腦的一個 CPU 核。
這個密碼，還將解鎖一個 20 年前的秘密。
怎樣的一個謎？
回到 1999 年 4 月，MIT 計算機(jī)科學(xué)實(shí)驗室 (LCS) 就要滿 35 歲了。
它收到了一份富有儀式感的生日禮物，是個時間囊 (Time Capsule) ：有人把重要的東西藏在里面，設(shè)定一個時間，留給未來的人類打開。
與眾不同的是，這個時間囊有一個“密碼鎖”，是由密碼學(xué)家 Ron Rivest 設(shè)計的。著名的RSA 加密算法便是以他的名字命名。
Rivest 設(shè)了一個平方密碼，初始值是2。2^2=4，4^2=16，16^2=256……
平方之后還要取模 (mod) ，就是余數(shù)。如 16 ≡ 1 mod 3， 16 除以 3 余1。
當(dāng)然，這里不是模三，是模一個很大的數(shù)：
△ 這是兩個大質(zhì)數(shù)的乘積，RSA 算法的根基
那么，平方運(yùn)算要做多少次？
80 萬億次。
就像開頭提到的那樣，用摩爾定律推算，破解這個密碼大概需要35 年。這正是實(shí)驗室當(dāng)時的年紀(jì)。
那如果一直沒有人解出答案，或者大家干脆已經(jīng)忘記了這一道謎題呢？
設(shè)計者就把 35 年定為最終期限。即便人類沒有交出答卷，時間囊依然會在2033 年、實(shí)驗室 70 周年的慶典上開啟。
當(dāng)然，1999 年的科學(xué)家們不會想到，四年之后 LCS 實(shí)驗室就和 AI 實(shí)驗室合體進(jìn)化，成為了后來大名鼎鼎的CSAIL。
他們大概也不會想到，20 年后會有人提前交卷。
并且，***個交卷的程序員，只用了三年半來解題而已。
三年半破解謎題
2015 年，謎題發(fā)射的 16 年后，自學(xué)成才的比利時程序員Bernard Fabrot (簡稱“博納”) 和它偶遇了。
謎題代碼是用 Java 寫的，但博納認(rèn)為用 GNP 多精度運(yùn)算庫 (GMP) 的話，解起來會更快。
這個開源庫是用C語言寫成的，也為 Python、R、C++、PHP 等各種語言做了包裝。
博納把家里臺式機(jī)的其中一個 CPU 核，變成了解題專用，7 天 24 小時不停地跑。除非家里停電，或者要出遠(yuǎn)門。
除了最親密的朋友之外，博納不敢把自己的秘密行動告訴任何人。
“我知道我是有機(jī)會贏的，可如果告訴了別人，他們用上更強(qiáng)的設(shè)備就可能超過我了。”
三年有余，博納完成了那80 萬億次平方運(yùn)算。
***一步，是用平方運(yùn)算得到的結(jié)果、和題中給出的一個數(shù)，按題目要求做運(yùn)算；算出的一串?dāng)?shù)字，可以翻譯成一句祝賀。
博納收到了溫暖的賀詞，便雞凍地向 MIT 宣布自己解開了謎題。
像前文說起的那樣，20 年了，計算機(jī)科學(xué)實(shí)驗室不復(fù)存在，與 AI 實(shí)驗室合體而成的CSAIL 實(shí)驗室也已赫赫有名。
而 CSAIL 負(fù)責(zé)人 Daniela Rus 聽到這個消息的時候，甚至不知道題目的存在。不過，稍微回溯一下歷史，雙方便對上了暗號。
博納現(xiàn)在還不能透露這句話是什么。一切等到5 月 15 日，答案會和時間囊一同昭告天下。
他會帶著榮光參加這場儀式。
事實(shí)也證明，不讓太多人知道自己的想法，是非常機(jī)智的：
對手也快完成了
雖然，CSAIL 負(fù)責(zé)人并不記得當(dāng)年的故事，但企圖解開這個謎團(tuán)的，并不止博納一人。
還有一個根正苗紅的項目組，名叫Cryptophage，由前英特爾工程師 Simon Peffers 帶領(lǐng)，只為破解 MIT 密碼而生。
他們用的方法和博納不一樣。那是一個新的平方算法，跑在可編程的加速器FPGA上，大約比 CPU 快 10 倍。
團(tuán)隊說只需要兩個月，預(yù)計 5 月 11 日就能跑出答案了。
結(jié)局總是出人意料。團(tuán)隊滿懷欣喜地聯(lián)系 MIT，預(yù)告即將誕生的成果，卻被告知已有人捷足先登。
雖敗猶榮，他們依然受到了邀請，參加 5 月 15 日時間囊開啟的盛會。
One More Thing
在打開之前，除了設(shè)計師沒有人知道，時間囊里究竟藏了多少秘密。
但現(xiàn)在已經(jīng)有些劇透了。有的禮物來自比爾·蓋茨，有的禮物來自萬維網(wǎng)的*** Tim Berners-Lee。
而大贏家博納最期待的，還是世界上最早的 PC 游戲：Zork (魔域) 的原始版本。
