本页使用了标题或全文手工转换

整数分解

维基百科,自由的百科全书
跳转至: 导航搜索

數學中,整數分解質因數分解)問題是指:給出一個正整數,將其寫成幾個因數的乘積。例如,給出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二進制數位長度的數是兩個差不多大小相等的因數的乘積,現在還沒有很好的算法來以多項式時間複雜度分解它。

這就意味著沒有已知算法可以在Onk)(k為常數)的時間內分解它。但是現在的算法也是比Θ(en)快的。換句話說,現在我們已知最好的算法比指數數量級時間要快,比多項式數量級時間要慢。已知最好的漸近線運行時間是普通數域篩選法(GNFS)。時間是:


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

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

難度與複雜度[编辑]

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

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

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

例如梅森合数分解一些进展[编辑]

  1,p=4r+3,如果8r+7也是素数,则:(8r+7)|(2^{p}-1)。

“|”表示整除,3|15,表示15被3整除。

即(2p+1)|(2^{p}-1);

例如:23|(2^{11}-1);11=4×2+3,23=8×2+7;

47|(2^{23}-1);23=4×5+3,47=8×5+7;

167|(2^{83}-1); 83=4×20+3,167=8×20+7;

...

  2,p=2^{n}3^{2}+1,则(6p+1)|(2^{p}-1)。

例如:223|(2^{37}-1),37=2^{2}3^{2}+1,223=6×37+1;

439|(2^{73}-1),73=2^{3}3^{2}+1,439=6×73+1;

3463|(2^{577}-1) ,577=2^{6}3^{2}+1,3463=6×577+1.

...

  3,p=2^{n}3^{m}5^{s}-1,则(8p+1)|(2^{p}-1);

例如:233|(2^{29}-1);,29=2^{1}3^{1}5^{1}-1,233=8×29+1

1433|(2^{179}-1); ,179=2^{2}3^{2}5^{1}-1,1433=8×179+1;

1913|(2^{239}-1);,239=2^{4}3^{1}5^{1}-1,1913=8×239+1.

...

  还有一些梅森数分解取得进展,不再一一叙述。

整數分解算法[编辑]

特殊用途算法[编辑]

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

一般用途算法[编辑]

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

其他算法[编辑]

參見[编辑]