量子計算将能分解任意極大整數，RSA加密或成擺設

就算是一台超級計算機有可能在數年的時間内計算出任意質因數，這也是得不償失的。為了科學地解決這個問題，麻省理工學院（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。這對于建立量子計算機和研究新的量子計算機算法，是一個非常大的動力。

本文轉自d1net（轉載）