整数分解- 维基百科，自由的百科全书 - Wikipedia

在数学中，整数分解（英语：integer factorization）又称素因数分解（prime factorization），是将一个正整数写成几个约数的乘积。

例如，给出45这个数，它可以分解成 ... 整数分解 维基百科，自由的百科全书 跳到导航 跳到搜索   提示：此条目的主题不是整数分拆。

此条目没有列出任何参考或来源。

(2015年3月14日)维基百科所有的内容都应该可供查证。

请协助补充可靠来源以改善这篇条目。

无法查证的内容可能会因为异议提出而移除。

在数学中，整数分解（英语：integerfactorization）又称素因数分解（primefactorization），是将一个正整数写成几个约数的乘积。

例如，给出45这个数，它可以分解成 {\displaystyle} 3 2 × 5 {\displaystyle3^{2}\times5} 。

根据算术基本定理，这样的分解结果应该是独一无二的。

这个问题在代数学、密码学、计算复杂性理论和量子计算机等领域中有重要意义。

目录 1因子分解 2实际应用 3当今的新进展 3.1难度与复杂度 4整数分解算法 4.1特殊用途算法 4.2一般用途算法 4.3其他算法 5参见 因子分解[编辑] 完整的因子列表可以根据约数分解推导出，将幂从零不断增加直到等于这个数，算出可以整除这个数的所有整数。

例如，因为 45 = {\displaystyle45=\,} 3 2 × 5 {\displaystyle3^{2}\times5} ，由此可知， 45可以被以下数字因子分解: 30×50=1 30×51=5 31×50=3 31×51=15 32×50=9 32×51=45 相对应的，约数分解只包括约数因子。

参见约数分解算法。

实际应用[编辑] 给出两个整数，很容易就能将它们两个相乘。

但是，给出一个大整数(100位数以上的整数)，找出它们的约数就显得不是那么容易了。

这就是许多现代密码系统的关键所在。

如果能够找到解决整数分解问题的快速方法，几个重要的密码系统将会被攻破， 包括RSA加密算法公钥算法和BlumBlumShub（英语：BlumBlumShub）随机数发生器。

尽管快速分解是攻破这些系统的方法之一，仍然会有其它的不涉及到分解的其它方法。

所以情形完全可能变成这样：整数分解问题仍然是非常困难，这些密码系统却是能够很快攻破。

有的密码系统则能提供更强的保证：如果这些密码系统被快速破解（即能够以多项式时间复杂度破解）， 则可以利用破解这些系统的算法来快速地以多项式时间复杂度分解整数。

换句话说，破解这样的密码系统不会比整数分解更容易。

这样的密码系统包括Rabincryptosystem（英语：Rabincryptosystem）(RSA的一个变体）以及BlumBlumShub（英语：BlumBlumShub）随机数发生器。

当今的新进展[编辑] 2005年，作为公共研究一部分的, 有663个二进制数位之长的RSA200（英语：RSAnumbers）已经被一种一般用途的方法所分解。

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

这就意味着没有已知算法可以在O（nk）（k为常数）的时间内分解它。

但是现在的算法也是比O(en)快的。

换句话说，现在我们已知最好的算法比指数数量级时间要快，比多项式数量级时间要慢。

已知最好的渐近线运行时间是普通数域筛选法（GNFS）。

时间是： O ( exp ⁡ ( ( 64 9 n ) 1 3 ( log ⁡ n ) 2 3 ) ) {\displaystyle\mathrm{O}\left(\exp\left(\left({\frac{64}{9}}n\right)^{\frac{1}{3}}(\logn)^{\frac{2}{3}}\right)\right)} 对于平常的计算机，GNFS是我们已知最好的对付n个二进制数位大约数的方法。

不过，对于量子计算机，彼得·秀尔在1994年发现了一种可以用多项式时间来解决这个问题的算法。

如果大的量子计算机建立起来，这将对密码学有很重要的意义。

这个算法在时间上只需要O(n3)，空间只要O(n)就可以了。

构造出这样一个算法只需要2n个量子位。

2001年，第一个7量子位的量子计算机第一个运行这个算法，它分解的数是15。

难度与复杂度[编辑] 现在还不确切知道整数分解属于哪个复杂度类。

我们知道这个问题的判定问题形式（“请问N是否有一个比M小的约数?”）是在NP与反NP之中。

因为不管是答案为是或不是，我们都可以用一个素因数以及该素因数的素数证明来验证这个答案。

由秀尔算法可知，这个问题在BQP中。

大部分的人则怀疑这个问题不在P、NP完全、以及反NP完全这三个复杂性类别中。

如果这个问题可以被证明为NP完全或反NP完全，则我们便可推得NP=反NP。

这将会是个很震撼的结果，也因此大多数人猜想整数分解这个问题不在上述的复杂性类别中。

也有许多人尝试去找出多项式时间的算法来解决这个问题，但是都尚未成功，因此这个问题也被多数人怀疑不在P中。

有趣的是，判定一个整数是否是素数则比分解该整数简单许多。

AKS算法证明前者可以在多项式时间中解决。

测试一个数是否为素数是RSA算法中非常重要的一环，因为它在一开始的时候需要找很大的素数。

整数分解算法[编辑] 特殊用途算法[编辑] 一个特别的因子分解算法的运行时间依赖它本身的未知因子：大小，类型等等。

在不同的算法之间运行时间也是不同的。

试除法 车轮分解（英语：Wheelfactorization） 波拉德RHO算法（英语：Pollard'srhoalgorithm） 代数群因式分解算法（英语：Algebraic-groupfactorisationalgorithms），其中包括Pollard'sp − 1算法（英语：Pollard'sp−1algorithm）、Williams'p + 1算法（英语：Williams'p+1algorithm）和Lenstra椭圆曲线分解法（英语：Lenstraellipticcurvefactorization） 费马素数判定法 欧拉因式分解法（英语：Euler'sfactorizationmethod） 特殊数域筛选法（英语：Specialnumberfieldsieve） 一般用途算法[编辑] 一般用途算法的运行时间仅仅依赖要分解的整数的长度。

这种算法可以用来分解RSA数。

大部分一般用途算法基于平方同余方法。

Dixon算法（英语：Dixon'salgorithm） 连分数分解法（英语：Continuedfractionfactorization）（CFRAC） 二次筛选法 有理筛选法 普通数域筛选法 Shanks'squareformsfactorization（英语：Shanks'squareformsfactorization）（SQUFOF） 其他算法[编辑] 秀尔算法 参见[编辑] 数学主题 素因数表 查论编和约数有关的整数分类简介 素因数分解 约数 元约数 除数函数 素因数 算术基本定理 依约数分解分类 素数 合数 半素数 普洛尼克数 楔形数 无平方数因数的数 幂数 素数幂 平方数 立方数 次方数 阿喀琉斯数 光滑数 正规数 粗糙数 不寻常数 依约数和分类 完全数 殆完全数 准完全数 多重完全数 Hemiperfect数 Hyperperfectnumber（英语：Hyperperfectnumber） 超完全数 元完全数 半完全数 本原半完全数 实际数 有许多约数 过剩数 本原过剩数 高过剩数 超过剩数 可罗萨里过剩数 高合成数 Superiorhighlycompositenumber（英语：Superiorhighlycompositenumber） 奇异数 和真因子和数列有关 不可及数 相亲数 交际数 婚约数 其他 亏数 友谊数 孤独数 卓越数 欧尔调和数 佩服数 节俭数 等数位数 奢侈数 查论编数论算法素数测试 AKS素性测试 APRtest Baillie–PSW 椭圆曲线素性 Pocklington 费马素性检验 卢卡斯素性测试 卢卡斯-莱默检验法 Lucas–Lehmer–Riesel 普罗斯定理 Pépin's QuadraticFrobeniustest Solovay–Strassen 米勒-拉宾检验 素数生成 阿特金筛法 埃拉托斯特尼筛法 SieveofSundaram Wheelfactorization 整数分解 Continuedfraction(CFRAC) Dixon's Lenstraellipticcurve(ECM) 欧拉因式分解法 波拉德ρ算法 p−1 p+1 二次筛选法 普通数域筛选法 Specialnumberfieldsieve(SNFS) 有理筛选法 费马因式分解法 Shanks'ssquareforms 试除法 秀尔算法 乘法算法 古埃及乘算 长乘法 卡拉楚巴算法 图姆-库克算法 颂哈吉-施特拉森算法 富尔算法 离散对数 大步小步算法 波拉德ρ算法 Pollardkangaroo Pohlig–Hellman Indexcalculus Functionfieldsieve 最大公约数 二进制最大公因数算法 辗转相除法 扩展欧几里得算法 Lehmer's 二次剩余 Cipolla Pocklington's Tonelli–Shanks 其他算法 Chakravala Cornacchia LLL 整数平方根 模幂运算 蒙哥马利算法 Schoof's 斜体表示该算法只适用于特殊形式的数字 取自“https://zh.wikipedia.org/w/index.php?title=整数分解&oldid=72886469” 分类：​整数分解算法计算复杂性假设计算机科学中未解决的问题隐藏分类：​自2015年3月缺少来源的条目含有英语的条目自动计算质因数分解的条目 导航菜单 个人工具 没有登录讨论贡献创建账号登录 命名空间 条目讨论 大陆简体 不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體 查看 阅读编辑查看历史 更多 搜索 导航 首页分类索引特色内容新闻动态最近更改随机条目资助维基百科 帮助 帮助维基社群方针与指引互助客栈知识问答字词转换IRC即时聊天联络我们关于维基百科 工具 链入页面相关更改上传文件特殊页面固定链接页面信息引用本页维基数据项目 打印/导出 下载为PDF可打印版本 在其他项目中 维基共享资源 其他语言 AlemannischالعربيةCatalàČeštinaDanskDeutschEnglishEsperantoEspañolEuskaraفارسیSuomiFrançaisעבריתMagyarBahasaIndonesiaГӀалгӀайÍslenska日本語한국어LëtzebuergeschNederlandsPortuguêsRomânăРусскийSimpleEnglishSlovenščinaСрпски/srpskiSvenskaไทยTürkçeУкраїнськаTiếngViệt 编辑链接