十大足球直播推荐栗子 发自 凹非寺
量子位 报道 | 公众号 QbitAI
诞生在1999年的MIT密码难题，被一个自学成才的程序员破解了。
当年，出题人按照摩尔定律估计，完成计算要35年。
结局的到来，足足提前了15年。
而交卷的人类只用了i7电脑的一个CPU核。
这个密码，还将解锁一个20年前的秘密。
怎样的一个谜？
回到1999年4月，MIT计算机科学实验室 (LCS) 就要满35岁了。
它收到了一份富有仪式感的生日礼物，是个时间囊 (Time Capsule) ：有人把重要的东西藏在里面，设定一个时间，留给未来的人类打开。
与众不同的是，这个时间囊有一个“密码锁”，是由密码学家Ron Rivest设计的。著名的RSA加密算法便是以他的名字命名。
Rivest设了一个平方密码，初始值是2。2^2=4，4^2=16，16^2=256……
平方之后还要取模 (mod) ，就是余数。如16 ≡ 1 mod 3， 16除以3余1。
当然，这里不是模三，是模一个很大的数：
△ 这是两个大质数的乘积，RSA算法的根基
那么，平方运算要做多少次？
80万亿次。
就像开头提到的那样，用摩尔定律推算，破解这个密码大概需要35年。这正是实验室当时的年纪。
那如果一直没有人解出答案，或者大家干脆已经忘记了这一道谜题呢？
设计者就把35年定为最终期限。即便人类没有交出答卷，时间囊依然会在2033年、实验室70周年的庆典上开启。
当然，1999年的科学家们不会想到，四年之后LCS实验室就和AI实验室合体进化，成为了后来大名鼎鼎的CSAIL。
他们大概也不会想到，20年后会有人提前交卷。
并且，第一个交卷的程序员，只用了三年半来解题而已。
三年半破解谜题
2015年，谜题发射的16年后，自学成才的比利时程序员Bernard Fabrot (简称“博纳”) 和它偶遇了。
谜题代码是用Java写的，但博纳认为用GNP多精度运算库 (GMP) 的话，解起来会更快。
这个开源库是用C语言写成的，也为Python、R、C 、PHP等各种语言做了包装。
博纳把家里台式机的其中一个CPU核，变成了解题专用，7天24小时不停地跑。除非家里停电，或者要出远门。
除了最亲密的朋友之外，博纳不敢把自己的秘密行动告诉任何人。
“我知道我是有机会赢的，可如果告诉了别人，他们用上更强的设备就可能超过我了。”
三年有余，博纳完成了那80万亿次平方运算。
最后一步，是用平方运算得到的结果、和题中给出的一个数，按题目要求做运算；算出的一串数字，可以翻译成一句祝贺。
博纳收到了温暖的贺词，便鸡冻地向MIT宣布自己解开了谜题。
像前文说起的那样，20年了，计算机科学实验室不复存在，与AI实验室合体而成的CSAIL实验室也已赫赫有名。
而CSAIL负责人Daniela Rus听到这个消息的时候，甚至不知道题目的存在。不过，稍微回溯一下历史，双方便对上了暗号。
博纳现在还不能透露这句话是什么。一切等到5月15日，答案会和时间囊一同昭告天下。
他会带着荣光参加这场仪式。
事实也证明，不让太多人知道自己的想法，是非常机智的：
对手也快完成了
虽然，CSAIL负责人并不记得当年的故事，但企图解开这个谜团的，并不止博纳一人。
还有一个根正苗红的项目组，名叫Cryptophage，由前英特尔工程师Simon Peffers带领，只为破解MIT密码而生。
他们用的方法和博纳不一样。那是一个新的平方算法，跑在可编程的加速器FPGA上，大约比CPU快10倍。
团队说只需要两个月，预计5月11日就能跑出答案了。
结局总是出人意料。团队满怀欣喜地联系MIT，预告即将诞生的成果，却被告知已有人捷足先登。
虽败犹荣，他们依然受到了邀请，参加5月15日时间囊开启的盛会。
One More Thing
在打开之前，除了设计师没有人知道，时间囊里究竟藏了多少秘密。
但现在已经有些剧透了。有的礼物来自比尔·盖茨，有的礼物来自万维网的发明者Tim Berners-Lee。
而大赢家博纳最期待的，还是世界上最早的PC游戏：Zork (魔域) 的原始版本。
谜题本题：
people.csail.mit.edu/rivest/lcs35-puzzle-description.txt
— 完 —
诚挚招聘
量子位正在招募编辑/记者，工作地点在北京中关村。期待有才气、有热情的同学加入我们！相关细节，请在量子位公众号(QbitAI)对话界面，回复“招聘”两个字。
量子位 QbitAI · 头条号签约作者
վ'ᴗ' ի 追踪AI技术和产品新动态
