诞生在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。
当然,这里不是模三,是模一个很大的数:
那么,平方运算要做多少次?
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 (魔域) 的原始版本。
谜题本题:
— 完 —
诚挚招聘
量子位正在招募编辑/记者,工作地点在北京中关村。期待有才气、有热情的同学加入我们!相关细节,请在量子位公众号(QbitAI)对话界面,回复“招聘”两个字。
量子位 QbitAI · 头条号签约作者
վ’ᴗ’ ի 追踪AI技术和产品新动态