舒爾算法

舒爾算法，即秀爾算法（Shor算法），以數學家彼得·秀爾命名，是一個在1994年發現的，針對整數分解這題目的的量子算法（在量子計算機上面運作的算法）。它解決如下題目：給定一個整數N，找出他的質因數。

基本介紹

• 中文名：舒爾算法
• 外文名：Shor's algorithm
• 領域：計算機編程

簡介

舒爾算法，即秀爾算法（Shor算法），以數學家彼得·秀爾命名，是一個在1994年發現的，針對整數分解這題目的的量子算法（在量子計算機上面運作的算法）。它解決如下題目：給定一個整數N，找出他的質因數。

在一個量子計算機上面，要分解整數N，秀爾算法的運作需要多項式時間（時間是logN的某個多項式這么長，logN在這裡的意義是輸入的檔案長度）。更精確的說，這個算法花費O((logN))的時間，展示出質因數分解問題可以使用量子計算機以多項式時間解出，因此在複雜度類BQP裡面。這比起傳統已知最快的因數分解算法，普通數域篩選法還要快了一個指數的差異。

秀爾算法非常重要，因為它代表使用量子計算機的話，我們可以用來破解已被廣泛使用的公開密鑰加密方法，也就是RSA加密算法。RSA算法的基礎在於假設了我們不能很有效率的分解一個已知的整數。就目前所知，這假設對傳統的（也就是非量子）電腦為真；沒有已知傳統的算法可以在多項式時間內解決這個問題。然而，秀爾算法展示了因數分解這問題在量子計算機上可以很有效率的解決，所以一個足夠大的量子計算機可以破解RSA。這對於建立量子計算機和研究新的量子計算機算法，是一個非常大的動力。

在2001年，IBM的一個小組展示了秀爾算法的實例，使用NMR實驗的量子計算機，以及7個量子位元，將15分解成3×5。然而，對IBM的實驗的是否是量子計算的真實展示，則有一些疑慮出現，因為沒有纏結現象被發現。在IBM的實驗之後，有其他的團隊以光學量子位元實驗秀爾算法，並強調其纏結現象可被觀察到。

整數分解

在數學中，整數分解（英語：integer factorization）又稱素因數分解（prime factorization），是將一個正整數寫成幾個約數的乘積。例如，給出45這個數，它可以分解成(3^2)×5。根據算術基本定理，這樣的分解結果應該是獨一無二的。這個問題在代數學、密碼學、計算複雜性理論和量子計算機等領域中有重要意義。

實際套用

給出兩個大約數，很容易就能將它們兩個相乘。但是，給出它們的乘積，找出它們的因子就顯得不是那么容易了。這就是許多現代密碼系統的關鍵所在。如果能夠找到解決整數分解問題的快速方法，幾個重要的密碼系統將會被攻破，包括RSA公鑰算法和Blum Blum Shub隨機數發生器。

儘管快速分解是攻破這些系統的方法之一，仍然會有其它的不涉及到分解的其它方法。所以情形完全可能變成這樣：整數分解問題仍然是非常困難，這些密碼系統卻是能夠很快攻破。有的密碼系統則能提供更強的保證：如果這些密碼系統被快速破解（即能夠以多項式時間複雜度破解），則可以利用破解這些系統的算法來快速地（以多項式時間複雜度）分解整數。換句話說，破解這樣的密碼系統不會比整數分解更容易。這樣的密碼系統包括Rabin密碼系統（RSA的一個變體）以及Blum Blum Shub隨機數發生器。

質因數

質因數（或稱質因子）在數論里是指能整除給定正整數的質數。根據算術基本定理，不考慮排列順序的情況下，每個正整數都能夠以唯一的方式表示成它的質因數的乘積。兩個沒有共同質因子的正整數稱為互質。因為1沒有質因子，1與任何正整數（包括1本身）都是互質。只有一個質因子的正整數為質數。

將一個正整數表示成質因數乘積的過程和得到的表示結果叫做質因數分解。顯示質因數分解結果時，如果其中某個質因數出現了不止一次，可以用冪次的形式表示。例如360的質因數分解是：

其中的質因數2、3、5在360的質因數分解中的冪次分別是3，2，1。

數論中的不少函式與正整數的質因子有關，比如取值為n的質因數個數的函式和取值為n的質因數之和的函式。它們都是加性函式，但並非完全加性函式。