第九章 大整数因子分解算法

因子分解问题（IFP）：找到一个合数N的非平凡因子f（不要求一定是素因子） 如果存在一个算法能检测出N是否为素数，且存在一个算法能找出合数N的非平凡因子f，则存在一个简单的递归算法得到N的素数幂分解。 递归算法如下： 1. 找出N的一个非平凡因子f 2. 算法递归的应用到f和N/f上 3. 将f和N/f的素数幂分解合在一起得到N的素数幂分解

数论里能应用计算机的所有问题中，可能没有比整数因子分解更具影响力的问题了。 ——Hugh C. Williams 大整数分解是许多密码学算法和协议的安全依据，如RSA密码体制。 方法：(1)穷举法； (2)分解算法。

找出N的素因子或判定N是否为素数都不是一件容易的事情，因此，只要可能的话我们都应当尽可能的避免分解大整数。 事实上，存在很多素性检测和整数因子分解算法；唯一的问题是无论是素性检测还是整数因子分解都没有找到有效（确定性多项式时间）算法，也无人能够证明不存在确定性多项式时间算法。

最有效的因子分解算法主要可归为以下两大类： 运行时间主要依赖于待分解整数N的大小，并不十分依赖于找到的因子p的大小。例如： Lehman方法，最坏情况下运行时间的界为 Shanks的平方因子分解方法SQUFOF，具有期望 运行时间 Shanks的类群法，具有运行时间 连分数（CFRAC）方法，在合理假设下具有期望运行时间 其中c为常数（依赖于算法的细节）；通常取c=

多重多项式二次筛法（MPQS），在合理假设下具有期望运行时间 其中c为常数（依赖于算法的细节）；通常取c= 数域筛法（NFS），在合理假设下具有期望运行时间 若用GNFS（NFS的一个普通版本）来分解任意整数N时， 若用SNFS（NFS的一个普通版本）来分解一个特殊的整数N时，其中 ，r和s很小，r >1且e很大， 实质上和渐进上，这个算法的运行速度比已知的任何分解因子的方法都快

运行时间主要依赖于找到的N因子p的大小。（假定 ） 例如： 试除法，具有运行时间 Pollard’s -方法（也被称为Pollard’s “rho”算法），在合理假设下具有期望运行时间 Lenstra的椭圆曲线方法（ECM），在合理假设下具有期望运行时间 其中，c 为常数（依赖于算法的细节）； 项表示对比特长度为 或 的数进行算术运算所用的时间上限；从理论上看可由 代替。

注：以上两类算法都很重要，很难说清是否一种算法就比另一种好。但一般来说，在使用第一类算法之前，先用第二类算法寻找小因子是值得尝试的。 例如，可先用试除法，再利用其他方法（例如NFS）。该事实表明试除法尽管简单，但对整数因子分解来说还是有用的。

9.1 试除法和费马方法 试除法 (5) 退出，停止算法 最简单的因子分解方法，通过尝试n的所有可能的因子来得到n的完整素因子分解式： (3) 计算余数. 且 . 若 ，执行步骤(4). ， 返回步骤(2). (4) 找到因子？若q>k，则 ，且返回步骤(3) (5) 退出，停止算法

10.1 试除法和费马方法 (5) 退出，停止算法 注：算法2.1的一个直接改进是利用试除数的辅助序列： 此序列包含不超过 的所有素数（为方便，也可能包含一些合数）且至少有一个值 算法2.2（试除法分解因子）：此算法用试除法通过试除数的辅助序列来分解整数n>1 (1) 初始化. 输入n，令 ， (2) n=1?若n=1，则执行步骤(5) (3) 计算余数. 且 . 若 ，执行步骤(4). ， 返回步骤(2). (4) 找到因子？若 ，则 ，且返回步骤(3) (5) 退出，停止算法

算法2.2的运行时间为 若在步骤(2)和(3)之间插入素性检测，则运行时间为 或 ，若算法的试除数只包含素数，其中 是n的 第二大素因子. 试除法检测对排除小因子很有效，但不能用来进行完全分解，除非n很小，例如

费马分解因子方法 现假设n为任意奇数（若n为偶数，只须反复除以2直至得到奇数）。 若n=pq，其中p不大于q，均为奇数，则令 (x+y)(x-y) 费马方法试图利用上述想法找出n=pq 费马方法分解n要进行 次算术步骤

9.2 通用整数因子分解方法 通用整数因子分解方法: 是指用此方法分解任何给定大小的整数所用时间与分解任何同样大小的整数所用时间相同。 例如，用通用方法将一个100位的数分解成1位和99位素数的乘积所用时间与将另一个不同的数分解成两个50位的素数所用时间相同。 三种广泛使用的通用整数因子分解方法是： 连分数方法（CFRAC），二次筛法（QS），数域筛法（NFS） 这些方法不依赖于待分解数或它的因子的任何特性 理论依据： 若有两个整数x和y满足 (2.1) 则gcd(x-y, N)和gcd(x+y, N)可能为N的非平凡因子，因为N|(x+y)(x-y)但N不是(x+y)的因子，也不是(x-y)的因子。

同余式(2.1)通常被称为勒让德同余。 用勒让德同余来分解因子只须执行以下两步： (1) 找同余式 的一个非平凡解. (2) 用欧几里得算法计算N的因子 (d, d’)=(gcd(x-y, N), gcd (x+y, N)) . 构造形如式(2.1)的同余式的最好方法是从积累若干个以下形式的同余式开始的： (2.2) 将这样一些同余式相乘以便在同余号两边都产生平方项。

基于这种思想，CFRAC、QS和NFS共有的诀窍就是找出以下形式的同余式（也叫关系式）： (2.3) 其中每个 均为“小”素数（所有这种 ，构成一个因子基，用FB表示）。若能找到足够多的这种同余式，则有希望找到以下形式的关系式： (2.4) 其中 为1或0，从而有 (2.5) 其中 显然，现在有 ，又若 不成立，则N可被分解。

9.2.1 连分数法 连分数法(CFRAC)可能是第一个现代通用的因子分解方法。最初的思想可能要追溯到20世纪20年代M.Kraitchik，甚至更早到A.M.Legendre. 20世纪30年代D.H.lLehmer和R.E.Powers用这种思想设计了一种新技术，大约40年后 ，M.A.Morrison和J.Brillhart第一个将这种思想应用到计算机上，在1970年9月13日成功分解出第七个 费马数 CFRAC法是寻找较小的|W|值，使得 有解 。因为W很小，确切的说， ，所以它很可能成为 因子基FB中素数的乘积。

9.2.1 连分数法 CFRAC方法的思想： 若W很小，且 ，则对某个k和d，有 ，因而 也会很小。 换句话说，有理数x/d逼近 。使人联想到 的连分数展开式，因为实数的连分数展开式可以给出该实数 好的有理数逼近。

9.2.1 连分数法 猜想（ CFRAC方法的复杂度 ）：在某些合理的假设下， CFRAC方法分解整数Ｎ的时间为 注：这是一个猜想，而非定理，因为它的成立依赖于某些未被证明的假设。

9.2.2 二次筛法 二次筛法（QS）的想法由美国Carl Pomerance于1982年首先提出的 二次筛法使用最广泛的变种是由Peter Montgometry提出的多重多项式二次筛法（MPQS） 二次筛法为分解大数而设计 二次筛法的最新纪录是对某个129位数的RSA-129的分解（Rivest于1977年预测适用当时最快的计算机和最好的算法分解像RSA-129 大小的数所需运行时间为　　　　年）

9.2.2 二次筛法 方法： 因子基FB的选择：

9.2.2 二次筛法 例： N=4033的二次筛法 解：第一步，选择因子基FB={2，3，7，13，17，19} （因为　　　　　　　　，即5和11不能除尽任何 ，所以5、11不在因子基中。 ） 第二步，通过对从x=64(= )到73的Q(x) 除因子基中的素数来进行筛选（见下表中间的那些列），如果剩余下的数相当小（在“Left”一栏下面）那它已经分解成功了。完整的分解记在最右边的一列中：

9.2.2 二次筛法 第三步，对所有这样的分解，其方次的奇偶性记在一个0/1矩阵中

9.2.2 二次筛法 第四步，寻找使它们所含的方次都是偶数的相应行，既可得所求s和t。例如，上述矩阵的65和70、64和71所在行都满足行和为０，即 两者都可导出4033的分解：4958和4292与4033共有因子37，而4142和4796与4033共有因子109。 因此

9.2.2 二次筛法 二次筛法可以从两方面来提高速度： 把那些被因子基部分地分解的数记录下来 一个　　　　数在经过除以因子基中的素数之后剩下一个或两个大素数因子，如果它能和另一个这样的数结合起来，那它也许仍然有用。 例，设　N=991241，可以验证 　和 　于是 某种部分的因子分解的组合使得“外来的”素数成为偶数方次，那么这种组合称为循环（cycle）。

9.2.2 二次筛法 筛法不仅可以对表达式 进行，也可以处理更一般的形如 的二次多项式。这一变革，称为多重多项式二次筛法（MPQS）。 优越性：每个多项式筛法可以独立地进行，这就可以把工作分散到许多不同的计算机上去做，每个机器将它得到的全因子分解或部分因子分解报告总部。然后，一个全面协调机器在这些部分因子分解中找循环。最后，进行0/1矩阵的计算。 猜想（ QS/MPQS方法的复杂度 ）：在某些合理的假设下， 用QS/MPQS方法分解整数Ｎ的时间为　

9.2.3专门用途的因子分解方法 “专门”是指因子分解方法的成功依赖于待分解数的一些特殊性质。一般指待分解数的因子都很小；或要求带分解数或它的因子有特殊的数学形式。 专门的方法并不总能成功，但在使用CFRAC、MPQS或NFS这些通用方法之前尝试一下它们是有帮助的。 例如：“rho”方法、“p-1”方法、Lenstra的椭圆曲线方法等。

Pollard “p-1”算法 John M. Pollard于1974年提出一种称为bound的方法 这种方法是在找到一个基本的素数p的基础上，在p-1的素数分解式中不含有大于预定B值的素因数的情况下，求出一个数的素因数。 理论依据：设p是奇素数，由费马小定理知： 若m为任意整数，p-1|m，则有 设N为待分解整数，p是N的一个奇素因子，p未知，若p-1|k!，则 ，依次计算 （i=1,2,…B）当 I 足够大时， 即可得到N的分解。 也可用最小的k个素数之积代替k！

Pollard’s Rho算法 可以较快地找到合数的较小因子。 1.算法描述 给定整数n，设初始值x=2，y=x2+1； (1)计算g=gcd(x-y,n)； (2)若1<g<n，则停止，g为n的一个因子； (3)若g=1,x2+1 x，(y2+1)2+1%n y，返回(1)； (4)若g=n，失败，需要对算法重新初始化。

2.举例 n=1133 解：(1)选x=2，y=5 (2)计算g=gcd(3,1133)=1 (3)计算x2+1=5 x，(y2+1)2+1%n=677 y (4)计算g=gcd(672,1133)=1 (5)计算x2+1=26， (y2+1)2+1%n=884 (6)计算g=gcd(884-26,1133) =gcd(858,1133)=11 因此，n的一个真因子为11。

g=pi,r=floor(logqn),b=bqr mod n Pollard’s P-1算法 1.算法描述 选择随机整数b，1<b<n； (1)计算g=gcd(b,n)，若g>1，找到真因子，停止； 否则，令pi={2,3,5,7,…} (2)令i=0，执行： g=1 i++; 继续 g=n 失败 结束 1<g<n g为因子 g=pi,r=floor(logqn),b=bqr mod n g=gcd(b-1,n) g

2.举例 n=9991 解：(1)取初值b=3，计算g=gcd(3,9991)=1； (2)q=2,r=floor(log29991)=13 bqr mod n=3213 mod 9991=229 g=gcd(229-1,9991)=1 (3)继续： q=3,r=floor(log39991)=8 bqr mod n=338 mod 9991=3202 g=gcd(3202-1,9991)=97 所以n=9991的一个因子为97。

2.定理 设n-1=ku,gcd(k,u)=1,k>n1/2，k的分解已知。 充要条件：若对每一个整除k的素数q，存在一个b， 使得： bn-1=1 mod n 且 gcd(b(n-1)/q-1,n)=1 则n为素数。 另外：若k>n1/2不满足，则还需考虑b0，使得： b0n-1=1 mod n 且 gcd(b0k-1,n)=1 举例验证： (1) n=31 (2) n=103 3.推论 设n=u2m+1，n为奇数且u<2m。 若存在一个b，使得b(n-1)/2=-1 mod n，则n为素数。 举例验证：n=13=322+1； n=41=523+1

ECM方法：随机选取阶为g的群G，g接近于p，则可在群 G上而不是群Zp上执行与Pollard “p-1”算法类似的计算。 缺陷：要求N有一个素因子p使得p-1只有小的素因子。 Pollard “p-1”算法是利用了群Zp，也可利用其他的群。 Lenstra于1987年设计的椭圆曲线算法（ECM）实际上是Pollard “p-1”算法的一般化，该算法牵涉到定义在模p椭圆曲线上的群，成功率依赖于接近p的一个整数只有小的素因子。 ECM方法：随机选取阶为g的群G，g接近于p，则可在群 G上而不是群Zp上执行与Pollard “p-1”算法类似的计算。 若g的所有素因子均小于界B，则可找到N的一个素因子；否则选取不同的群G(通常是不同的阶g)，重复上述步骤直到找到因子为止。

9.2.4 数域筛法 数域筛法(NFS)是目前所有已知的因子分解方法中最好的。有两种形式： 专门的NFS(SNFS)： 　　特别适用于具有形式的整数 通用的NFS(GNFS)：适用于任意整数 基本思想与QS法一致：在因子基上通过筛选的过程寻找Ｎ的同余式，然后在Z/2Z上由高斯消元法得到两边平方的同余式　　　　　　　，从而有希望分解整数Ｎ。 给定一个正奇数N， NFS分解N有以下四个主要步骤：

9.2.4 数域筛法

9.2.4 数域筛法

9.2.4 数域筛法 数域筛法（NFS），在合理假设下具有期望运行时间 若用GNFS来分解任意整数N时，则有 若用SNFS来分解一个特殊整数N时，则有