- 注册时间
- 2009-4-27
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 3513
- 在线时间
- 小时
|
楼主 |
发表于 2009-4-30 22:12:55
|
显示全部楼层
多了解了解
二次筛法
The Quadratic Sieve Factoring Algorithm
Eric 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 (mod p), x∈Z(p)
这能用Shanks-Tonelli 运算法则来解决 .我们将得到 S1p 和 S2p=p-S1p 两个结果. 然后, 那些在筛选区间中的 Q(xi)和 xi 当xi=s1p, s2p+pk 时都可被 p 整除.
这里有两种的方法去筛. 一种是获取一个子区间(依赖你的内存大小), 对于子区间的每个xi, 将Q(xi)放入一个数组.对于每个 p ,从 S1p和S2p开始,对在等差级数中的每一个数组元素,除以最高可能的p的幂.在一个向量中记录p的适当的幂(mod 2).你将有一个每一个可分解的Q(xi)的向量, 而且对应唯一的因数基中的素数集. 一旦筛选完了一区间,记录素数的指数的向量就可以放进矩阵A. 重复此步骤, 知道有足够继续下一步. 这将在下面解释.
第二种方法不这么严格, 但是快很多. 代替工作于一些子区间的Q(x)的值, 在一数组记录数Q(xi)的二进制位数. 对于每一个在特殊的算术级数对于p的元素, 减去 p 的二进制位数. 每个因数基中的素数已经 had their turn 之后, 这些剩余"位"接近 0 的元素很可能用那些素数完全分解. 我们需要考虑 round-off 错误和事实上很多数有平方因子. 对于有平方因子的数, 我们可以第二次筛选子区间采集解答 Q(x) = 0 (mod p^2) 等等. 当完成所有那些, 我们设置一个将考虑的二进制位数的上界. 那将可能完全分解因数that slip through at this point的数, 但是节省的时间将比补偿它的更多. 遇到这个极限条件的数然后将成为因数, 重新看那个算术级数这样我们可以很快明确哪个素数整除哪个Q(xi).
A second way is less exact, but is much quicker. 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 remaining "bits" close to 0 are likely
to 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 (mod p^2) 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 factored, 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) , 我们考虑 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. 我们的开端将成为:
.
其中 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*17^2*19, 那么相应的行将是 (0,1,1,0,0,1,0). 回忆起我们希望这些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(x)的值, 那么我们至少有1023/1024的机率找到一个正确的因数. 所以我们用文章开始描述过的GCD检查记录解答方法的向量中的Q(xi), xi 相应的乘积是否给我们一个正确的因数. 如果不能, 检查生成集合中的下一个元素. 当一个正确的因数找到了(实际上你就有两个因数), 测试它的素性. 如果你在分解RSA模, 则因数必是素数, 因此你完成了分解.
4. 变种: 多项式二次筛选法(The Multiple Polynomial Quadratic Sieve, MPQS)
正如名字所暗示的, MPQS使用一些多项式代替Q(x). 这方法首先被Peter Montgomery暗示. 所有多项式有如下形式:
其中a, b和c由下面方法确定. 这么做的动机是通过使用一些多项式, 可以使Q(x)小很多于,是筛选区间小很多.
在我们的系数确定中, 令a为平方数. 然后选择0≤b<a满足b2≡n (mod a). 这仅在n以每个q|a的素数q为模时都是平方数时成立. 所以我们希望选择a是一个已知因数分解的数且对于每个q|a的素数q, (n/q)=1. 最后, 选择满足b2-ac=n的c. 当我们找到一个分解好的Q(x)注意到:
于是:
回想起a是平方数, 所以aQ(x)必是.
假设我们的筛选区间是[-M,M]. 我们希望使M和区间中的Q(x) 最优化. 为此, 其中一个方法是确定系数使Q(x)在[-M,M]的最大和最小值的绝对值大致相等. 最小值在x=-b/a. 因为我们选择0≤b<a, -1<-b/a≤0且Q(-b/a)=-n/a. 所以明显的最大值在-M或M, 且约等于(a2M2-n)/a. 我们希望它约是n/a, 所以我们选择:
关系到这方法的一方面是切换多项式的费用. Pomerance [6] 说如果切换多项式的费用占总费用的25%~30%, 对该方法将非常不利. 当需改变多项式, 明显需要新系数, 但是对于每个多项式和每个因数基里的素数p我们都要解决Q(x)≈0 (mod p), 即在改变多项式时有一个繁重的载入工作.
一个Pomerance称为 “自初始化”(self-initialization) 的方法可以帮助显著减少切换多项式的费用. 其技巧是在一些多项式中确定常数a. 我们依然希望 a≈sqrt(2n)/M, 所以使a为k个素数的乘积, 每个素数p的数量级约为 (sqrt(2n)/M)1/k 且满足 (n/p)=1. 我们同样需要找满足b2≡n (mod a) 的b. 事实上因为a的因数是k个素数, 以至于有2k-1个值b. 然后多项式的初始化问题: 对于因数基里的所有素数p找每个多项式Q(x)=0 (mod p) 的解可以一次完成.
这个版本的主要优势当然是减小因数基和筛选区间的大小. Silverman [8] 给出一些n一直到66位的建议. 因数基的最佳大小随所用机器变化, 虽然一个好的估计指出所用素数的数目只需原始QS十分之一, 但是这也意味着筛选区间上千大. 此系统的另一个优势是便于并行处理, 每个处理器处理一个不同的多项式. 如果每一个处理器产生它自己的多项式, 那么它可以公平独立地运行, 只需在筛好所有区间后联系中央服务器.
5. 变种: 双倍大素数MPQS (The Double Large Prime MPQS)
这个版本的QS被Lenstra, Manasse, 和一些其他的人在1993 and 1994用来分解RSA-129和揭露信息 "The magic words are squeamish ossifrage." . RSA 1977年宣布这个挑战时, 他们相信23000年来分解这数字赢得 \$100奖金. 实际上, 只需8个月的努力. 双倍大素数版本所做的事是考虑Q(xi)的部分分解. 在筛选步骤we hang onto Q(x) and its partial factorization 如果我们有:
按上述定义的L必是素数. 我们可以找到这些部分因数分解by incresing our theshold value after sieving by 2ln(pmax). 如果我们找到另一个包含常数L的Q(x), 那么把L添加到我们的因数基中并且两个Q(xi)的积将有因数L2. 所以我们合并这两个分解到矩阵A. 可能有其他Q(xi)可被这个更大的因数基所分解. 我们同样添加这些进去. 估计[7]这将节省1/6的筛选时间.
6. 高斯消元
分解过程中最后的一个步骤是高斯消元. 建立起的矩阵非常大, 且几乎每个元素都是零. 即是所谓的稀疏矩阵. 使用来自基本线性代数的标准技术缩减这个矩阵可以大幅提速. 一个平常的想法是如果我们有一列挚友一个1, 我们可以消去那行联立它. 有可靠的方法使Q(x)成为平方数的因数. 有限域上矩阵的高斯消元有两种算法: Wiedemann 和 Lanczos [10]. 对于这两种算法来说, Wiedemann较好地工作于我们学过的域GF(2). 运行时近似为:
其中B是因数基中素数的数目, w近似为矩阵到向量的乘法的数目. 如果是像这里的稀疏矩阵, w会很小. 我们同时需要2B2的储存空间.
7. 运行时 |
|