二次筛法EricLandquisi.docVIP

二次筛法The Quadratic Sieve Factoring AlgorithmEric Landquisi数学 488: 密码算术2001年12月14日1． 介绍数学家早已开始寻找更快更好的方法去分解一个和数. 一开始, 是不断用更大的质数除, 直到得知它的分解. 这种试除法一直没有被改进, 直到费马应用平方差来分解因数: a2-b2 a-b a+b . 在这种方法中, 我们从被分解数n开始. 找到大于n的最小平方数. 然后检验他们的差是否平方数. 如果是, 就可以用分解平方差的技巧来分解n. 如果不是, 那么找下一个完全平方数, 重复上面的处理. 虽然费马分解法比试除法快很多, 但是在真实应用中, 例如分解一个几百位长的RSA模, 纯粹地用费马分解法太慢了. 一些其他方法已出现, 像椭圆曲线法 Elliptic Curve Method, 简称 ECM 由H. Lenstra在1987发现, 还有两个由 波拉德 Pollard 在上世纪70年代中期发现的概率性的方法: ρ-1方法 ρ-1 method 和ρ方法 ρmethod ρ是希腊字母rho . 最快的运算法则仍然用类似费马的方法, 例如连分数法 the Continued Fraction Method , 二次筛选法 the Quadratic Sieve 及其变种 , 还有数域筛选法 the Number Field Sieve, 简称NFS 及其变种 . 一个例外是几乎与二次筛选法一样快的椭圆曲线法. 本文的中心是二次筛选法.2． 二次筛选法以后简称二次筛选法为QS, 它在1981年由卡尔 帕梅让斯 Carl Pomerance 发明,是扩展 克雷契克 Kraitchik 和 狄克逊 Dixon 的思想. QS是最快的分解法直到1993年发现了数域筛选法. 不过对小于110位的数QS还是比NFS快.3． 它怎样工作?设n是被分解数,QS试图寻找两个数 x, y 满足 x≠y mod n , 且x2 y2 mod n . 则 x-y x+y 0 mod n , 接着用欧几里德法 辗转相除法求最大公约数 检验 x-y,n 是否一个非平凡约数, 至少有1/2的机会找到非平凡约.我们首先定义Q x x+[sqrt n ] 2-n x~2-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 x~^2 mod n . 于是, 我们有 Q xi1 Q xi2 ...Q xir xi1xi2...xir 2 mod n , 并且如果满足上面的条件, 那么我们就有了n的因数.3.1 设定因数基和筛选区间我们需要一个有效的方法去确定 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 的二次剩余. 所以在因数基中的质数必满足勒让德符号 Legendre symbol n/p 1. 第二个判断这些素数的标准是它们应该小于依赖于n的范围B, 我们分析运行时将讨论这些. 集合中的每个素数相关小,我们也说因数基是平滑的.3.2 筛选之前,我们为了因数基有一个素数集合.现在开始从筛选区间取出数x,并且计算 Q x , 然后检查他的因数是否在我们的因数基中.如果是,就是说Q x 是平滑的, 否则,丢弃它.继续处理下一个筛选区间中的元素.如果我们使用一个大的因数基,虽然是难以想象的低效to consider numbers one at a time和用所有在因数基中的素数检查整除性.如果改为在并行工作,将一次筛完全部区间.每一个处理单元会处理一个子区间.这里是它怎样工作.如果 p 是 Q x 的一个质因数, 则 p|Q x+p . 反过来, 如果 x y mod p , 则 Q x Q y mod p . 所以, 对于每一个因数基中的素数, 有:Q x s2 0 m