量子計算機可實現 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），更多干貨在等你！