质因数分解算法

数学中，整数分解（素因数分解）问题是指：给出一个正整数，将其写成几个约数的乘积。例如，给出45这个数，它可以分解成32 ×5。根据算术基本定理，这样的分解结果应该是独一无二的。这个问题在代数学、密码学、计算复杂性理论和量子计算机等领域中有重要意义。
2005年，作为公共研究一部分的有663个二进制数位之长的RSA-200已经被一种一般用途的方法所分解。

如果一个大的，有n个二进制数位长度的数是两个差不多大小相等的约数的乘积，现在还没有很好的算法来以多项式时间复杂度分解它。

这就意味着没有已知算法可以在O（nk）（k为常数）的时间内分解它。但是现在的算法也是比Θ(en)快的。换句话说，现在我们已知最好的算法比指数数量级时间要快，比多项式数量级时间要慢。已知最好的渐近线运行时间是普通数域筛选法(GNFS)。时间是：

对于平常的计算机，GNFS是我们已知最好的对付n个二进制数位大约数的方法。不过，对于量子计算机， 彼得·秀尔在1994年发现了一种可以用多项式时间来解决这个问题的算法。如果大的量子计算机建立起来，这将对密码学有很重要的意义。这个算法在时间上只需要O(n3)，空间只要O(n)就可以了。 构造出这样一个算法只需要2n量子位。2001年，第一个7量子位的量子计算机第一个运行这个算法，它分解的数是15

如果想获得最新消息，请你上wikipedia百科，英文版。