整数分解

完整的因子列表可以根據因數分解推導出，將冪從零不斷增加直到等於這個數，算出可以整除這個數的所有整數。
例如，因為${\displaystyle 45=\,}$${\displaystyle 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隨機數發生器。

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

2005年，作為公共研究一部分的, 有663個二進制數位之長的RSA200已經被一種一般用途的方法所分解。

如果一個大的，有n個二進制數位長度的數,是兩個差不多大小相等的因數的乘積，

現在還沒有很好的演算法來以多項式時間複雜度分解它。

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

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

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

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

時間是：

${\displaystyle \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。

• 質因數表