量子计算的算法：离散对数与因数分解
量子计算机能飞快地分解巨大的数——并攻破守护互联网的加密。
1994 年，一位数学家证明：一台还没有人造出来的机器，原则上能破解守护着互联网秘密的那些密码。
核心想法
几乎一切在线的安全通信——你的银行、你的消息、你的密码——都押在一个简单的赌注上：哪怕最快的计算机，要找出「相乘才得到某个巨大的数」的那两个素数，也得花上比宇宙年龄还久的时间。彼得·肖尔却表明：一台量子计算机——一种遵循量子物理规则、根本不同的机器——能很快赢下这个赌注。它能飞快地分解那些庞大的数——从而打开建立其上的密码。
他的窍门，是把因数分解变成一个关于「节奏」的问题。你不去正面搜寻因数，而是去看藏在数里的一种重复图样，找出它多久重复一次。量子计算机能让许多可能性像层叠的波那样相互干涉，于是一下子就「感觉」到这种重复。
它是如何诞生的
整个 1980 年代，少数物理学家——理查德·费曼也在其中——揣摩着：一台用量子零件造出来的计算机，能否做到普通机器做不到的事。这想法引人入胜，却找不到一个非它不可的用途。直到 1994 年，在 AT&T 的贝尔实验室，彼得·肖尔找到了一个。他在丹尼尔·西蒙关于「求隐藏周期」的巧妙结果之上，证明了量子机器能分解数、能攻破最广为使用的密码。
他那年十一月所作的报告，让整个领域为之一震。一夜之间，量子计算不再是一桩奇思，而成了国家安全的大事；资金与人才纷纷涌入，而那场「真把这种机器造出来——并防住它」的漫长竞赛，就此开始。
它为何重要
RSA 及其同族，守护着地球上几乎每一条安全连接（RSA 就在本馆中）。肖尔的结果是一个证明——而非一种预感：一台足够大的量子计算机将攻破它们。正是这一个事实，掀起了全球对「后量子」密码的搜寻——那是连量子计算机也攻不破的密码；2024 年，首批这样的标准正式发布，全世界的系统如今正在升级——而那台构成威胁的机器，还未诞生。
一个可以想象的画面
想象一座上了锁的钟楼，它的门只有在你确知「两记特定钟声之间隔着多少秒」时才会打开。一个拿着秒表的人，得听上长得离谱的时间，才能确定那节奏。而一台量子计算机，就好比能同时听见每一种可能的节奏一齐响起，再瞬间挑出那真正存在的一种。一旦它知道了节拍，门——以及门后的秘密——便自行打开。
它的位置
这是本馆中那门密码学的「暗面孪生」。迪菲与赫尔曼（1976），以及随后的 RSA（1978），把公钥密码建立在被认为难得没指望的问题之上；肖尔却表明，那些问题只是对「我们当时拥有的机器」才难。他的工作，与图灵「计算机究竟能做什么」之问比肩而立，并指向一个未来：从金钱到比特币（也在本馆中）——一切的安全，或许都得重新筑造。
A digital computer is generally believed to be an efficient universal computing device; that is, it is believed able to simulate any physical computing device with an increase in computation time by at most a polynomial factor. This may not be true when quantum mechanics is taken into consideration. This paper considers factoring integers and finding discrete logarithms, two problems which are generally thought to be hard on a classical computer and which have been used as the basis of several proposed cryptosystems.