整數分解

整數分解（英語：integer factorization）又稱整數因式分解、整數因子分解，或整數因子化^[1]，在數論中，「整數的因數分解」是指在可能的情況下，將一個正整數分解為更小整數的乘積，即寫成幾個因數的乘積。若進一步限制因數為質數，則這個過程稱為質因數分解（英語：prime factorization），其中包括檢定給定整數是否為質數。

例如，給出45這個數，它可以分解成 $3^{2}\times 5$ 。根據算術基本定理，這樣的分解結果應該是獨一無二的。這個問題在代數學、密碼學、計算複雜性理論和量子計算機等領域中有重要意義。

因子分解

完整的因子列表可以根據因數分解推導出，將冪從零不斷增加直到等於這個數，算出可以整除這個數的所有整數。
例如，因為 $45=\,$ $3^{2}\times 5$ ，由此可知，
45可以被以下數字因子分解:

3⁰ ×5⁰ =1
3⁰×5¹ =5
3¹×5⁰ =3
3¹×5¹ =15
3²×5⁰ =9
3²×5¹ =45

相對應的，因數分解只包括因數因子。參見因數分解算法。

實際應用

給出兩個整數，很容易就能將它們兩個相乘。但是，給出一個大整數(100位數以上的整數)，找出它們的因數就顯得不是那麼容易了。這就是許多現代密碼系統的關鍵所在。如果能夠找到解決整數分解問題的快速方法，幾個重要的密碼系統將會被攻破，包括RSA加密演算法公鑰算法和Blum Blum Shub（英語：Blum Blum Shub）隨機數發生器。儘管快速分解是攻破這些系統的方法之一，仍然會有其它的不涉及到分解的其它方法。所以情形完全可能變成這樣：整數分解問題仍然是非常困難，這些密碼系統卻是能夠很快攻破。有的密碼系統則能提供更強的保證：如果這些密碼系統被快速破解（即可以以多項式時間複雜度破解），則可以利用破解這些系統的算法來快速地以多項式時間複雜度分解整數。換句話說，破解這樣的密碼系統不會比整數分解更容易。這種的密碼系統包括Rabin cryptosystem（英語：Rabin cryptosystem）(RSA的一個變體）以及Blum Blum Shub（英語：Blum Blum Shub）隨機數發生器。

當今的新進展

2005年，作為公共研究一部分的，有663個二進制數位之長的RSA200（英語：RSA numbers）已經被一種一般用途的方法所分解。如果一個大的，有n個二進制數位長度的數，是兩個差不多大小相等的因數的乘積，現在還沒有很好的演算法來以多項式時間複雜度分解它。即意味著沒有已知算法可以在O（n^k）（k為常數）的時間內分解它，但是現在的算法也是比O(eⁿ)快的。亦即，現在我們已知最好的算法比指數數量級時間要快，比多項式數量級時間要慢。已知最好的漸近線運行時間是普通數體篩選法（GNFS）。

時間是：

\mathrm {O} \left(\exp \left(\left({\frac {64}{9}}n\right)^{\frac {1}{3}}(\log n)^{\frac {2}{3}}\right)\right)

對於平常的計算機，GNFS是我們已知最好的對付n個二進制數位大因數的方法。不過，對於量子計算機，彼得·秀爾在1994年發現了一種可以用多項式時間來解決這個問題的算法。如果大的量子計算機建立起來，會對密碼學有很重要的意義。這個算法在時間上只需要O(n³)，空間只要O(n)就可以了。構造出這樣一個算法只需要2n個量子位。2001年，第一個7量子位的量子計算機第一個運行這個算法，它分解的數是15。

難度與複雜度

現在還不確切知道整數分解屬於哪個複雜度類。我們知道這個問題的判定問題形式（「請問N是否有一個比M小的因數?」）是在NP與反NP之中。因為不管是答案為是或不是，我們都可以用一個質因數以及該質因數的質數證明來驗證這個答案。由秀爾演算法可知，這個問題在BQP中。大部份的人則懷疑這個問題不在P、NP完全、以及反NP完全這三個複雜性類別中。如果這個問題可以被證明為NP完全或反NP完全，則我們便可推得NP=反NP。這將會是個很震撼的結果，也因此大多數人猜想整數分解這個問題不在上述的複雜性類別中。也有許多人嘗試去找出多項式時間的演算法來解決這個問題，但是都尚未成功，因此這個問題也被多數人懷疑不在P中。

但判定一個整數是否是質數比分解該整數簡單許多。AKS算法証明前者可以在多項式時間中解決。測試一個數是否為質數是RSA演算法中非常重要的一環，因為它在一開始的時候需要找很大的質數。

整數分解算法

特殊用途算法

一個特別的因數分解算法的運行時間依賴它本身的未知因子：大小，類型等等。在不同的算法之間運行時間也是不同的。

試除法
輪式因數分解法（英語：Wheel factorization）
波拉德RHO算法（英語：Pollard's rho algorithm）
代數群因式分解算法（英語：Algebraic-group factorisation algorithms），其中包括Pollard's p − 1算法（英語：Pollard's p − 1 algorithm）、Williams' p + 1算法（英語：Williams' p + 1 algorithm）和Lenstra橢圓曲線分解法（英語：Lenstra elliptic curve factorization）
費馬質數判定法
歐拉因式分解法
特殊數體篩選法（英語：Special number field sieve）

一般用途算法

一般用途算法的運行時間僅僅依賴要分解的整數的長度。這種算法可以用來分解RSA數。大部分一般用途算法基於平方同餘方法。

Dixon算法（英語：Dixon's algorithm）
連分數分解法（英語：Continued fraction factorization）（CFRAC）
二次篩選法
有理篩選法
普通數體篩選法
Shanks' square forms factorization（英語：Shanks' square forms factorization）（SQUFOF）

其他算法

秀爾算法

參見

^ 存档副本. [2023-08-14]. （原始內容存檔於2023-08-14）.

[1] 存档副本. [2023-08-14]. （原始內容存檔於2023-08-14）.

[1]

閱論編和因數有關的整數分類
簡介	質因數分解因數元因數除數函數質因數算術基本定理
依因數分解分類	質數合數半質數普洛尼克數楔形數無平方數因數的數冪數質數冪平方數立方數次方數阿喀琉斯數光滑數正規數粗糙數不尋常數
依因數和分類	完全數殆完全數准完全數多重完全數 Hemiperfect數 Hyperperfect number（英語：Hyperperfect number）超完全數元完全數半完全數本原半完全數實際數
有許多因數	過剩數本原過剩數高過剩數超過剩數可羅薩里過剩數高合成數 Superior highly composite number（英語：Superior highly composite number）奇異數
和真因子和數列有關	不可及數相親數交際數婚約數
其他	虧數友誼數孤獨數卓越數歐爾調和數佩服數節儉數等數位數奢侈數

閱論編數論算法
質數測試	AKS APR（英語：Adleman–Pomerance–Rumely primality test） Baillie–PSW（英語：Baillie–PSW primality test）橢圓曲線（英語：Elliptic curve primality） Pocklington（英語：Pocklington primality test）費馬盧卡斯（英語：Lucas primality test）盧卡斯-萊默 Lucas–Lehmer–Riesel（英語：Lucas–Lehmer–Riesel test）普羅斯 Pépin（英語：Pépin's test）二次Frobenius（英語：Quadratic Frobenius test） Solovay–Strassen（英語：Solovay–Strassen primality test）米勒-拉賓
質數生成（英語：Generating primes）	阿特金篩法（英語：Sieve of Atkin）埃拉托斯特尼篩法 Pritchard篩法（英語：Sieve of Pritchard） Sundaram篩法（英語：Sieve of Sundaram）輪式因數分解法（英語：Wheel factorization）
整數分解	連分數分解 (CFRAC)（英語：Continued fraction factorization） Dixon's（英語：Dixon's factorization method） Lenstra橢圓曲線 (ECM)（英語：Lenstra elliptic-curve factorization）歐拉因式分解法波拉德ρ算法（英語：Pollard's rho algorithm） p − 1（英語：Pollard's p − 1 algorithm） p + 1（英語：Williams's p + 1 algorithm）二次篩選法普通數體篩選法特殊數體篩選法 (SNFS)（英語：Special number field sieve）有理篩選法費馬因式分解法（英語：Fermat's factorization method） Shanks二次形式（英語：Shanks's square forms factorization）試除法秀爾演算法
乘法算法	古埃及乘算（英語：Ancient Egyptian multiplication）長乘法卡拉楚巴算法圖姆-庫克算法頌哈吉-施特拉森演算法富爾算法（英語：Fürer's algorithm）
歐幾里德除法除法算法	二進制（英語：Binary division）倍塊法（英語：Chunking (division)） Fourier（英語：Fourier division） Goldschmidt（英語：Goldschmidt division） Newton-Raphson（英語：Newton–Raphson division）長除法短除法 SRT
離散對數	大步小步算法波拉德ρ算法 Pollard kangaroo（英語：Pollard's kangaroo algorithm） Pohlig–Hellman（英語：Pohlig–Hellman algorithm） Index calculus（英語：Index calculus algorithm） Function field sieve（英語：Function field sieve）
最大公因數	二進制最大公因數算法（英語：Binary GCD algorithm）輾轉相除法擴展歐幾里得算法 Lehmer's（英語：Lehmer's GCD algorithm）
二次剩餘	Cipolla（英語：Cipolla's algorithm） Pocklington's（英語：Pocklington's algorithm） Tonelli–Shanks（英語：Tonelli–Shanks algorithm） Berlekamp（英語：Berlekamp–Rabin algorithm） Kunerth（英語：Kunerth's algorithm）
其他算法	Chakravala（英語：Chakravala method） Cornacchia（英語：Cornacchia's algorithm）整數關係（英語：Integer relation algorithm）（LLL（英語：Lenstra–Lenstra–Lovász lattice basis reduction algorithm）；KZ（英語：Korkine–Zolotarev lattice basis reduction algorithm））平方求冪整數平方根模冪運算蒙哥馬利算法 Schoof（英語：Schoof's algorithm）特拉亨伯格系統（英語：Trachtenberg system）
斜體表示該算法只適用於特殊形式的數字