量子計算機可實(shí)現 Shor 算法，或可破解 RSA

量子計算核心突破，RSA 密或成擺設。

在以前，要想計算出任意質(zhì)因數，一臺超級計算機很可能花費幾年的時(shí)間，不過(guò)這并劃算，效率低不說(shuō)，花費還大。近日，據外媒報道，麻省理工學(xué)院的科學(xué)家研究出一種新的方法可以明確計算出任意質(zhì)因數，它以可擴展的方式實(shí)現了 Shor 算法。

據悉，MIT 和 Innsbruck 大學(xué)的科學(xué)家們組裝了一臺 5 量子比特的量子計算機，使用激光脈沖來(lái)在每一個(gè)原子上實(shí)行 Shor 的算法，分解數字 15 的質(zhì)因數。這樣做的好處是，與現有量子系統相比，它能更高效地計算出方案且容易縮放區間。

從維基百科上可以看出，在 1994 年，Shor 算法才出現。它是在量子計算機上面運作的算法，并以數學(xué)家彼得·秀爾命名。簡(jiǎn)單來(lái)說(shuō)就是，能在一個(gè)整數 N 找出它的質(zhì)因數。

以一個(gè)整數 N 為例，要想分解它，Shor 算法的運作需要多項式時(shí)間，其實(shí)也就是 O((log N)3) 的時(shí)間。與傳統最快的因數分解算法相比，大約快了一個(gè)指數的差異。

從上述來(lái)看，Shor 算法對于我們來(lái)說(shuō)是很重要的，只要我們能夠熟練的運用它，或許就可以破解公開(kāi)密鑰加密方法，也就是大家常說(shuō)的 RSA 加密算法。它是一種非對稱(chēng)加密算法，其運用的領(lǐng)域非常廣泛，包括公開(kāi)密鑰加密和電子商業(yè)。它的優(yōu)勢在于對極大整數做因數分解的極大難度。簡(jiǎn)單來(lái)說(shuō)，對一極大整數做因數分解越困難，RSA 算法越可靠。在這之前，還沒(méi)有出現可以破解 RSA 算法的方法，現在如果出現一種快速因數分解的算法，那么使用 RSA 加密信息的人會(huì )越來(lái)越少。

不過(guò)，Shor 算法可以很有效率地解決量子計算機的因數分解問(wèn)題，前提是一個(gè)足夠大的量子計算機。

最后，記得關(guān)注微信公眾號：鎂客網(wǎng)（im2maker），更多干貨在等你！