整数分解
维基百科，自由的百科全书
數學中，整數分解(質因數分解)問題是指：給出一個正整數，將其寫成幾個素數的乘積。例如，給出45這個數，它可以分解成32 ×5。根據算術基本定理，這樣的分解結果應該是獨一無二的。這個問題在代數學、密碼學、計算複雜性理論和量子計算機等領域中有重要意義。
目录 |
[编辑] 因子分解
完整的因子列表可以根據素數分解推導出，將冪從零不斷增加直到等於這個數。例如，因為45= 32×51，45可以被30 ×50，30×51，31×50，31×51，32×50，和32×51，或者 1，5，3，9，15，和 45整除。相對應的，素數分解只包括素數因子。參見素數分解算法。
[编辑] 實際應用
給出兩個大素數，很容易就能將它們兩個相乘。但是，給出它們的乘積，找出它們的因子就顯得不是那麼容易了。這就是許多現代密碼系統的關鍵所在。如果能夠找到解決整數分解問題的快速方法，幾個重要的密碼系統將會被攻破，包括RSA公鑰算法和Blum Blum Shub隨機數發生器。
儘管快速分解是攻破這些系統的方法之一，仍然會有其它的不涉及到分解的其它方法。所以情形完全可能變成這樣：整數分解問題仍然是非常困難，這些密碼系統卻是能夠很快攻破。有的密碼系統則能提供更強的保證：如果這些密碼系統被快速破解（即能夠以多項式時間複雜度破解），則可以利用破解這些系統的算法來快速地（以多項式時間複雜度）分解整數。換句話說，破解這樣的密碼系統不會比整數分解更容易。這樣的密碼系統包括 Rabin密碼系統（RSA的一個變體），以及 Blum Blum Shub 隨機數發生器。
[编辑] 當今的新進展
2005年，作為公共研究一部分的有663個二進制數位之長的RSA-200已經被一種一般用途的方法所分解。
如果一個大的，有n個二進制數位長度的數是兩個差不多大小相等的素數的乘積，現在還沒有很好的算法來以多項式時間複雜度分解它。
這就意味著沒有已知算法可以在O(nk)（k為常數）的時間內分解它。但是現在的算法也是比Θ(en)快的。換句話說，現在我們已知最好的算法比指數數量級時間要快，比多項式數量級時間要慢。已知最好的漸近線運行時間是普通數域篩選法(GNFS)。時間是：
對於平常的計算機，GNFS是我們已知最好的對付n個二進制數位大素數的方法。不過，對於量子計算機， 彼得·肖 在1994年發現了一種可以用多項式時間來解決這個問題的算法。如果大的量子計算機建立起來，這將對密碼學有很重要的意義。這個算法在時間上只需要O(n3)，空間只要O(n)就可以了。 構造出這樣一個算法只需要2n量子位。2001年，第一個7量子位的量子計算機第一個運行這個算法，它分解的數是15。
[编辑] 難度與複雜度
現在還不確切知道整數分解屬於那個複雜性等級。
我們知道這個問題的判定問題形式（「請問N是否有一個比M小的因數?」）是在NP與co-NP之中。因為不管是答案為是或不是，我們都可以用一個質因數以及該質因數的質數證明來驗證這個答案。由 肖 的演算法，我們得知這個問題在BQP中。大部份的人則懷疑這個問題不在P、NP-Complete、以及co-NP-Complete這三個複雜性類別中。如果這個問題可以被證明為NP-Complete或co-NP-Complete，則我們便可推得NP=co-NP。這將會是個很震憾的結果，也因此大多數人猜想整數分解這個問題不在上述的複雜性類別中。也有許多人嘗試去找出多項式時間的演算法來解決這個問題，但是都尚未成功，因此這個問題也被多數人懷疑不在P中。
有趣的是，當判定問題為「N是否為一合數？」則比要找出N的因數這個問題要簡單的許多。有文章[1]指出前者這個問題可以在多項式時間中解決（其中n為N的位數）。若允許微小的失誤，更有許多的隨機化演算法可以非常快速的測試出一個數是否為質數。測試一個數是否質數不難，這是RSA演算法中非常重要的一環，因為它在一開始的時後需要找很大的質數。（參見素性測試）。
[编辑] 整數分解算法
[编辑] 特殊用途算法
一個特別的因子分解算法的運行時間依賴它本身的未知因子：大小，類型等等。在不同的算法之間運行時間也是不同的。
[编辑] 一般用途算法
一般用途算法的運行時間僅僅依賴要分解的整數的長度。這種算法可以用來分解RSA數。大部分一般用途算法基於平方同余方法。
- Dixon's algorithm
- 連分數分解法 (CFRAC)
- 二次篩選法
- 普通數域篩選法
