给出两个大素数，很容易就能将它们两个相乘。但是，给出它们的乘积，找出它们的因子就显得不是那么容易了。这就是许多现代密码系统的关键所在。如果能够找到解决整数分解问题的快速方法，几个重要的密码系统将会被攻破，包括RSA公钥算法和Blum Blum Shub随机数发生器。
整数分解
百科内容来自于：
实际应用
当今的新进展
2005年，作为公共研究一部分的有663个二进制数位之长的RSA-200已经被一种一般用途的方法所分解。
这就意味着没有已知算法可以在O(
n)（
k为常数）的时间内分解它。但是现在的算法也是比Θ(e)快的。换句话说，现在我们已知最好的算法比指数数量级时间要快，比多项式数量级时间要慢。已知最好的渐近线运行时间是普通数域筛选法(GNFS)。时间是：
对于平常的计算机，GNFS是我们已知最好的对付
n个二进制数位大素数的方法。不过，对于量子计算机， 彼得·肖 在1994年发现了一种可以用多项式时间来解决这个问题的算法。如果大的量子计算机建立起来，这将对密码学有很重要的意义。这个算法在时间上只需要O(
n)，空间只要O(
n)就可以了。 构造出这样一个算法只需要2
n量子位。2001年，第一个7量子位的量子计算机第一个运行这个算法，它分解的数是15。
难度与复杂度
现在还不确切知道整数分解属于那个复杂性等级。
我们知道这个问题的判定问题形式（“请问
N是否有一个比
M小的因子?”）是在NP与co-NP之中。因为不管是答案为是或不是，我们都可以用一个质因子以及该质因子的质数证明来验证这个答案。由 肖 的算法，我们得知这个问题在BQP中。大部份的人则怀疑这个问题不在P、NP-Complete、以及co-NP-Complete这三个复杂性类别中。如果这个问题可以被证明为NP-Complete或co-NP-Complete，则我们便可推得NP=co-NP。这将会是个很震撼的结果，也因此大多数人猜想整数分解这个问题不在上述的复杂性类别中。也有许多人尝试去找出多项式时间的算法来解决这个问题，但是都尚未成功，因此这个问题也被多数人怀疑不在P中。
整数分解算法
图书信息
内容简介
作者简介
图书目录
丛书序言
序言
1 开头小引、数论难题
2 整数分解、古老问题
3 中华神算、制胜出奇
4 库克论题、辨别难易
5 质数分布、深刻神秘
6 椭圆曲线、标新立异
7 二次筛法、值得称道
8 数域筛法、独占鳌头
9 柳暗花明、密码新法
10 孙子兵法、兵不厌诈
11 参考文献、阅读建议
$firstVoiceSent
- 来自原声例句