整数分解- 维基百科，自由的百科全书

在數學中，整數分解（英語：integer factorization）又稱質因數分解（prime factorization），是將一個正整數寫成幾個因數的乘積。

例如，給出45這個數，它可以分解成 ... 整數分解 數學技術 語言 監視 編輯 提示：此條目的主題不是整數分拆。

此條目沒有列出任何參考或來源。

(2015年3月14日)維基百科所有的內容都應該可供查證。

請協助補充可靠來源以改善這篇條目。

無法查證的內容可能會因為異議提出而移除。

在數學中，整數分解（英語：integerfactorization）又稱質因數分解（primefactorization），是將一個正整數寫成幾個因數的乘積。

例如，給出45這個數，它可以分解成 {\displaystyle} 3 2 × 5 {\displaystyle3^{2}\times5} 。

根據算術基本定理，這樣的分解結果應該是獨一無二的。

這個問題在代數學、密碼學、計算複雜性理論和量子計算機等領域中有重要意義。

目次 1因子分解 2實際應用 3當今的新進展 3.1難度與複雜度 4整數分解算法 4.1特殊用途算法 4.2一般用途算法 4.3其他算法 5參見 因子分解編輯 完整的因子列表可以根據因數分解推導出，將冪從零不斷增加直到等於這個數，算出可以整除這個數的所有整數。

例如，因為 45 = {\displaystyle45=\,}   3 2 × 5 {\displaystyle3^{2}\times5}  ，由此可知， 45可以被以下數字因子分解: 30×50=1 30×51=5 31×50=3 31×51=15 32×50=9 32×51=45相對應的，因數分解只包括因數因子。

參見因數分解算法。

實際應用編輯 給出兩個整數，很容易就能將它們兩個相乘。

但是，給出一個大整數(100位數以上的整數)，找出它們的因數就顯得不是那麼容易了。

這就是許多現代密碼系統的關鍵所在。

如果能夠找到解決整數分解問題的快速方法，幾個重要的密碼系統將會被攻破， 包括RSA加密演算法公鑰算法和BlumBlumShub（英語：BlumBlumShub）隨機數發生器。

儘管快速分解是攻破這些系統的方法之一，仍然會有其它的不涉及到分解的其它方法。

所以情形完全可能變成這樣：整數分解問題仍然是非常困難，這些密碼系統卻是能夠很快攻破。

有的密碼系統則能提供更強的保證：如果這些密碼系統被快速破解（即能夠以多項式時間複雜度破解）， 則可以利用破解這些系統的算法來快速地以多項式時間複雜度分解整數。

換句話說，破解這樣的密碼系統不會比整數分解更容易。

這樣的密碼系統包括Rabincryptosystem（英語：Rabincryptosystem）(RSA的一個變體）以及BlumBlumShub（英語：BlumBlumShub）隨機數發生器。

當今的新進展編輯 2005年，作為公共研究一部分的, 有663個二進制數位之長的RSA200（英語：RSAnumbers）已經被一種一般用途的方法所分解。

如果一個大的，有n個二進制數位長度的數,是兩個差不多大小相等的因數的乘積，現在還沒有很好的演算法來以多項式時間複雜度分解它。

這就意味著沒有已知算法可以在O（nk）（k為常數）的時間內分解它。

但是現在的算法也是比O(en)快的。

換句話說，現在我們已知最好的算法比指數數量級時間要快，比多項式數量級時間要慢。

已知最好的漸近線運行時間是普通數體篩選法（GNFS）。

時間是： O ( exp ⁡ ( ( 64 9 n ) 1 3 ( log ⁡ n ) 2 3 ) ) {\displaystyle\mathrm{O}\left(\exp\left(\left({\frac{64}{9}}n\right)^{\frac{1}{3}}(\logn)^{\frac{2}{3}}\right)\right)}  對於平常的計算機，GNFS是我們已知最好的對付n個二進制數位大因數的方法。

不過，對於量子計算機，彼得·秀爾在1994年發現了一種可以用多項式時間來解決這個問題的算法。

如果大的量子計算機建立起來，這將對密碼學有很重要的意義。

這個算法在時間上只需要O(n3)，空間只要O(n)就可以了。

構造出這樣一個算法只需要2n個量子位。

2001年，第一個7量子位的量子計算機第一個運行這個算法，它分解的數是15。

難度與複雜度編輯 現在還不確切知道整數分解屬於哪個複雜度類。

我們知道這個問題的判定問題形式（「請問N是否有一個比M小的因數?」）是在NP與反NP之中。

因為不管是答案為是或不是，我們都可以用一個質因數以及該質因數的質數證明來驗證這個答案。

由秀爾演算法可知，這個問題在BQP中。

大部份的人則懷疑這個問題不在P、NP完全、以及反NP完全這三個複雜性類別中。

如果這個問題可以被證明為NP完全或反NP完全，則我們便可推得NP=反NP。

這將會是個很震撼的結果，也因此大多數人猜想整數分解這個問題不在上述的複雜性類別中。

也有許多人嘗試去找出多項式時間的演算法來解決這個問題，但是都尚未成功，因此這個問題也被多數人懷疑不在P中。

有趣的是，判定一個整數是否是質數則比分解該整數簡單許多。

AKS算法証明前者可以在多項式時間中解決。

測試一個數是否為質數是RSA演算法中非常重要的一環，因為它在一開始的時候需要找很大的質數。

整數分解算法編輯 特殊用途算法編輯 一個特別的因子分解算法的運行時間依賴它本身的未知因子：大小，類型等等。

在不同的算法之間運行時間也是不同的。

試除法 車輪分解（英語：Wheelfactorization） 波拉德RHO算法（英語：Pollard'srhoalgorithm） 代數群因式分解算法（英語：Algebraic-groupfactorisationalgorithms），其中包括Pollard'sp − 1算法（英語：Pollard'sp−1algorithm）、Williams'p + 1算法（英語：Williams'p+1algorithm）和Lenstra橢圓曲線分解法（英語：Lenstraellipticcurvefactorization） 費馬質數判定法 歐拉因式分解法（英語：Euler'sfactorizationmethod） 特殊數體篩選法（英語：Specialnumberfieldsieve）一般用途算法編輯 一般用途算法的運行時間僅僅依賴要分解的整數的長度。

這種算法可以用來分解RSA數。

大部分一般用途算法基於平方同餘方法。

Dixon算法（英語：Dixon'salgorithm） 連分數分解法（英語：Continuedfractionfactorization）（CFRAC） 二次篩選法 有理篩選法 普通數體篩選法 Shanks'squareformsfactorization（英語：Shanks'squareformsfactorization）（SQUFOF）其他算法編輯 秀爾算法參見編輯  數學主題 質因數表 取自「https://zh.wikipedia.org/w/index.php?title=整数分解&oldid=72886469」