夜晚來自凹陷的秘史

量子比特報(bào)告|公眾號QbitAI

誕生于1999年的MIT密碼難題被自學(xué)的程序員解決了。

當(dāng)年，出題人按照摩爾定律估計(jì)，完成計(jì)算要35年。

結(jié)局的到來，足足提前了15年。

而交卷的人類只用了i7電腦的一個CPU核。

這個密碼，還將解鎖一個20年前的秘密。

怎樣的一個謎？

回到1999年4月，MIT計(jì)算機(jī)科學(xué)實(shí)驗(yàn)室 (LCS) 就要滿35歲了。

它收到了一份富有儀式感的生日禮物，是個時間囊 (Time Capsule) ：有人把重要的東西藏在里面，設(shè)定一個時間，留給未來的人類打開。

與眾不同的是，這個時間囊有一個“密碼鎖”，是由密碼學(xué)家Ron Rivest設(shè)計(jì)的。著名的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í)驗(yàn)室當(dāng)時的年紀(jì)。

那如果一直沒有人解出答案，或者大家干脆已經(jīng)忘記了這一道謎題呢？

設(shè)計(jì)者就把35年定為最終期限。即便人類沒有交出答卷，時間囊依然會在2033年、實(shí)驗(yàn)室70周年的慶典上開啟。

當(dāng)然，1999年的科學(xué)家們不會想到，四年之后LCS實(shí)驗(yàn)室就和AI實(shí)驗(yàn)室合體進(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è)備就可能超過我了?！?/p>

三年有余，博納完成了那80萬億次平方運(yùn)算。

最后一步，是用平方運(yùn)算得到的結(jié)果、和題中給出的一個數(shù)，按題目要求做運(yùn)算；算出的一串?dāng)?shù)字，可以翻譯成一句祝賀。

博納收到了溫暖的賀詞，便雞凍地向MIT宣布自己解開了謎題。

像前文說起的那樣，20年了，計(jì)算機(jī)科學(xué)實(shí)驗(yàn)室不復(fù)存在，與AI實(shí)驗(yàn)室合體而成的CSAIL實(shí)驗(yàn)室也已赫赫有名。

而CSAIL負(fù)責(zé)人Daniela Rus聽到這個消息的時候，甚至不知道題目的存在。不過，稍微回溯一下歷史，雙方便對上了暗號。

博納現(xiàn)在還不能透露這句話是什么。一切等到5月15日，答案會和時間囊一同昭告天下。

他會帶著榮光參加這場儀式。

事實(shí)也證明，不讓太多人知道自己的想法，是非常機(jī)智的：

對手也快完成了

雖然，CSAIL負(fù)責(zé)人并不記得當(dāng)年的故事，但企圖解開這個謎團(tuán)的，并不止博納一人。

還有一個根正苗紅的項(xiàng)目組，名叫Cryptophage，由前英特爾工程師Simon Peffers帶領(lǐng)，只為破解MIT密碼而生。

他們用的方法和博納不一樣。那是一個新的平方算法，跑在可編程的加速器FPGA上，大約比CPU快10倍。

團(tuán)隊(duì)說只需要兩個月，預(yù)計(jì)5月11日就能跑出答案了。

結(jié)局總是出人意料。團(tuán)隊(duì)滿懷欣喜地聯(lián)系MIT，預(yù)告即將誕生的成果，卻被告知已有人捷足先登。

雖敗猶榮，他們依然受到了邀請，參加5月15日時間囊開啟的盛會。

One More Thing

在打開之前，除了設(shè)計(jì)師沒有人知道，時間囊里究竟藏了多少秘密。

但現(xiàn)在已經(jīng)有些劇透了。有的禮物來自比爾·蓋茨，有的禮物來自萬維網(wǎng)的發(fā)明者Tim Berners-Lee。

而大贏家博納最期待的，還是世界上最早的PC游戲：Zork (魔域) 的原始版本。

謎題本題：

— 完 —

誠摯招聘

量子位正在招募編輯/記者，工作地點(diǎn)在北京中關(guān)村。期待有才氣、有熱情的同學(xué)加入我們！相關(guān)細(xì)節(jié)，請?jiān)诹孔游还娞?QbitAI)對話界面，回復(fù)“招聘”兩個字。

量子位 QbitAI · 頭條號簽約作者

?'?' ? 追蹤AI技術(shù)和產(chǎn)品新動態(tài)