这篇文章来源于：

http://book.csdn.net/bookfiles/649/10064920569.shtml

6.4   因子分解

下面介绍因子分解。基本的分解方法是将整数n除以所有的素数，但是对大多数应用速度太慢。多年来，人们一直致力于研究更有效的分解算法，这里我们介绍其中的一些。第16章我们还介绍了一种用椭圆曲线的方法，第19章我们将会看到量子计算机如果制造出来了是如何有效地进行因子分解的。

有一种方法很慢，通常称为费马分解。其思想是将n表示成平方差：n＝x2－y2。那么

n＝(x+y)(x－y)给出了n的分解。例如，假设我们要分解n＝295 927。计算n＋12, n＋22, n＋32, …, 直到发现一个完全平方数。在这个例子中，295 927＋32＝295 936＝5442。因此

295 927＝(544＋3)(544－3)＝547×541

当n是两个相近的素数的乘积时，费马分解方法很奏效。如果n＝pq，将用|p－q|/2步找到分解。但是p和q是两个随机选取的100位素数，|p－q|可能非常的大，可能也有100位。所以费马分解不大可能奏效。但是为安全起见，RSA的两个作为模的素数通常取稍微不同的大小。

我们现在介绍一些更现代的方法。如果n其中的一个素数有特殊的性质，有些时候能够轻而易举地分解n。例如，如果p整除n并且p－1只含有小的素数因子，下面的方法是有效的。它是Pollard在1974年发现的。

p－1分解算法　选择一个整数a＞1，通常使用a＝2，选择一个界B。计算b≡aB! (mod n)如下。设b1≡a (mod n)和bj≡bjj－1 (mod n)。那么bB≡b (mod n)。令d＝gcd (b－1, n)。如果1＜d＜n，那么我们就找到了一个n的非平凡因子。

假设p是n的素数因子，并且p－1只含有小的素数因子。那么很有可能p－1整除B!，设B!＝(p－1) k。用费马定理，b≡a B!≡(a p－1) k≡1 (mod p)，因此p将在b－1和n的最大公因子中出现。如果q是n的另一个素数因子，那么不大可能有b≡1 (mod q)，除非q－1也仅仅含有小的素数因子。如果d=n，并非什么都没有用了。在这种情况下，有指数r（即B!）和a满足a r≡1 (mod n)。很有可能用指数因子分解方法（将在后面的章节介绍）分解n。我们可以选择一个更小的B，然后重复这个计算。

但是我们如何选择上界B呢？如果选择一个小的B，那么算法会很快跑完但是成功的机会很小；如果选择一个大的B，那么算法将会很慢。实际采用的值取决于当时的情况。

在应用中，我们要使用的是两个素数乘积的整数，也就是n=pq，但是很难分解，因此我们应该确定p－1至少有一个100的因子。选择一个大素数p0，大概在1040左右。考虑kp0＋1这种形式的整数，k跑遍某些1060左右的整数，用Miller-Rabin测试判定其素数性。平均在100步以内找到预期的值p。现在选择一个大素数q0，用同样的步骤得到q。那么n=pq用p－1方法是很难分解的。

椭圆曲线分解方法（见16.3节）给出了p－1的推广。但是这种方法使用了一些p－1附近的随机数，只需要其中一个含有小的素数因子。这样可以探测出更多的素数p，而不仅仅是那些

p－1只有小的素数因子的素数p。

6.4.1   二次筛法

因为这是目前最好的分解因数的方法基础，我们重复6.3节的如下结果。

基本原理　设n是一个整数，存在x和y使得x2≡y2 (mod n)，但是x≡／±y (mod n)。那么n是一个合数，并且gcd (x－y, n)是n的一个非平凡因子。

假设要分解n＝3 837 523，观察到下面的式子：

9 3982≡55×19   (mod 3 837 523)

                    19 0952≡22×5×11×13×19   (mod 3 837 523)

1 9642≡32×133   (mod 3 837 523)

     17 0782≡26×32×11   (mod 3 837 523)

将上面的式子相乘，得到

(9 398×19 095×1 964×17 078)2≡(24×32×53×11×132×19)2

2 230 3872≡2 586 7052

因为2 230 387≡/±2 586 705 (mod 3 837 523)，所以可以通过如下计算分解3 837 523：

gcd (2 230 387－2 586 705, 3 837 523)＝1 093

另一个因子是3 837 523/1 093＝3 511。

我们这样看刚才做的计算。首先，生成了一些平方，在模n＝3 837 523下可以写成一些小素数（在本例中不超过20）的乘积。这个素数的集合称为因子基底（factor base）。我们马上会讨论如何生成这样的平方。每一个平方给出了矩阵的一行，其中的元素是素数2, 3, 5, 7, 11, 13, 17, 19的指数。例如关系式17 0782≡26×32×11 (mod 3 837 523)给出了行6, 2, 0, 0, 1, 0, 0, 0。

除了以上关系式，假设还发现了如下关系式：

8 0772≡2×19   (mod 3 837 523)

        3 3972≡25×5×132   (mod 3 837 523)

      14 2622≡52×72×13   (mod 3 837 523)

我们得到矩阵

现在看看在模2下行的线性相关性。这里是其中的3个：

(1) 1行＋5行＋6行＝(6, 0, 6, 0, 0, 2, 0, 2)≡0   (mod 2)

(2) 1行＋2行＋3行＋4行＝(8, 4, 6, 0, 2, 4, 0, 2)≡0   (mod 2)

(3) 3行＋7行＝(0, 2, 2, 2, 0, 4, 0, 0)≡0   (mod 2)

当我们有这样的相关性，这些数的乘积就得到一个平方。例如，由这些关系得到：

(1) (9 398×8 077×3 397)2≡26×56×132×192≡(23×53×13×19)2

(2) (9 398×19 095×1 964×17 018)2≡(23×32×53×11×132×19)2

(3) (1 964×14 262)2≡(3×5×7×132)2

因此对多个x和y有x2≡y2 (mod n)。如果x≡/±y (mod n)，那么gcd (x－y, n)得到n的一个非平凡因子。如果x≡±y (mod n)，那么gcd (x－y, n)＝1或者n，因此得不到分解。在这3个例子中，我们有：

(1) 3 590 5232≡247 0002，而3 590 523≡－247 000 (mod 3 837 523)

(2) 2 230 3872≡2 586 7052 且gcd (2 230 387－2 586 705, 3 837 523)＝1 093

(3) 1 147 9072≡17 7452 且gcd (1 147 907－17 745, 3 837 523)＝1 093

现在思考一个基本问题：如何找到9 398、19 095等数的？思想是生成平方的比n的倍数略微大一点。这就意味着他们很有可能是小素数的乘积。一个简单的方法是考察形如[]，其中j很小,i任意，[x]表示小于或等于x的最大整数。这个数的平方近似为，大约是模n。只要i不大，这个数是相当小的，因此很有可能是一些小素数的乘积。

刚才使用的方法是很多最好的分解方法的基础。主要的步骤是生成同余关系式

x 2≡小素数的乘积

上述方法的一个改进是称作二次筛法（quadratic sieve）的方法。一种最近的方法数域筛法，使用了更为复杂的技术生成这些关系，在某些情况下更快一些。请参阅[Pomerance]，其中有这两种方法的描述和关于因数分解方法的历史。同时见习题28。

一旦得到了一些同余关系式，就如前将它们放入一个矩阵。如果矩阵的行比列多，一定能够得到在模2下行的线性关系。这样就能得到同余关系式x2≡y2 (mod n)。当然如前面的例子由1行＋5行＋6行≡0 (mod n)得到x≡±y，这种情况是得不到分解的。但是这种情况平均发生的概率最多是一半。因此如果我们有足够多的关系式，例如行比列多不少，那么应该有一个关系式能到x2≡y2并且x≡/±y，这时gcd (x－y, n)是n的一个非平凡因子。

在20世纪后期，在因数分解上有显著的进步。这部分归功于计算机的发展，部分归功于算法的改进。因数分解主要的推动力来自于其在密码上的应用，特别是RSA算法。表6-1给出了各年的因数分解记录（根据十进制数的位数）。

表6-1   分解记录

年 位数    年 位数

1964    20 1984    71

1974    45 1994    129

（续）

年 位数    年 位数

1999    155 2005    200

2003    174

6.4.2   理论方法

表面上，Miller-Rabin判定看上去通常能分解n，但是实际上还没有满足b u≡1 (mod n)，就已经达到b k－1了。问题在于通常a n－1≡/1 (mod n)。另一方面，假设存在指数r，可能不是n－1，对所有满足gcd (a, n)＝1的a满足a r≡1 (mod n)，那么这种情况下经常可以分解n。注意到如果

n＞2，指数r必须是偶数，因为我们可以取a≡－1 (mod n)，所以需要(－1) r≡1。

通用指数分解方法　假设存在指数r＞0，对所有满足gcd (a, n)＝1的a满足ar≡1 (mod n)。记r＝2 km，其中m是奇数。选择随机数a满足1＜a＜n－1。如果gcd (a, n)≠1，我们就有了n的一个因子，因此假设gcd (a, n)＝1。令b0≡a m (mod n)，对0≤u≤k－1连续地定义bu+1≡bu2 (mod n)。如果b0≡1 (mod n)，那么停止，尝试另一个不同的a。如果对某个u，有bu≡－1 (mod n)，那么停止，尝试另一个不同的a。如果对某个u，有bu+1≡1 (mod n)并且bu≡/ ±1 (mod n)，那么gcd (b u－1, n)给出了n的一个非平凡因子。

这和Miller-Rabin测试非常相似，差别在于r的存在性保证了对某个u有b u+1≡1 (mod n)，这在Miller-Rabin测试中不是经常发生的。尝试几个a的值，能够很快地分解出n。

当然，我们会问指数r是如何找到的。一般来讲这似乎很困难，测试很难在实际中应用。但是用它我们可以说明在RSA算法中知道解密指数就可以对模数进行分解。

在一些情况下，我们不知道通用指数，但是知道指数r对一个值a是可行的。有时候利用这些就可以分解n了。

指数分解方法　假设有一个指数r＞0和一个整数a满足ar≡1 (mod n)。记r＝2 k m，其中m是奇数。令b0≡a m (mod n)，对0≤u≤k－1连续地定义 (mod n)。如果b0≡1 (mod n)，那么停止；分解n的过程失败。如果对某个u，有bu≡－1 (mod n)，那么停止；分解n的过程失败。如果对某个u，有bu+1≡1 (mod n)并且bu≡/±1 (mod n)，那么gcd (bu－1, n)给出了n的一个非平凡因子。

当然，如果我们取a＝1，那么任何r都是可行的。但是有b0＝1，所以方法失败。如果a和r是通过合理明智的方法找到的，这种方法分解n的机率还是很大的。