《整数分解》是2009年1月1日科学出版社来自出版的图书，作者是颜松远。
来自整数分解，又称质因子分解。在数学中，整数分解问题是指:给出一个正整数，将其写成几个素数的乘积。例如，给出45这个数，它可以分解成3^2×5。360百科根据算术基本定理，这样的分解结果应该是独一无二的。这个问题在代数学、密码学、计算复杂性理论和量子计算机等领域中有重要意义。这是一本为大学生和研究生而写的通俗读物，但由于它的起点较低，因此也牛六家层紧括紧乎效销弦适合于用作中小学生的课外读物(略过有关数学公式);同时又由于它的终点较高且理论曲折深刻，涉及很多几十年、几百年乃至数千年悬而未决的数学难题，因而师信属纸评举占对广大数学、计算机科学和密码学等专家也是一本不可多得的读物。
宗传明，1993年维也纳科学技术大学获博士学位，1997年晋升为中国科学院式州待环胶往女语害口数学研究所研究员，2000年始任北京大学数学科学学院教授。曾在维也纳、巴云兰孙明口介面非并黎、苏黎世、伦敦、柏小补基另林、伯克利等学习工作近十年。在剑桥大学出版社和斯普林格出版社出版争标充模长子粒执府班专著三部。曾荣获von Pre尔田规举右脚田chtl奖章(奥地利)、陈省身数学奖、中国青年科技奖、教育部自然科学一等奖、茅以升青年科技奖出最科越会岩等多项荣誉。
丛书设位南带调序言
序言
1 开来自头小引、数论难题
2 整数360百科分解、古老问题
3 中华神算、制胜出奇
4 库克论题、辨别难易
5 质数分布、深节乙有从倒轻永裂调刻神秘
6 椭圆曲线、标新立异
7 二次筛法、值得称道
鲁她航英商继8 数域筛法、独占鳌头
9 柳暗花明、密码新法
10 孙子兵法、兵不厌诈
11 参考文献、阅读建议
完整的直便打林争便推白因子列表可以根据素斯似管雨真三盐数分解推导出，将幂从零不断增加直到等于这个数。例如，因为45= 3^2×5，所以45能被 1，5，3，道培北际月加包把算输九9，15，和 45整除。相对应的，素数分解只包括素数因子。参见素数分解算法。
给出两个大素买防金斤皇数，很容易就能将它们两个相乘。但是，给出它们的乘积，找出它们的因子就显得不是那么容易了。这就是许多现代密码系统的关键所在。如果能够找到解决整数分解问题的快速方法，几个重要过过零酒了众模的密码系统将会被攻破，包括RSA公钥算法和Blu策项燃叫况太顺m Blum Shub随机鱼建部千重数发生器。
尽管快速分解是攻破这些系统的方法之一，仍然会有其它的不涉及到分解的其它方法。所以情形完全可能变成这样:整数分解问题仍然是非常困难，这些密码系统却是能够很快攻破。有的密码系统则能提供更强的条补尔顾攻么味掌胞保证:如果这些密码系统被快速破解(即能够以多项式时间复杂度破解)，则可以利用破解这些系统的算法来快速地(以多项式时间复杂度)分解整数。换句话说，破解这样的密码系统不会比整数分解更容易。这样的密码刻阶关系统包括Rabin密码系统(RSA的一个变体)，以及 Blum Blum Shub随机数发生器。
2005年，作为公共研究一部分的有663个二进制数位之长的RSA-20色0已经被一种一般用途的方法所分解。
如果一个大的，有n个二进制数位长度的数是两个差不多大小相等的素数的乘积，还没有很好的算法来以多项式时间复杂度分解它。
这就意味着没有已知算法可以在O(n)(k为料常数)的时间内分解它。但是算法也是比Θ(e)快的。换句话说，现在我妒架们已知最好的算法比指数数量级时间要快，比多项时著攻江是蒸培式数量级时间要慢。已知最好的渐近线运行时间是普通数域筛选法(GNFS)。时间是:
对于平常的计算机，GNFS是我们已知最好的对付n个二进设增卷早里吗入慢纪甲制数位大素数的方法。不过，对于量子计算机，彼得·肖在1994年发现了一种席搞圆术法握据谓期新可以用多项式时间来解决这个问题的算法。如果大的量子计算机建立起来，这将对密码学有很重要的意义。这个算法在时间上只需要O(n)，空间只要O(n)就可以了。 构造出这样一个算法只需要2n量子位。2001年，第一个7量子位的量子计算机第一个运行这个算法，它分解的数是15。
复杂性等级。
我们知道这个问题的判定问题形式("请问N是否有一个比M小的因子?")是在NP与co-NP之中。因为不管是答案为是或不是，我们都可以用一个质因子以及该质因子的质数证明来验证这个答案。由 肖 的算法，我们得知这个问题在BQP中。大部份的人则怀疑这个问题不在P、NP-Complete、以及co-NP-Complete这三个复杂性类别中。如果这个问题可以被证明为NP-Complete或co-NP-Complete，则我们便可推得NP=co-NP。这将会是个很震撼的结果，也因此大多数人猜想整数分解这个问题不在上述的复杂性类别中。也有许多人尝试去找出多项式时间的算法来解决这个问题，但是都尚未成功，因此这个问题也被多数人怀疑不在P中。
有趣的是，当判定问题为"N是否为一合数?"则比要找出N的因子这个问题要简单的许多。有文章[1]指出前者这个问题可以在多项式时间中解决(其中n为N的位数)。若允许微小的失误，更有许多的随机化算法可以非常快速的测试出一个数是否为质数。测试一个数是否质数不难，这是RSA算法中非常重要的一环，因为它在一开始的时后需要找很大的质数。(参见素性测试)。
一个特别的因子分解算法的运行时间依赖它本身的未知因子:大小，类型等等。在不同的算法之间运行时间也是不同的。
试除法、Lenstra 椭圆曲线分解法、费马分解方法、特殊数域筛选法
一般用途算法的运行时间仅仅依赖要分解的整数的长度。这种算法可以用来分解RSA数。大部分一般用途算法基于平方同余方法。
Dixon's algorithm连分数分解法(CFRAC)二次筛选法普通数域筛选法
Shor's algorithm(量子电脑)
关注微信