量子计算机可实现 Shor 算法，或可破解 RSA

量子计算核心突破，RSA 密或成摆设。

在以前，要想计算出任意质因数，一台超级计算机很可能花费几年的时间，不过这并划算，效率低不说，花费还大。近日，据外媒报道，麻省理工学院的科学家研究出一种新的方法可以明确计算出任意质因数，它以可扩展的方式实现了 Shor 算法。

据悉，MIT 和 Innsbruck 大学的科学家们组装了一台 5 量子比特的量子计算机，使用激光脉冲来在每一个原子上实行 Shor 的算法，分解数字 15 的质因数。这样做的好处是，与现有量子系统相比，它能更高效地计算出方案且容易缩放区间。

从维基百科上可以看出，在 1994 年，Shor 算法才出现。它是在量子计算机上面运作的算法，并以数学家彼得·秀尔命名。简单来说就是，能在一个整数 N 找出它的质因数。

以一个整数 N 为例，要想分解它，Shor 算法的运作需要多项式时间，其实也就是 O((log N)3) 的时间。与传统最快的因数分解算法相比，大约快了一个指数的差异。

从上述来看，Shor 算法对于我们来说是很重要的，只要我们能够熟练的运用它，或许就可以破解公开密钥加密方法，也就是大家常说的 RSA 加密算法。它是一种非对称加密算法，其运用的领域非常广泛，包括公开密钥加密和电子商业。它的优势在于对极大整数做因数分解的极大难度。简单来说，对一极大整数做因数分解越困难，RSA 算法越可靠。在这之前，还没有出现可以破解 RSA 算法的方法，现在如果出现一种快速因数分解的算法，那么使用 RSA 加密信息的人会越来越少。

不过，Shor 算法可以很有效率地解决量子计算机的因数分解问题，前提是一个足够大的量子计算机。

最后，记得关注微信公众号：镁客网（im2maker），更多干货在等你！