《二次筛法Eric Landquisi.doc》由会员分享，可在线阅读，更多相关《二次筛法Eric Landquisi.doc（4页珍藏版）》请在金锄头文库上搜索。
1、二次筛法The Quadratic Sieve Factoring AlgorithmEric Landquisi数学 488: 密码算术2001年12月14日1 介绍数学家早已开始寻找更快更好的方法去分解一个和数. 一开始, 是不断用更大的质数除, 直到得知它的分解. 这种试除法一直没有被改进, 直到费马应用平方差来分解因数: a2-b2=(a-b)(a+b). 在这种方法中, 我们从被分解数n开始. 找到大于n的最小平方数. 然后检验他们的差是否平方数. 如果是, 就可以用分解平方差的技巧来分解n. 如果不是, 那么找下一个完全平方数, 重复上面的处理. 虽然费马分解法比试除法快很多, 但
2、是在真实应用中, 例如分解一个几百位长的RSA模, 纯粹地用费马分解法太慢了. 一些其他方法已出现, 像椭圆曲线法(Elliptic Curve Method, 简称 ECM)由H. Lenstra在1987发现, 还有两个由 波拉德(Pollard) 在上世纪70年代中期发现的概率性的方法: -1方法(-1 method)和方法(method)(是希腊字母rho). 最快的运算法则仍然用类似费马的方法, 例如连分数法(the Continued Fraction Method), 二次筛选法(the Quadratic Sieve)(及其变种), 还有数域筛选法(the Number Fie
3、ld Sieve, 简称NFS)(及其变种). 一个例外是几乎与二次筛选法一样快的椭圆曲线法. 本文的中心是二次筛选法.2 二次筛选法以后简称二次筛选法为QS, 它在1981年由卡尔 帕梅让斯(Carl Pomerance)发明,是扩展 克雷契克(Kraitchik) 和 狄克逊(Dixon) 的思想. QS是最快的分解法直到1993年发现了数域筛选法. 不过对小于110位的数QS还是比NFS快.3 它怎样工作?设n是被分解数,QS试图寻找两个数 x, y 满足 xy (mod n), 且x2=y2 (mod n). 则 (x-y)(x+y)=0 (mod n), 接着用欧几里德法 (辗转相除
4、法求最大公约数) 检验 (x-y,n) 是否一个非平凡约数, 至少有1/2的机会找到非平凡约.我们首先定义Q(x)=(x+sqrt(n)2-n=x2-n, 然后计算Q(x(1), Q(x(2),.,Q(x(k), 下面会解释如何决定 x(i). 我们想要集合Q(x)的一个满足 Q(x(i1)Q(x(i2).Q(x(ir)是完全平方数y2 的子集. 注意到对所有 x, 有Q(x)=x2 (mod n). 于是, 我们有 Q(xi1)Q(xi2).Q(xir)=(xi1xi2.xir)2 (mod n), 并且如果满足上面的条件, 那么我们就有了n的因数.3.1 设定因数基和筛选区间我们需要一个有
5、效的方法去确定 xi, 以便得到Q(xi)的乘积. 接着检查乘积是否为平方数, 即乘积的质因数的指数必须都是偶数. 为此我们需要分解每一个 Q(xi). 所以我们希望它尽可能小且能用固定的被称作因数基的小质数(包括-1)集合分解. 要使 Q(xi) 小, 需选择接近0的x. 所以我们规定一个范围M, 并且仅仅筛选-M,M中的x (或者定义Q(x)=x2-n 然后筛选区间 sqrt(n)-M, sqrt(n)+M ). 现在, 如果x在这个筛选区间, 且一些质数 p 整除 Q(x), 那么 (x-sqrt(n)2=n (mod p), 即 n 是一个 mod p 的二次剩余. 所以在因数基中的质
6、数必满足勒让德符号(Legendre symbol) (n/p)=1. 第二个判断这些素数的标准是它们应该小于依赖于n的范围B, 我们分析运行时将讨论这些. 集合中的每个素数相关小,我们也说因数基是平滑的.3.2 筛选之前,我们为了因数基有一个素数集合.现在开始从筛选区间取出数x,并且计算 Q(x), 然后检查他的因数是否在我们的因数基中.如果是,就是说Q(x)是平滑的, 否则,丢弃它.继续处理下一个筛选区间中的元素.如果我们使用一个大的因数基,虽然是难以想象的低效to consider numbers one at a time和用所有在因数基中的素数检查整除性.如果改为在并行工作,将一次筛
7、完全部区间.每一个处理单元会处理一个子区间.这里是它怎样工作.如果 p 是 Q(x) 的一个质因数, 则 p|Q(x+p). 反过来, 如果 x=y (mod p), 则 Q(x)=Q(y) (mod p). 所以, 对于每一个因数基中的素数, 有:Q(x)=s2=0 (mod p), xZ(p)这能用Shanks-Tonelli 运算法则来解决 .我们将得到 S1p 和 S2p=p-S1p 两个结果. 然后, 那些在筛选区间中的 Q(xi)和 xi 当xi=s1p, s2p+pk 时都可被 p 整除. 这里有两种的方法去筛. 一种是获取一个子区间(依赖你的内存大小), 对于子区间的每个xi,
8、 将Q(xi)放入一个数组.对于每个 p ,从 S1p和S2p开始,对在等差级数中的每一个数组元素,除以最高可能的p的幂.在一个向量中记录p的适当的幂(mod 2).你将有一个每一个可分解的Q(xi)的向量, 而且对应唯一的因数基中的素数集. 一旦筛选完了一区间，记录素数的指数的向量就可以放进矩阵A. 重复此步骤, 知道有足够继续下一步. 这将在下面解释. 第二种方法不这么严格, 但是快很多. 代替工作于一些子区间的Q(x)的值, 在一数组记录数Q(xi)的二进制位数. 对于每一个在特殊的算术级数对于p的元素, 减去 p 的二进制位数. 每个因数基中的素数已经 had their turn 之
9、后, 这些剩余位接近 0 的元素很可能用那些素数完全分解. 我们需要考虑 round-off 错误和事实上很多数有平方因子. 对于有平方因子的数, 我们可以第二次筛选子区间采集解答 Q(x) = 0 (mod p2) 等等. 当完成所有那些, 我们设置一个将考虑的二进制位数的上界. 那将可能完全分解因数that slip through at this point的数, 但是节省的时间将比补偿它的更多. 遇到这个极限条件的数然后将成为因数, 重新看那个算术级数这样我们可以很快明确哪个素数整除哪个Q(xi).A second way is less exact, but is much quic
10、ker. Instead of working with the values of Q(x) over some subinterval, record the number of bits of the Q(xi) in an array. For every element in the particular arithmetic progressions for p, subtract the number of bits of p. After every prime in the factor base has had their turn, those elements with
11、 remaining bits close to 0 are likelyto be completely factorable over those primes. We need to take into account round-off error and the fact that many numbers are not square-free. For numbers that are not squre-free, we can sieve over the subinterval a second time picking out solutions to Q(x) = 0
12、(mod p2) and so on. When all that is done, we set an upper bound on the number of bits we will consider. There will likely be fully factorable numbers that slip through at this point, but the time saved will more than make up for it. The numbers that meet this threshold condition will then be factor
13、ed, by looking at the arithmetic progressions again so we can quickly nail down which primes divide which of the Q(xi). QS多数不重筛选区间查找素数的幂. 所以我们考虑筛选较小深度水平. 如果我们不用素数幂重筛, 临界值和 2 的指数变得非常重要. 幸亏我们有一个技巧解决 2 到一些区域. 如果 Q(x) = r2-n, 并且 r 是奇数, 则 2|Q(x). 我们可以较小地工作于n, 因此Q(x)常常被 2 的高次整除. 如果我们希望 8 总是整除偶数的 Q(x) , 我们
14、考虑 n (mod 8). 如果 n=3,7 (mod 8), 则2|Q(x). 如果 n=5 (mod 8), 则4|Q(x). 最后, 如果 n=1 (mod 8), 则8|Q(x). 那么使 8 整除每一个偶数 Q(x), 使 n:=5n 如果 n=3 (mod 8), 使 n:=3n 如果 n=5 (mod 8),与使 n:=7n 如果 n=7 (mod 8). Once the prime p = 2 is taken care of, sieve for the rest of the primes, subtracting the logarithms as above. 我们的
15、开端将成为: .其中 T 是一个接近2的值, pmax 是因数基中最大的素数. Silverman 8 暗示例如分解 30 位数时 T=1.5, 分解 45 位数时 T=2 , 还有分解 66 位数时 T=2.6.3.3 建造矩阵如果 Q(x) 完全分解了, 那么我们把以因数基中素数为底的指数(mod 2)放到一个如上描述的向量. 我们放所有这些向量到一个矩阵, 于是行体现 Q(xi), 列体现以因数基中素数为底的指数(mod 2). 例如, 我们的因数基是 -1,2,3,13,17,19,29 并且 Q(x)=2*3*172*19, 那么相应的行将是 (0,1,1,0,0,1,0). 回忆起
16、我们希望这些Q(xi)的乘积是完全平方数, 所以我们希望以在因数基中每个素因数为底的指数和为0 (mod 2). 可能有几种好方法从Q(xi)中得到完全平方数,它们多数不会给我们n的因数. 假设有 Q(x1), Q(x2),.,Q(xk), 那么我们希望找到解答 Q(x1)e1 + Q(x2)e2 + . + Q(xk)ek, 其中 ei 都是 0 或 1. 所以如果 是Q(xi)在A相应的行, 那么我们希望就是说我们需要解答:这样, 通过高斯消元法我们找到了解决方案. 所以我们至少需要找到同因数基里素数一样多的Q(xi). 生成的集合的每一个元素对应一个为完全平方数的Q(xi). 回忆解答中起至少有一半的机会将给我们一个正确的因数. 所以, 如果因数基有B个元素, 并且我们有B+10个Q(
