两个筛法的故事

1、原文网址：/notices/199612/pomerance.pdf原作者： Carl Pomerance两种筛法的故事 Carl Pomerance （这篇文章献给我的朋友 和老师Paul Erdos，以资纪念） 现在是分解大数成质因子比赛的最好时代。在1970年不可能分解一个20位的“硬”数。在1980年，那时是Brillhart-Morrison连分数分解算法的鼎盛时期，分解一个50位的数正变得平常起来。在1990年，我的二次筛法分解算法已经使能分解的大数位数翻倍，记录达到116位。到1994年二次筛法已经分解了著

2、名的129位的RSA挑战数，此数Martin Gardner在1976年的科学美国人杂志专栏中估计它在4x1016年内是安全的（虽然那时的其他人会谦虚点）。但现在二次筛法也不是冠军了。它在1996年春天被Pollard的数域筛法所取代，此方法成功地分解了一个130位的RSA挑战数，并且只需要二次筛法所需时间的15%。在本文中我们会简要地谈及这些分解算法这两种筛法以及很多参与研发算法的人们中的一部分。在本世纪中叶，有关计算的事情似乎是过时的。在绝大多数的书中分解大数的问题几乎被忽视，因为它被认为是很普通的。毕竟，从原理上讲因子分解是可行的，那还去讨论什么？也有少数研究者不考虑这种耗时的方式，努力

3、去发现更快的分解方法。对这些研究者来说，时间是基本和重大的问题，没法把它扔到一边。  但时代在变化。在最近的几十年里我们已看到可存取的快速计算能力的肇始，也看到加密系统的产生，并且它的安全性基于可推测的对快速大数分解（或其他数论问题）的无能力。今天很多人对分解感兴趣，承认它不仅是加密系统的安全性基准，也是计算能力本身的基准（就像SuperPi一样).在1984年美国计算机械协会颁发了一枚徽章给美国电子电气工程师协会（IEEE），那年是IEEE100周年纪念。这枚徽章刻上了那年由二次筛法完成分解的  的素数分解式。ACM的主席评论道：约300年前法国数学家

4、梅森推测 是一个合数，即一个可分解的数。大约在一百年以前它被证明是可分解的，但即使在20年以前分解这个数的计算量也被认为是难以克服的。事实上，使用一般的机器和传统的搜索算法，那么搜索时间估计要1020年。今年二月在加州的Sandia使用一台Cray计算机花了32小时将这个数分解了，这是一个世界记录。在计算领域我们已走过一段很长的路，为了庆祝IEEE对计算领域的贡献，我们在一枚徽章上刻下了这个梅森合数的五个因子。IEEE，生日快乐。分解大数是一种陌生的数学，类似于实验科学，事实有最终而明确的话语权。如果分解n的某个方法运行一阵子后声明“d是n的因子”，那么这个论断很容易检验；显然，整数

5、就是最终而明确的话语权。任何人都可以很好地这么做，一般不需要通过理论证明一个方法是怎么工作的。但是，作为实验科学，严密和启发性的分析对我们理解学科并推动它的发展却是很有价值的。并且作为实验科学，在研究者和应用者之间有时有点牵扯。一些人认为分解的理论研究是台面上的不动产（或者如Hendrik Lenstra曾风趣的表述，Siegel意译过来是，“玫瑰园里的一只猪”），通过夸张地给不同算法很多标签，如“多项式”，“指数式”，“随机”等等获得不该有的注意力，给那些做严肃艰苦计算的作业者以或有或无的回报。这个观点是有事实要素的。但正如我们看到的，理论对本文标题说的两种筛法扮演了一个重大角色。一个竞赛问

6、题    还是让我们从源头开始吧，至少这是我的源头。当我在谈论分解算法时，我常重复一件很早以前在中学时碰巧发生的一件事情。那时我参加一个数学竞赛，其中一道题是分解整数8051.要求在五分钟内完成。其实不是不让我们使用口袋计算器，在1960年它根本就不存在，这件事大约就是这个时间发生的！好了，我的算术很好，我相信在规定的时间内我能用试除法分解它，要一直试除到8051的平方根（约90）。但在很多考试中，特别是在一个竞赛中，很多学生希望能契合出题者的意图。我确信他们不会出一个只需用理所当然的方法拼命去试除，直到找到因子的题目。肯定有某种聪明的替代途径能找到答案

7、。所以我花了几分钟寻找这个聪明的办法，但我变得越来越焦虑因为花了太多时间。最后虽然迟了，我还是用试除法，但我已经浪费了很多时间，最后没答出这道题。     那么现在你能找到聪明的法子吗？如果你愿意想一想，那就停一下再看下一段。Fermat和Kraitchik   诀窍是把8051写成8100-49，即902-72,所以我们可以使用代数，就是分解一个平方数差，以便分解8051.结果是83x97.这个办法一直有效吗？每个奇合数都可以分解成平方差：只需使用恒等式ab=(1/2(a+b)2-(1/2(a-b)2.努力寻找平

8、方差的办法实际上是费马的一种分解方法。就像试除法有很容易的情形(如有很小的质因子）一样，平方差方法也有很容易的情形。例如，如果n=ab且a和b近似等于根号n，就像n=8051的情形一样，那是很容易找到两个平方数的。但在最糟糕的情形下，平方差方法会比试除法更差。另一种方法更差。使用试除法时，大部分数会碰上容易的情形；即是，大部分数有一个小因子。但使用平方差方法时，只有一小部分数有它们平方根附近的因子。所以这种方法只对可能的输入数中的一小部分有好的效果。（虽然试除法对大部分输入数能开启分解，但要达到完全分解通常要困难得多。大部分数都能抵抗住试除法甚或试除法+平方差法）。两种筛法的故事(二）连分数法

9、Kraitchik方法的本质是当x等于根号n附近的连续整数时挑选一系列x2-n的数，以便找到一个子系列，它们相乘得到平方数。如果这个平方数的平方根是v，并且相关的x相乘后为u，那么就有u2v2 mod n,这样就有可能这个同余式是非平凡的，即uv mod n.在1931年D.H.Lehmer和R.E.Powers提议用源于根号n的连分数展开式的方法来代替Kraitchik's的函数Q(x)=x2-n.如果ai/bi是根号n的第i个渐近分数，设Qi=ai2-bi2n。则有Qiai2 mod n.这样，不是去选择数Q(x),我们可以去选择Qi，两种情况下它们对n的剩余都

10、是平方数。虽然连分数计算起来很麻烦，就象暴躁的野兽，但在二次无理数的情况下还算好。事实上，有一个源于高斯或更早的简便的递归程序（参考16),可以满足这里的计算需要，即求出一系列的整数Qi和ai mod n。但是为何放着非常简便的二次多项式不用，偏要用奇特的连分数呢？那是因为这个不等式Qi<2sqrt(n).数列Qi的绝对值比数列Q(x)要小很多。（当x的值偏离根号n时，数Q(x)的值几乎是线性增长，且斜率为2sqrt(n).)如果一个人要处理很多数，以便从中发现一些数相乘后得到一个完全平方数，大概处理一批较小的数比处理一批较大的数要容易些吧。所以Lehmer与Powers的连分数方法比K

11、raitchik的二次多项式有一个明显的优点。 怎样选择合适的数在一个算法里有项说明要求你处理一些数以便找到一个子集产生一个平方数，这当然是令人奇怪的。我记得有幅漫画，里面有两个穿白色外套的科学家站在一个写满了晦涩难懂的符号的黑板前，其中一个指向一特别详细的关键点，对另一位说这里出现了一个奇迹。我们能找到Kraitchik系列中75,168,360和560这些数并相乘得到平方数，这是奇迹吗？为什么我们想找到这样的子集，并且如果它存在，我们又怎样有效地发现它呢？要找到一个给定系列数的子集来相乘得到一个平方数，一个有条不紊的战略是John Brillhart和Michael Morris

12、on找到的，很奇怪，它的核心仅仅是线性代数（参看16).每个正整数有一个基于m的质数分解集上的指数向量v(m)。设pi为第i个质数，那么有m=pivi.(这个乘积包括分解集上所有的数，其中只有有限个指数vi不等于零.）那么v(m)就是向量(v1,v2,···）.举例来说，在第四个位置后去掉后面无数个零，我们有      v(75)=(0,1,2,0),    v(168)=(3,1,0,1),    v(360)=(3,2,1

13、,0),    v(560)=(4,0,1,1). 按我们的意图来看，指数向量给出了太多的信息。我们仅仅对平方数感兴趣，既然一个正整数m是平方数当且仅当v(m)的每一项都是偶数，我们应对每个指数取模2的剩余。由于矢量v把乘法运算变为加法，我们要找的数就是它们的指数向量和取模2后为零向量。上述的指数向量取模2后缩减为      v(75)(0,1,0,0) mod 2,    v(168)(1,1,0,1) mod 2,  &#

14、160; v(360)(1,0,1,0) mod 2,    v(560)(0,0,1,1) mod 2. 注意到它们的和正是零向量！这样75，168，360和560的乘积就是一个完全平方数。为了系统化这个程序，Brillhart和Morrison建议选择某个数B，并且只关注系列数中能在前B个质数集上完全分解的的那些数。所以在上面那个例子中，我们有B=4.只要找到B+1个这样的数，我们就有B维矢量空间FB2中的B+1个矢量。由线性代数可知它们必定是线性相关的。但是什么是F2域上的线性相关关系呢？既然唯一的数量值是0和1，一个线性相关关

15、系就是一个相加等于零向量的子集。从线性代数中我们有很多算法能帮我们找到这个相关性。提一下，这次我们还算是幸运的，既然我们仅用了四个向量就找到了相关性，在糟糕的情形下可能要五个向量。Brillhart和Morrison称这些素数p1,p2,.,pB为“因子基”。（更准确的说，他们排除了那些n不可能是它们的二次剩余的质数pj,这些质数不可能整除连分数方法中的整数Qi，也不可能整除Kraitchik方法中的整数Q(x).)怎么选择B呢？如果B选得小，那么我们不用收集太多数就可停下来。但如果选得太小，那么在系列数中找到一个在前B个素数上完全分解的整数可能性就非常小，找到一个都很困难。这样在某处就有一个

16、最佳平衡点，对于用Kraitchik方法分解2041，最佳平衡点的结果是B=4.有些备用数可能是负的。我们怎么处理它们的指数向量呢？显然我们不能忽视这个符号，因为平方数不可能为负数。然而，我们可以在每一个指数向量里加一个额外的维度，对正数取0值，对负数则取1。（就好象这是因子基中的一个质数一样。）所以允许收集的数为负数只是在维度上大了一位。例如，让我们再考虑数2041并尽力用Kraitchik方法来分解它，但现在允许用负数。这样使用多项式Q(x)=x2-2041和因子基2,3,和5，我们有    Q(43)=-192=-26·3 &#

17、160;(1,0,1,0)    Q(44)=-105    Q(45)=-16=  -24   (1,0,0,0)    Q(46)= 75= 3·52  (0,0,1,0),这里相关指数的第一个坐标是-1.所以使用包括2，3和5的更小的因子基，但也允许负数，我们很幸运，目前收集到的三个向量是线性相关的。这样就有了同余式(43·45·46)2(-192)(-16)(75) m

18、od 2041,即124724802 mod 2041.这又给出了2041的因子13，因为（1247-480，2041）=13.最后的求解最大公约数的步骤会得到一个非平凡分解吗？答案是不一定.读者可以试试2041的又一组平方数解集.例如x=41,45和49时,算出Q(x)，最后得到同余式601214402 mod 2041.用前面说的术语，这个同余式是平凡的，因为601-1440 mod 2041.这样，可以肯定最大公约数(601-1440,2041)的值是很无趣的因子1. 平滑数和复杂性理论的激励在70年代末，随着RSA公开密匙加密系统的出现，预测大数分解的强度变得非常重要。我们不

19、仅要知道当前技术的状况，也需要预测超出现在可行的更大的数的分解会带来什么。尤其是，凭经验看似乎价钱一样的计算机每一年半到两年速度和容量都翻倍。假定是这样并且没有新的分解算法，十年内技术的状况是怎样的呢？对这类问题，复杂性理论就用得上了。人们可能会分析Kraitchik的多项式法或Lemer-Powers的连分数法到底怎么样？70年代末Richard Schroeppel在内部通讯上提议了一种方法。从本质上讲，他开始把连分数方法中的Qi和Karitchik方法中的Q(x)看作是“随机的”. 如果你被给出某个特定边界X下的一个真实随机数流，在你发现某个子集相乘可得到平方数之前要等多久呢？

20、    一个数如果它的质因子都不大于Y,a那么称它为Y-平滑数.（这样一个数能在不大于pB的质数集上分解的数就是pB-平滑数.)一个不大于X的随机正整数是Y-平滑数的概率是多少呢？它等于(X,Y)/X(X,Y)/X,其中(X,Y)是区间1,X中的Y-平滑数的个数。这样随机数要测试它是否是Y-平滑数，期望的测试次数是概率的倒数，即X/(X,Y).但我们要找(Y)个Y-平滑数，这儿(Y)定义了不大于Y的质数的个数。所以要测试的随机数的期的论据，它假定由n的平方根的连分数或Kraitchik的二次多项式产生的辅助数是“随机的”，在是Y-平滑数的属性上也是随机的

21、。这点没有被证明。另外，得到很多个是Y-平滑数的辅助数据不一定能保证分解n，既然每次我们使用F2域上的线性代数来收集同余平方数，那就有可能运气很差，只得到无助于分解的平凡解。再说由于假定了的随机性，我们不会预期没完没了的坏运气，这个启发再次支持了上述推测。    上文谈到，这个复杂性论据首先由Richard Schroeppel70年代末在未出版的文章中提出。（在参考文献4中他陈述了上面指出的结论，虽然在那时它不是一个定理，甚至也不是一个事实上的推测。）有了研究复杂性的工具后，这次他使用这些工具找到了一种新的分解方法，后来被称为线性筛法。线性筛法是二次筛

22、法的先驱，也是二次筛法的灵感来源。两种筛法的故事（三）使用复杂性理论提出一个更好的算法：二次筛法上述的复杂性理论梗概让我们可能找到某些可以改进的地方。现在是时候识别那些能在不大于Y=pB的质数内完全分解的辅助数，即那些Y-平滑数。在上面的论证中我们假定这需要(Y)个步骤，其中(Y)是不大于Y的质数的个数.一个数是Y-平滑数的概率按上面的符号标记是(X,Y)/X. 你可能会预计到并且实践中也很容易验证，当Y有适当的大小，并且X非常大时，这个概率是非常非常小。这样辅助数依次冒出来，而我们对每个这样的辅助数都要投入大块的时间，仅仅是为了验证它是不是Y-平滑数，不是话我们会丢弃它。1981年

23、初我意识到人们可以采用某种和厄拉托塞尼筛法密切相关的东西来快速识别Kraitchik的二次多项式Q(x)=x2-n中的平滑数。厄拉托塞尼筛法是用来发现自然数的一个初始化区间的所有质数的著名工具。第一个循环是质数2，然后依次间隔一个数划去后面的数，即4,6,8,等等。下一个未划去的数是3，对它也进行一个循环，即依次划去后面的第三个数。照此方法继续下去。最后到达筛法区间的上限的平方根的时候，可以终止筛选程序并圈出所有保留下来的未划去的数。圈出的数就是质数，划去的数则是合数。要注意厄拉托塞尼筛法只是找到了所有质数。一些被划去的数可能被重复划去了很多次。例如，30被划去了三次，42也一样，因为它们都有

24、三个质因子。这样我们可以快速扫描数列寻找那些被划去多次的数，也就是有很多质因子的数。显然有很多质因子跟全是小质数因子这两者之间有某种相关性。但我们可以比仅仅有一个相关性做得更好。通过用质数分解而不是划去，象30和42这样的数在筛选完成后会变成1，因为它们能在筛选集中的质数下完全分解。所以(二次筛法)不是用筛选区间的上限的平方根内的质数集来筛选，应该说我们仅仅用Y以内的质数来筛选。在筛选过程完成后所有变成1的数都是Y-平滑数。但不是每个Y-平滑数都被筛选中了。例如，60在被质因子分解后变成了2。问题出在它有小于Y但幂次大于1的质因子。我们可以修正这点，办法是也用质数的更高幂次筛选，以及用优先的质

25、因子反复试除。那么最后变成1的数就会是区间内的所有Y-平滑数了。和用试除法来确认每个候选数是不是Y-平滑数相比，二次筛法的速度难以置信地快。如果筛选区间是N，执行的步骤仅仅需要约NloglogY次，或者说每个候选数要lologY步.所以在一个初始化的区间我们能快速识别Y-平滑数。但我们能用这个办法来识别二次多项式Q(x)=x2-n里的Y-平滑数吗？一个筛法起作用的是对筛选因子集里每个模数m，m的倍数按固定的间距出现在数列中。这样举个例子来说，取一个质数p,我们问，x是多少时p能整除Q(x)呢？这个问题并不难。如果n（待分解的数）是p的非零二次剩余,那么当且仅当xa或b mod p时有两个二次剩

26、余类 a mod p和b mod p满足Q(x)0(mod p).如果n不是p的二次剩余，那么Q(x)不可能被p整除，对p不用做任何计算（即因子基可排除p).所以从本质上讲可以用一样的方法，我们可以对每个候选数在约loglogY步里识别Q(x)中的Y-平滑数。复杂性论证又会告诉我们什么呢？分解n的时间现在大约是exp(sqrt(lognloglogn);即指数里的根号2不见了。这是个大成就吗？你可以赌一把。二次筛法的低复杂性和其他的友好特性能让可分解的数的长度增加一倍（和上面讨论的连分数方法相比）。作为复杂性论证和无需数值实验的结果，二次筛法诞生了。 算法执行和改进提高事实

27、上，我很庆幸二次筛法成为一种有竞争力的算法。往往是，当一个人通过复杂性论证和思维试验发明了一种独特的算法后，结果却可能是因为太棘手而成不了有竞争力的方法。另外，即使基本的思想很合理，一些重要的改进还要等那些实际尝试的人来发现。事实上后来二次筛法也是这样。第一个尝试用二次筛法分解一个大数的人是Joseph Gerver(参看9).用这个任务作为学习编程的机会，他成功地分解了一个来自Cunnngham项目的47位数。这个项目本世纪由Lt.-Col.Allan J.Cunningham和H.J.Woodall发起，目的是分解形如bn±1的数，其中b是不大于12且不是幂的数，n可以是很大的数

28、(参看3).Gerver分解的数是3225-1的一个因子。实际上在试图让人们尝试二次筛法时我也有一个困难时期。很多Cunningham项目的分解者似乎对连分数方法很满意，他们认为和连分数方法里的数Qi相比，Kraitchik的多项式Q(x)的更大数值对羽翼未丰的二次筛法来讲，是一个巨大的障碍。但1982年秋天在Winnipeg召开的一个会议上，我说服了Sandia实验室的Gus Simmons和Tony Warnock在他们的Cray计算机上试一下二次筛法。Jim Davis和Diane Holdridge被分派在Cray计算机上为二次筛法编程的任务。结果他们不仅成功了，而且很快创造了记录。D

29、avis发现了一个能减少上文提到的障碍(待分解数较大)的重要改进。他发现了一个方法，在头一个多项式Q(x)=x2-n的数值变得太大时，可以切换到其他二次多项式。虽然这个方法不能在本质上改变计算复杂度的估值，但它让二次筛法更具可行性。他们的成功不仅登上了Mathematical Intelligencer杂志的封面(1984年卷六封三，在一台Cray计算机上分解了由71个1组成的大数）,甚至在当时的时代杂志上登了一篇短文，文章末尾是Simmons的一张照片。让人好笑的是在Sandia团队开始这个项目前，又一个Sandia团队已经设计和制造了给公开密匙加密系统使用的RSA芯片，它的安全性基于我们不

30、能分解100位左右的大数。显然现在它不是足够安全了，芯片不得不报废。在同一时期Peter Montgomery独立地提出了又一种稍微好一点的切换多项式的办法，现在我们使用他的方法，不再使用Davis的方法。相对于连分数方法，二次筛法的一个很大的优点是它特别容易把因子分解的任务分散给很多计算机做。例如，通过使用很多个多项式，每个计算机可以按它得到的一系列多项式进行筛选运算。早期二次筛法的巨大成功来自超级计算机，例如Sandia实验室的Cray XMP.但随着低成本工作站和个人计算机的增多，很自然地二次筛法被并行运算，数据记录再传送给那些对大数组织分布式攻击的人。 Robert Silv

31、erman是第一个使用多台计算机来分解一个大数的人。后来，Red Alford和我使用100多台很一般的且没联网的PC分解了两个100位数参看2).但我们没有创造记录，因为当我们正在作业当中时，Arjen Lenstra和Mark Manasse在分发分解问题上迈出了一大步。他们把二次筛法的程序放到因特网上，向来自世界各地的人们索取计算机时间.正是通过这种分散的努力129位的RSA挑战数最终在1994年被分解了。这个项目的领导者是Derek Atkins,Michael Graff,Paul Leyland 和 lenstra,真实时间花了8个月，用了超过1017个运算步骤

32、。二次筛法基本上是一种非常简便的算法，这也是它的优点之一。由于它的简便性，人们会想到有可能设计一种专用计算机，专门用来分解大数。佐治亚大学的Jeff Smith和Sam Wagstaff已经实现了一个执行连分数方法的专用处理器。它的绰号是“佐治亚攻击者”，它取得了一些有限的成功，但被在通常计算机上运行的二次筛法分解实例盖住了光芒。Smith,Randy Tuler 和我（参看21）认为我们应该构建一个二次筛法专用处理器。名字叫“Quasimod",作为二次筛法的运算动力，已经构建了但从没正常发挥功能。这一点由于低成本高性能的计算机呈指数式增长普及，变得没有实际意义。两种筛法

33、的故事（四）数域筛法的黎明John Pollard,从Don Coppesmith、Andrew Odlyzko和用过二次筛法的Richard Schroeppel（参看6)的离散对数算法那儿得到灵感，1988年发表了一封信给几个人，描绘了他的通过代数数域来分解特定大数的想法。最初他的想法不是用来分解任何大的合数，而是针对某些“理想”的合数，这些合数的特点是它们非常接近某个幂并有某些其他好的特性。他通过对整数227+1的分解阐述了思想，这个数正是第七个费马数。这个数是有来历的，它是近二十年前连分数方法成功分解的第一个数。我得承认开始的时候对Pollard的方法不太热心，既然它似乎只能应用到很少

34、的数上面。但是有一些人严肃地对待它，其中一个人是Hendrik Lensrta.他改善了这个算法的一些细节，和他的兄弟Arjen、Mark Manasse一起着手用这个算法分解来自Cunningham项目中的几个数。在成功了几次后（其中值得一提的是一个138位数），Brian LaMacchia和Andrew Odlyzko为了配合这个方法又对大的稀疏矩阵的处理方法取得了一些进展，Lenstra兄弟俩和Manasse把目标锁定在一个有名的大数229+1上，即第九个费马数.显然它超出了二次筛法的分解范围。而Hendrik Lenstra自己的椭圆曲线方法，这是他在1985年找到的方法，此法特别适

35、合分解具有相对小的质因子（30位左右）的大数，到目前为止对分解F9也无济于事。最后Lenstra兄弟和Manasse在1990年春天成功地找到了229+1的质因子。这个轰动一时的成就向世界宣布Pollard的数域筛法的到来。但对于一般的大数又会是什情况呢？1989年夏天我去温哥华参加加拿大数论协会会议时有过一次座谈。那是一次关于大数分解的座谈会，我觉得谈谈Pollard的新方法是个好主意。在去会议途中的飞机上我对这个方法做了一个复杂性理论分析，以了解它在一般大数下的效果，并假定各种技术困难不存在且对一般大数能用这种办法。结果我很震惊，这种目前还不存在的算法的复杂度大概是 .它和二次筛

36、法复杂度的主要区别是关键性的指数数值，logn的幂从1/2减少到1/3.如果说在从连分数方法转向到二次筛法时，由于指数的常量减小而产生了很大的进步的话，那么可以想象由于减小了指数的指数会产生多大的效果。显然这个方法值得认真思索！这儿我不想给人留下这样的印象，即我当时通过复杂性分析已经单独找到了一种把数域筛法应用到一般大数的方法。远不是这样。我只不过是暗暗地对这个将来的令人兴奋的可能性关注了下。说到底这种可能性的实现大部分要归功于Joe Buhler,Hendrik Lenstra以及其他人。另外这之前几个月，Lenstra已经对Pollard的方法应用到特殊类型数的复杂度做了分析，他也是得到了

37、一样的表达式 .我自己的分析是基于一些乐观的代数学假定和一些我期望是站得住的论据，这些平均化的论据针对一般的大数。Pollard的方法分解n的起点是在整数域上构造一个最高指数项系数为1的不可约多项式，并且有一个整数m使得f(m)0 mod n.多项式应该有一个“适当”的次数d,意思是如果n是100到200位数，那么d应为5或6.例如象第九个费马数这样的大数，n= ,它很容易构造出这样的多项式.注意到8n=2515+8.所以设f(x)=x5+8,并且m=2103.  这样的多项式会可能会有什么用呢？设代数整数是f(x)的一个复数根，环Z由所有的多项式表达式

38、组成，通过用剩余m mod n替代每个出现的我们有一个很自然的映射ZZ/(nZ).我们设定的f,和m的条件保证能很好地被定义。不仅如此，是一个环同态。现在设想S是具有两个属性的互质整数对<a,b>组成的有限集合。第一个属性是S中的所有对<a,b>构成相应的代数整数a-b,它们相乘后是环Z里的一个完全平方数，设为2. S的第二个属性是S中的所有对<a,b>构成相应的整数a-mb是整数域Z中的完全平方数，设为2.既然可以写成的多项式表达式，我们可以用m替换出现的每个，得到一个整数,且()mod n.这样就有接下去我们知道怎么处理u和v.就象Kraitchik在7

39、0年前告诉我们的一样，我们希望找到一个非平凡同余式，即（u和v不是相同剩余类）,如果是这样，我们就得到最大公约数(u-v,n),一个n的非平凡因子。到哪里去找设想的<a,b>数对构成的集合S呢？至少对S的第二个属性，即数列a-mb的乘积是平方数，很显然我们可以再次使用指数向量和一个筛法。这儿的变量a和b就类似于二次筛法中的Q(x)的一个变量。所以我们视此为线性多项式的一个参数族。我们能固定b让a通过某个区间，再更换到下一个b,一直这样重复。但S也要有第一个属性：对同样的数对<a,b>,a-b也是Z里的平方数。Pollard告诉我们，如果在好的情形下Z是Q()里的代数整数

40、环，如果这个环是一个唯一分解域，如果我们知道一个单元基，那么我们同样可以建立代数整数a-b的指数向量，本质上可以重复相同的算法。为了同时保持S的两个属性，这需要涉及更长的指数向量，它的维数包括所有的小质数，a-b的符号，Z中的所有“小”质数，还有单元基中的每个单元。 但对一般的大数n我们又怎样设想呢？实际上，我们又怎样达成找到多项式f(x)和整数m使得f(m)0 mod n这第一步呢？并且如果我们找到了f(x)后，为什么我们还要希望Z有上面说的所有好的特性以完成Pollard的计划工作呢？两种筛法的故事（五）数域筛法的演化可以从一个很简单的设计开始，那就是找到f(x)和m.办法是象上

41、次一样找到f(x).首先，人们要先决定函数f的阶d.接着可以设m是n的d次方根的整数部分.现在把n写成m进制的多项式，以便得到  ,这儿底m的“数位”满足0<=ci<m.(如果n>(2d)d,那么领头的“数位”cd是1.）多项式现在出现在我们面前；它是 .这样我们有了一个首项系数为1的多项式f(x),但它是不可约的吗？有很多策略把整数域Z上初始多项式分解成不可约的因子.事实上，我们有值得庆贺的多项式时间的算法，由Arjen Lenstra,Hendrik Lenstra 和 Laszlo Lovasz所提出，用来分解Zx上的原

42、始多项式（运行时间的上限是各系数的数值还有阶的和的一个固定次的幂）。所以假定我们不走运，上面的程序得到了一个可约的多项式f(x),即有f(x)=g(x)h(x).那么有n=f(m)=g(m)h(m),从来自John Brillhart,Michael Filaseta和Andrew Odlyzko的结果来看，这个n的分解是非平凡的。而我们的目标就是找到n的非平凡的分解，所以这根本不能说是不幸的！既然几乎所有的多项式是不可约的，更有可能的情况是这个构造将让我们开始数域筛法的过程，我们没法立即能分解n.现在还有一个主要问题，我们怎么绕开这个事实，即没有理由期望环Z有任何好的特性。到1990年，Jo

43、e Buhler,Hendrik Lenstra和我已经解决了剩下的困难，结合 Len Adleman的一个非常实用的方法（参见1),此方法简化了我们的一些构造，最终在附录11中发表了“一般数域筛法"的描述。这儿有一个我们做的事情的简明摘要。a-b的范数N(a-b)(Q上）很容易计算出来等于bdf(a/b).这是f的平均化版本。如果N(a-b)是Y-平滑的，我们定义a-b是Y-平滑的。既然范数是相乘的，接下来就有如果不同的代数整数a-b的乘积是一个代数整数平方数，那就也有范数的乘积是一个整数的平方数（但是反过来不成立）。注意我们知道怎样找到一个数对<a,b>的集

44、合使得N(a-b)的乘积是个平方数。这可以通过用一个筛法找到N(a-b)的Y-平滑值并通过F2上的指数向量代数结合这些数值。    但有了N（a-b)的乘积是平方数，只是a-b的乘积是平方数的一个必要条件，还远远不是充分条件。主要原因是范数映射把不同的理想质数变成Z中的同样的事情，所以范数很容易成为平方数但没有是平方数的证据。例如，Zi中两个一阶的质数，2+i和2-i,有范数5.它们的乘积是5,而它的范数25=52,但(2+i)(2-i）=5是非平方数。（注意如果我们在Q()里的所有代数整数环上作业，那么a-b的所有理想质因子（a和b为互质整数）是一阶的

45、;即，它们的范数是有理质数）（范数为有理质数的理想质因子是一阶的）。对每一个质数p设Rp是f(x)0 mod p的解的集合（每一个质数p都有一个对应的集合Rp）。当我们通过一对<a,b>，用p除N（a-b)时，那么有一些p上的理想质数能整除a-b.并且我们知道是哪一个，既然a/b和Rp中的某一个对模p同余，这可以用来区分p上的不同理想质数。这样我们能对每个质数p安置指数向量坐标为#Rp,并追踪a-b的理想质数分解。注意#Rp<=d,f(x)的阶。所以我们已经克服了主要的困难，但仍然有很多障碍。我们被假定是在环Z上作业，而这可能不是完全的代数整数环。事实上，这个环可能不是戴德金

46、域，所以我们可能不能分解成理想质数，以上段落仅仅能保证由代数整数a-b的乘积产生的主要理想数是某个理想数的平方，但不能说一定是一个主要理想数的平方。即使它是一个主要理想数的平方，它可能不是一个代数整数的平方，因为那些单元。（例如，-9产生的理想数是Z中的一个理想数的平方，但-9不是一个平方数。）并且即使数a-b的乘积是一个代数整数的平方，我们又怎么知道它是Z里的一个元素的平方呢？上面的障碍通过使用f'()2作为一个乘法器比较容易解决（原作者注：有个定理是如果f是Z上的首项系数为1的不可约多项式，且有一个复数根，若是Q（）的代数整数环，那么f'()属于Z.所以如果2是Q（)的代数

47、整数环中的平方数，那么f'()22也是Z里的一个平方数。）,但其它的障碍似乎要困难些。然而，Len Adleman(参看1)的一个简单又聪明的办法能有效地克服这些困难。要点是即使我们不得不面对一些讨厌的障碍，它们形成，模平方数，一个很少维数的F2向量空间。所以第一个想法就是忽略这些问题。但维数不是那么小。Adleman建议随机选一些二次特征并使用它们的值结合a-b这些数来扩大指数向量集。（随机二次特征在开头有一个固定选项。）所以我们可以整理数组a-b的乘积成一个”障碍空间“上的平方数，而且它非常有可能是实际上的平方数。例如，用一个非平凡数-9来考虑上面的问题。如果我们以某种方式不”看“

48、符号问题它确实看起来象一个平方数，因为我们知道对每个质数p,-9的质数分解的p的指数是偶数，我们仍然可以发现这个问题。考虑一个评估点为-9的二次特征，此时的勒让德符号，如果-9是模p的平方数，勒让德符号为1，如果-9不是模p的平方数,勒让德符号为-1.我们用p=7来试一下。很容易计算出勒让德符号值为-1.所以-9不是模7的平方数，它也不可能是Z中的平方数。如果-9是某个模p的平方数，却无法保证它是Z中的平方数。例如，如果我们5而不是用7试，那么-9将看起来象个平方数。Adleman的办法是在那些被选择的二次特征上评估a-b的平滑值，并用线性代数建立一个元素具有如下两个属性：它的未扩大的指数向量

49、全部为偶数记录，在每个特征上它的值均为1.从一个启发性的观念看，这个代数整数很有可能是一个平方数。如果它真不是平方数的话，我们可以继续使用F2上的线性代数建立又一个候选数。要确认算法，仍然有一些困难。其中一个是”平方根问题“。如果你有不同有理整数的质数分解并且它们的乘积是平方数，你很容易通过它的质因子分解式找到平方数的平方根。但在Z上问题不是那么直观。尽管如此，还是有策略解决这个问题，虽然它仍然是算法中的一个计算性的值得关注的步骤。有兴趣的读者可以查阅参考文献15.可能现在还不清楚为什么数域筛法是一个好的分解算法。在一个分解算法如二次筛法或数域筛法里的一个关键数值是我们以前称为"X&

50、quot;的东西。它是一个那些结合成一个平方数的辅助数们的评估值。知道X你就可以知道复杂度；它大约是 .在二次筛法中我们有X约为n(1/2+).但在数域筛法中，我们可以选择多项式f(x)和整数m以如下的方式：（a-mb)(a-b)(从这些数中我们希望找到平滑数）的边界值X的形式为 .这样我们用来筛选平滑数的辅助数的位数大约是n的位数的三分之二次幂，而二次筛法的辅助数的位数只是大约为n的位数的一半强。这就是为什么数域筛法和二次筛法相比只是渐近的更快。更早前我指出了数域筛法分解n的启发式运行时间具有表达式,但我没有说明”c“是什么.依据数域筛法使用的版本不同，c实际上有三个值.

51、”特殊“的数域筛法，更接近于Pollard的原始方法，能很好地适合于象229+1这种接近某个高次幂的数，它的c值是c=(32/9)1/31.523."一般”的数域筛法是我在本文中描绘的方法，适用于任何非幂的奇合数。它的c值是c=(64/9)1/31.923.最后，Don Coppersmith(参看5)提出了一般数域筛法的又一版本，此版本使用了很多多项式。这种方法的"c“值是 .这个算法渐近地代表了最坏情况下分解算法的冠军。有人认为Coppersmith的算法完全不切实际，但在文献8中考虑了使用几个多项式的想法是否可能有一些实际价值。两个筛法的故事（六） 

52、;分解艺术的现状1996年春天一个大的团队（参看7)使用一般数域筛法完成了一个130位的RSA挑战数的分解。通过这个严酷考验最终数域筛法超越了二次筛法，其从1983年一直是分解最大的”硬“数的算法冠军。虽然实时时间和两年前用二次筛法分解129位的挑战数所花的时间差不多，但估计这个新的分解只花了大约15%的计算机时间。这个差异的原因是由于项目只使用了更少的计算机以及一些”停机时间“，因为正在写算法最后阶段的编码工作。 头二十个费马数 在表中Pk代表一个k位的十进制质数，而Ck代表一个我们不知道非平凡分解的k位的十进制合数.费马数的分解历史是大数分解历史的缩影。费马本人知道F0

53、到F4,然后他猜测接下来所以具有22m+1形式的数都是质数。然而，欧拉发现了F5的分解式。要找到这个分解式不算太难，如果使用以下结论的话，它本质上源于费马，即若p是Fm的一个质因子则必有p1 mod 2(m+2),其中m>=2.这样F5的所有质因子必有 1 mod 128，它的第一个这样的质因子不是一个更小的费马数，而是641.通过这个方法F6也被分解了（1880年由Landry完成），还有很多其他的费马数的”小“质因子也找到了，包括这张表以外的超过80个质因子。费马数F7是Brillhart-Morrison连分数分解方法的第一个成功例子。Brent和Pollard使用Pol

54、lard的 ”rho"方法的改编版分解了F8.而本文中讨论的F9也被数域筛法分解了。费马数F10和F11被Brent使用Lenstra的椭圆曲线方法分解了。我们知道F14,F20和F22是合数，但我们不知道这些数的任何质因子。运用Pepin的判定标准发现它们是合数：Fm当且仅当3(Fm-1)/2)-1 mod Fm.我们不知道它是质数还是合数的最小的费马数是F24.很多数论学者现在认为F4后的每个费马数都是合数。费马数联系着欧拉的一个久远的问题：哪种n可以用尺规作出正n边形？高斯证明当且仅当n>=3且n的最大奇因子是确定的费马质数的乘积。高斯的定理是在他19岁时完成的，这个定理

55、一直跟到他死：他的墓碑上刻了一个正十七边形。所以二次筛法和数域筛法的交叉点在哪儿呢？这个问题的答案跟你和谁谈有点关系。每个人都同意一件事：对更小的数而言即小于100位数二次筛法更好，对更大的数而言即大于130位数数域筛法更好。象这类问题没有明显答案的一个原因是这个事情高度依赖于编程和使用计算机的种类的得分。例如，在文献7中报道说数域筛法的表现对计算机有多少内存很敏感。二次筛法也是这样，但没到那个程度。在本篇简短的回顾中有很多东西没说。一个重要的省略是对算法和二次筛法及数域筛法的线性代数部分的复杂度的讨论。开始时我们使用了高斯消去法，Brillahrt和Morrison在使用连分数方法时就是用它

56、。但问题的规模越来越大。当今一个一百万规模的分解基在创纪录的分解上也是整装待发。显然，一个线性代数的问题即一百万乘以一百万不是一个可以小看的事情。有一些有趣的新工作，这涉及改编的迭代方法，用来处理从真实数的离散矩阵到F2上的离散矩阵。最近的文献可参看14.在数域筛法基本思想上的几个改进显示了一些希望。一个是可以用bkg(a/b)替代数域筛法中使用的线性表达式a-mb,其中g(x)是k阶的环Z上的不可约多项式（满足g(m)0 mod n).即我们使用两个多项式f(x)和g(x)，它们有一个相同的根m mod n(原始的方案是我们有g(x)=x-m).这是一个当前研究的课题以配合选择多项式的新策略

57、。对通用数域筛法的又一变动是用Coppersmith建议的路径里的一族多项式来替代多项式f(x).关于数域筛法以及这两种方法的描述，可参看8.离散对数问题（给定一个循环群，通过发生数g和群中的一个元素h,找到一个整数x满足gx=h)在密码学中是很令人感兴趣的。上文谈到，Pollard的数域筛法的最初思想也脱胎于离散对数算法。我们已有完整的过程周期，因为Dan Gordon、Oliver Schirokauer和Len Adleman已经给出了数域筛法的各自改进，可以用来计算有限域上的乘法群里的离散对数算法。最近的文献查阅，可参看22.关于素性判定的主题我还没作任何谈论。通常识别一个数是不是合数

58、比要分解它容易得多。当我们使用复杂的并耗费时间的分解方法来分解某数时，我们已经通过其他测试知道它是一个奇合数并且不是一个幂。我已经简略地提过Hendrik Lenstra的椭圆曲线分解方法。这个算法对所有属于一个小集合里的合数比二次筛法和数域筛法都更有效，而对那些所谓的“硬”数，我们还是保留各种筛法。分解也有严密的一面，研究者们竭力进行探索，证明关于分解算法的定理。到目前为止，我们证明的定理中概率性方法比确定性的方法数量要更多。我们似乎不能完全否认不同的实际方法，比如二次筛法和数域筛法，实际上像打广告一样工作。幸运的是，我们努力要分解的数还没被通知缺少证明。更多的阅读资料，我已在参考文献中建议

59、了几个，还可以参看10,13,17,18,19,20.另外，当前我正在和Richard Crandall合作写一本书，PRIMES:A computational perspective(质数：一个计算学视角),将在1997年的某个时间出炉。我希望我已经和大家沟通了关于二次筛法和数域筛法进展后面的一些想法和令人兴奋的事情。从这个发展历程可以看到理论复杂度估计和好的设计灵感的相互作用。二者缺少任何一个，都不能把我们引领到今天的所在。致谢这篇文章是1996年4月30号到5月2号，作为Lehigh大学举办的投掷者演讲系列中的一部分，我发表的同名演讲稿的基础上写成的.我怀着感激的心情向他们对这篇文章写

60、作的支持和鼓励以深深的致意。我也要感谢Notices杂志的编辑，特别是Susan Landau,为着他们的鼓励。还要为以下这些个人的关键性评论而致谢：Joe Buhler,Scott Contini,Richard Crandall,Bruce Dodson,Andrew Granville,Hendrik Lenstra,Kevin McCurley,Andrew Odlyzko,David Pomerance,Richard Schroeppel,John Selfridge,和Hugh Williams.参考文献1 L. M. Adelman, Factoring numbers using singu-lar integers, Pr