整数分解

整数分解（英语：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算法中非常重要的一环，因为它在一开始的时候需要找很大的素数。