就算是一台超级计算机有可能在数年的时间内计算出任意质因数，这也是得不偿失的。为了科学地解决这个问题，麻省理工学院（MIT）的科学家找到了明确的方法。今天，《科学》杂志最新发表的一篇论文显示，量子计算机有史以来第一次以可扩展的方式，实现了Shor算法。
据外媒Engadget报道，MIT和 Innsbruck大学的计算机科学家组装了一台5量子比特的量子计算机，它将能够用Shor算法完成对数字15的质因数分解。他们研发了一台量子计算机原型，然后使用一系列离子，借助激光脉冲来在4个量子比特上执行Shor算法，令其分解数字，第5个量子比特则用于储存和输出结果。目前的结果是，这台计算机不仅能够比现有量子系统更高效地计算出方案，而且区间缩放相对容易。
据维基百科解释，Shor算法（秀尔算法）是一个在1994年发现，以数学家彼得·秀尔命名，针对整数分解的量子算法（在量子计算机上面运作的算法）。比较不正式的表述是，它解决题目如下：给定一个整数N，找出他的质因数。
在一个量子计算机上面，要分解整数N，秀尔算法的运作需要多项式时间（时间是log N的某个多项式这么长）。更精确的说，这个算法花费O((log N)3)的时间，展示出质因数分解问题可以使用量子计算机以多项式时间解出，因此在复杂度类BQP里面。这比起传统已知最快的因数分解算法，普通数域筛选法，其花费次指数时间——大约O(e1.9 (log N)1/3 (log log N)2/3)，还要快了一个指数的差异。
秀尔算法的重要性不言而喻，实现它我们就有望破解已被广泛使用的公开密钥加密方法——RSA加密算法。RSA加密算法是一种非对称加密算法，在公开密钥加密和电子商业中RSA被广泛使用，其高度可靠的秘密在在于：对极大整数做因数分解的极大难度。也就是说，对一极大整数做因数分解愈困难，RSA算法愈可靠。但是，假如有人找到一种快速因数分解的算法的话，那么用RSA加密的信息的可靠性就肯定会极度下降。此前，世界上还没有任何攻击RSA算法的可靠方式。
然而，秀尔算法展示了因数分解这问题在量子计算机上可以很有效率地解决，所以一个足够大的量子计算机可以破解RSA。这对于建立量子计算机和研究新的量子计算机算法，是一个非常大的动力。
原文发布时间为：2016-03-06
本文作者：温晓桦
本文来源：雷锋网，如需转载请联系原作者。
