二次筛法的一些知识
鹗鸟（ossifrage），又名髭兀鹰（lammergeier），是阿尔卑斯山上一种稀有的肉食秃鹰。它的翅膀展开将近十米宽。鸟名的字面含义是“碎骨”。顾名思义，其习性
令人毛骨悚然。
上面这段鸟类学的细微末节知识与数学毫不相干。但是，近十余年来，这一令人
毛骨悚然的秃鹰却在数论密码学的领地中出现。
下面可能是人类数学史上最短的数学论文了，因为它没有一个字，仅仅是一个乘
法算式。这篇论文的标题同样没有一个字，叫“RSA-129”。但它的每一个读者都被这篇
论文震惊了，都知道它意味着什么，给数学，给人类带来了什么。假使数学设有诺贝尔
奖，那么当年的数学诺贝尔奖多半就要授予这篇论文的作者了，尽管这篇论文的作者达
六百多人。
————————————
11438 16257 57888 86766 92357 79976 14661 20102 18296 72124 23625 62561 8429
3 57069 35245 73389 78305 97123 56395 87050 58989 07514 75992 90026 87954 35
41
=
34905 29510 84765 09491 47849 61990 38981 33417 76463 84933 87843 99082 0577
*
32769 13299 32667 09549 96198 81908 34461 41317 76429 67992 94253 97982 8853
3
————————————
十一年前，1994年4月，由一些破译密码志愿者组成的一个松散的国际小组解决了一个十
七年悬而未决的挑战问题。他们破译了一个128位数字的密码：
96869 61375 46220 61477 14092 22543 55882 90575 99911 24574 31987 46951 2093
0 81629 82251 45708 35693 14766 22883 98962 80133 91990 55182 99451 57815 15
4
得到一个谜一般的讯息：“The magic words are squeamish ossifrage”。
这个秃鹰讯息的破译标志着两个表面上截然不同的研究领域二十年来的进展：对安全通
讯非常实际的要求以及高度理论性的数论，这个令人毛骨悚然的秃鹰是用数码锁了起来
，此密码的钥匙藏在一个129位数的素数因子之中。
这结果的重要性不只是对于侦探或那些摆弄数字的人而言的。随着计算机在日常生活中
越来越有用，对安全通讯的要求愈增。随便什么人在取款机上按一个四位数或者输入口
令上截计算机帐户，实际上，已经是在进行秘密的通讯。
计算机线路上的银行事务以及其它新型的计算机化的商业活动要求机器保护他们接触到
的数据。数据密码化是普遍出现的一个解决办法。但是，什么地方又扯上了数论？
故事开始于1976年，斯坦福大学的Whitfield Diffie和Martin Hellman 在密码学中引进
了一个极其新颖的想法：公开钥密码。人们常常不言而喻地假定，如果知道了如何编密
码，那么当然也知道了如何解密码。例如，如果你知道一种密码，它是基于字母的移位
，A换成B，B换成C，等等，那么很容易将“Uif nbhjd xpset bsf trfbnjti pttjgsbhf
”解码：只须将每个字母作相反方向移位。Diffie 和Hellman对这种编码和解码“显然
”的关系提出质疑。他们提可能有一种密码，即使知道编码的算法——就是说，知道了
如何将“原文”变成“密文”，也无助于破译。
第二年，Ronald Rivest，Adi Shamir和Leonard Adleman三位数论密码学家提出了实现
Diffie和Hellman想法的实际办法。
他们的办法，就是所谓RSA码，是依据一系列初等的数论的定理。这些已经足以使他们成
功地组织一个公司——RSA数据加密有限公司（RSA Data Security Inc），位于加利福
利亚州红木巿。
为了简单地说明RSA码，假定B想给A送去一个信息：“I love you”。他从一个简单的尽
人皆知的办法开始，把字母换成数字，例如A=01，B=02，…，z=26，用00代替单词之间
的空格。于是这条信息便生成了一个数：
M=09001214220500251421。
B然后察看A的公开加密算法，它由两个数组成，N和e（“e”代表加密编码encryption）
。N是一个大数，比方说有200位。它是两个大素数的乘积。但这对B无关紧要。他只要把
M作e次乘方，除以N，然后记下余数C，用数学符号，这表示C=M^e mod N。数C便是信息
码。B将它送给A。
A有她自己的秘密的破密数d，为了破译B的信息，她用C，d和N算出数C^d mod N。就象魔
术一样，结果就是M，A于是只需将它变回字母。
当然，这不是魔术。这结果得自于e，d和N的素数因子之间的数论关系。假定N=pq，其中
p和q是素数，那么e和d可以选成满足（p-1）（q-1）整除ed-1的任何两个数。实际上，
对每一个e存在唯一的d满足条件。（准确言之，e与p-1和q-1不能有公因子。特别地，它
不能是偶数。然而，几乎可以是任何大素数）。此外，对给定的e，其实很容易找到合适
的d，只要你知道p和q。
这在理论上，无秘密可言。任何人要想破译A的密码只需找到数N的因子p和q，对计算机
来说，原则上也容易做到。RSA“牢不可破”的原因是，分解大素数的乘积令人难以置信
的费时，虽然在概念上那很简单。要分解几百位数的数，亿万个超级计算机一起工作亿
亿万年也还做不到。因子分解绝非易事。
是这样吗？
如果使用单纯的试除办法，那一定如此。为了要分解数N，尝试做除法的最大次数大约正
比于N的平方根。而且，很不幸，在极多的情况下，试除的次数确实要达到这个最大值。
因此，用这个办法分解一个由两个100位数相乘而得的200位数，试除次数的数量级会是
10^100——这超过了任何可以想象的计算机在任何可以想象的时间内的计算能力。
然而，试除不是分解大数的最聪明的办法。早在如费马那时的数学家已经找到基于数论
原理的更有效的办法。费马他自己就有一个极其有趣的办法：为了因子分解N，先找出两
个数x，y满足x^2-y^2=N。然后左边简单地分解成（x+y）（x-y）。例如，21=25-4=52-
22=（5+2）（5-2）=7*3。
对费马方法进一步变通的办法是寻找数x和y使得N整除x^2-y^2。于是，有50%的机会x+y
包含N的一个因子，而x-y包含另一个因子。（如果不然，假定说N正好整除x+y，那么就
重新找。）例如，21整除10^2-4^2，则因子10+4=14=2*7以及10-4=6=2*3，再一次给出因
子分解21=7*3。
在二十世纪二十年代，Maurice Kraitchik提出用较小的数来凑成x和y的值。以N=111为
例，简单的考虑就能得出
11^2(mod 111)=121(mod 111)=10=2*5
14^2(mod 111)=196(mod 111)=85=5*17
16^2(mod 111)=256(mod 111)=34=2*17
这里记号a(mod N)是指a除以N后得到的余数。于是，可见111整除（11*14*16）^2-（2*
5*17）^2，它可以分解成为2634*2294。111的因子便可用所谓的欧几里得德算法找出来
，这个办法在二千多年以前就已经知道了。欧几里得算法用计算一系列余数得出两个数
的最大公约数。例如用以下计算求得111和2294的最大公约数：
2294(mod 111)=74
111(mod 74)=37
74(mod 37)=0
这表明37整除111和2294。类似的方法求得3是111和2634的公因子，至此完成了因子分解
111=37*3。
加州大学洛杉矶分校Michael Morrison和亚力圣那大学的John Brillhart在七十年代使
因子分解的拼凑方法系统化，用线性代数方法选取要组合的平方数。全心全意的方法在
本质上归结为选定一组小素数，称为因子基，然后从大量的候选的数x中筛选，只选取那
些x，它满足x^2(mod N)（即x^2除以N的余数）的素数因子全在因子基中。X^2(mod N)用
因子基得到的因子分解记录在一个矩阵元为0或1的矩阵中。每一行对应一个x。每一列对
应因子基中的一个素数。在“x行，p列”的值代表p整除x^2(mod N)奇数次或是偶数次。
当积累了相当数量的x之后，线性代数就可以有贡献了，它可以帮助你找出一个组合使其
所含的因子基中的素数都是偶数方次。线性代数理论保证只要行数多于列数，这样的组
合一定存在。并非所有的组合都可以得到数N的因子数。但是当有很多组合时——即当行
数比列数多出很多时——至少有一种组合成功的几率极大。
这就是在1977年Rivest，Shamir及Adleman提出他们的公开钥密码系统时的状况。他们认
为每秒钟百万次运算的计算机可以在4小时之内因子分解一个50位的数，但是分解一个1
00位的数要花几乎一个世纪，而200位的数大约要花40亿年。甚至考虑到计算速度可以再
提高百万倍（甚至尚未出现），基于200位数的密码看来是十分安全的。
Mirtin Gardner在1977年“Scientific American”的专栏文章中介绍了RSA码。为了显
示这一技术的威力，RSA公司的研究人员用一个129位的数N和一个4位数e 对那个关于秃
鹰的消息作了编码。Gardner刊登了那个密文，同时给出了N和e。RSA公司还悬赏100美元
，奖给第一个破译这密码的人。
这100美元看来很安全，至少在未来两万年左右不会有问题：RSA公司估计因子分解一个
129位的数大约要花23000年。到那时，比方说以年利率6%的复利来算，100美元会变成5
00位数的巨款。计算机速度的增长可能会降低它一两个数量级，但是对象RSA-129这样一
个数，安全性似乎仍然相当有保证。
然而数学史上往往有意外的事发生。这个叫阵的RSA-129仅仅在十七年之后就败下阵来，
使它兵败下阵的计算从开始到算完只花了不到一年的时间。一批松散组成的因子分解迷
，大约有六百多人，分布在二十几个国家。他们经过八个月的努力最后于1994年4月为R
SA-129找到了64位数和65位数两个素数因子。
分解RSA-129这一项行动计划的完全靠新技术的发展，而这些技术在1977年时还刚刚起步
。其中之一是因特网。然而，核心的动力还是所谓二次筛法的算法。
二次筛法是在1981年由乔治亚大学的Garl Pomerance所提出。它从根本上加快了Kraitc
hik算法，使得Morrison-Brillhart设施高度运行。拼凑方法的症结在于难以找到x，使
x^2(mod N)能按因子基作因子分解。大部分数不具有这种性质。于是，只能大量使用费
时的试除法计算。二次筛法革新了这一过程，因此极大地加速了Morrison和Brillhart的
0/1矩阵的构造。
二次筛法的算法过程大致如下：
对N=4033的二次筛法：
x x^2-N 2 3 7 13 17 19 left
64 63 — 21 3 — — — 3 3^2*7
65 192 96 32 — — — — 32 2^6*3
66 323 — — — — 19 1 1 17*19
67 456 228 76 — — — 4 4 2^3*3*19
68 591 — 197 — — — — 197 —
69 728 364 — 52 4 — — 4 2^3*7*13
70 867 — 289 — — 17 — 17 3*17^2
71 1008 504 168 24 — — — 24 2^4*32*7
72 1151 — — — — — — 1151 —
73 1296 648 316 — — — — 316 —
二次筛法为分解大数而设计，但是用小数，例如N=4033，可以最好地解释它的运作。对
这个N，素数2，3，7，13，17，以及19可以用作因子基（5和11不能除尽任何x^2-4033）
。在上表中，这一算法通过对从64到73的数除因子基中的素数来进行筛选（见表中间的
那些列）。如果剩余下的数相当小（在“Left”一栏下面）那它已经分解成功了。完整
的分解记在最右边的一列中。对所有这样的分解，其方次的奇偶性记在一个0/1矩阵中：
N=4033的0/1矩阵
2 3 7 13 17 19
64 0 0 1 0 0 0
65 0 1 0 0 0 0
66 0 0 0 0 1 1
67 1 1 0 0 0 1
69 1 0 1 1 0 0
70 0 1 0 0 0 0
71 0 0 1 0 0 0
有两个两行的能使它们所含的方次都是偶数。由这两个组合可得
(65*70)^2-(2^3*3*17)^2=(4550+408)(4550-408)=4958*4142
(64*71)^2-(2^3*3^2*7)^2=(4544+252)(4544-252)=4796*4292
两者都可导出4033的分解：4985和4292与4033共有因子37，而4142和4796与4033共有因
子109。因此4033=37*109。诚然，用试除办法，可以得到这个答案更快。但是当数非常
大时，二次筛法就要远有有效。
x值的范围取成稍稍大于所考虑的N之平方根。对每个因子基中的素数p，考察诸x^2-N中
前p个值，从中确定能被这整除的那些值（因子基必须根据数N进行调整，使得每个素数
至少能整除1个x^2-N值）。避免了昂贵的试除法。这样，算法对数x进行了“筛选”，成
功地对x^2-N的每一个适当的值用因子基中的素数作了除法。这些值最后完全被分解，其
所有素因子全在因子基中。进而将结果记录到0/1矩阵中去。
二次筛法可以从两方面来提高速度，这对RSA-129行动计划意义重大。首先，把那些被因
子基部分地分解的数记录下来可能有好处。一个x%2-N数在经过除以因子基中的素数之后
剩下一个或两个大素数因子，如果它能和另一个这样的数能使起来，那它也许仍然有用
。例如，设N=991241，可以验证997^2(mod N)=2^4*173和1079^2(mod N)=2^3*5^3*173，
于是(997*1079)^2=2*5*(2^3*5*173)^2。某种部分的因子分解的组合使得“外来的”素
数成为偶数方次，那么这种组合称为循环（eycle）。
其次，筛法不仅可以对表达式x^2-N进行，也可以处理更一般的型如(ax+b)^2-N的二次多
项式。这一变革，称为多重多项式二次筛法。它有其优越性，因为每个多项式筛法可以
独立地进行，这就可以把工作分散到许多不同的计算机上去做，每个机器将它得到的全
因子分解或部分因子分解报告总部。然后，一个全面协调机器在这些部分因子分解中找
循环。最后，进行0/1矩阵的计算。
这就是RSA-129被因子分解的过程。这一行动计划由牛津大学的Paul Leyland，爱荷华州
立大学的Michael Graff以及RSA公司的Derek Atkins发起，所用的程序由在新泽西州的
Morristown，贝尔通讯研究所的Arjen Lenstra和加州Palo Alto DEC系统研究中心的Ma
rk Manasse编制。他们的因子基包括524339个素数。他们通过互联网发送程序和数据库
，然后上网上征求志愿者。
Leyland在一次电子邮件通讯中对他的志愿大军说：“将你在个人电脑，工作站，超级计
算机或传真机上得到的闲散的循环，捐献出来，你的捐献也许不能为你扣税，但那是确
确实实的慈善捐献。”关于传真机他不是开玩笑：在美国真的有人想出办法利用传真机
上的计算机在电话空闲时间筛选数字。
随后的八个月中结果不断积累，每天大约有三万个完全的或部分的因子分解送来，在周
末更多，因为那时机器往往更有空闲。到1994年4月，他们收集到8424486个因子分解：
112011个“完全分解”，1431337个“单部分分解”以及6881138个“双部分分解”。用
这些部分分解，他们拼成457455个循环。从而，得到一个有569466行的0/1矩阵，这已完
全足够保证存在一种组合，它对因子基中的524339个素数全部有偶方次。最后的一个困
难步骤是找出这些组合，那么，分解RSA-129便易如反掌了。当然，除非这些组合中没有
一个能行得通，但这种可能性极度少。同样，这一任务概念上虽简单，但是矩阵之大到
了难以计算的地步。如今已经到了10^12byte硬盘的时代了，五十几万行和列的矩阵听起
来不太可怕。但是，别忘了做乘法：RSA-129的矩阵有几乎三千亿个矩阵元。
Lenstra用Mas Par超级计算机用两个步骤来进行所需的计算。第一步是用已知的所谓“
Structured Gauss”的线性代数技术来削减原先庞大的矩阵。这种做法是可行的，因为
在二次筛法中的任何0/1矩阵，其矩阵之大部分都是0，因子基中只有一小部分素数出现
在各个因子分解中，而其中可能还有偶次方。实际上，削减后的较小的矩阵消除了冗长
连绵的0。
第二步是用这个较小的矩阵来找到合适的组合，这仍然是超级计算机干的活。因为尽管
是较小的矩阵，它仍然相当庞大，有188346行和188146列。这相当于有350亿个0和1，4
0亿个byte的数据（每一个数据0功1是一个比特，一个byte是8个比特）。当今，40亿个
byte并不被认为是个特别大的数据文件。但是，Lenstre所要作的计算要求每个比特都正
确无误——甚至矩阵一个输入出错都会前功尽弃。Lenstra说：“你几乎从来没有见到过
一个文件，它的所有40亿个byte都一样至关重要。”
不过，这个计算成功了。从这个0/1矩阵中找到了一个合适的能使用它得到了RSA-129的
因子分解，然后那秃鹰讯息的计算便唾手可得。
值得注意的是，RSA-129分解的成功并不危及现行的以RSA为基础的编码，用以因子分解
数字所需要的计算机能力随着数字位数的增加而冲天猛增。那些搞因子分解的人们认为
他们能在最近的将来出击150位数——有一种称为数域筛法的新技术已经显示很有希望，
那是把二次筛法推广到代数数域。然而，搞密码学的诸位很容易占上风，因为他们只需
把编码基于越来越大的数。Rivest指出：“我们建议用200位到300位的数。”除非计算
数论有惊人的突破，因子分解在一个长时间内仍然是个难题。然而，数论家们相信进展
到来之期，就如整数本身一样，一定是屈指可数的。
多了解了解
二次筛法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+)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 然后筛选区间 [-M, +M] ). 现在, 如果x在这个筛选区间, 且一些质数 p 整除 Q(x), 那么 (x-)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 暗示例如分解 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 说如果切换多项式的费用占总费用的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 给出一些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)可被这个更大的因数基所分解. 我们同样添加这些进去. 估计这将节省1/6的筛选时间.
6. 高斯消元
分解过程中最后的一个步骤是高斯消元. 建立起的矩阵非常大, 且几乎每个元素都是零. 即是所谓的稀疏矩阵. 使用来自基本线性代数的标准技术缩减这个矩阵可以大幅提速. 一个平常的想法是如果我们有一列挚友一个1, 我们可以消去那行联立它. 有可靠的方法使Q(x)成为平方数的因数. 有限域上矩阵的高斯消元有两种算法: Wiedemann 和 Lanczos . 对于这两种算法来说, Wiedemann较好地工作于我们学过的域GF(2). 运行时近似为:
其中B是因数基中素数的数目, w近似为矩阵到向量的乘法的数目. 如果是像这里的稀疏矩阵, w会很小. 我们同时需要2B2的储存空间.
7. 运行时 :)
不错
就目前来说
二次筛在分解一定大小的数时，是最快的
所以目前三个筛法
小数字用椭圆曲线，大的用二次筛，最大的用数域筛
各自有其因子范围 我怀疑你能看明白吗？？？？？？？？？？
页:
[1]