素数判定与大数因子分解问题

无心人

【世界数学难题】素数判定与大数因子分解问题（上）
http://hi.baidu.com/caronation/b ... 3bfcf482025c5d.html

序言
　　数论中一个最基本、最古老而当前仍然受到人们重规的问题就是判别给定的整数是否素数(简称为素数判别或素性判别)和将大合数分解成素因子乘积(简称为大数分解)。在历史上，这个问题曾经吸引了包括费马(Fermat)、欧拉(Euler)、勒让德(Legendre)和高斯(Gauss)在内的大批数学家，他们花费了大量的时间和精力去研究这个问题。高斯在其著名的《算术探讨》(《Disquisitiones Arithmeticae》)中称道：“把素数同合数鉴别开来及将合数分解成素因子乘积被认作为算术中最重要最有用的问题之一。”我国的《易经》中也对这个问题作了研究。
　　素数判别和大数分解这个问题具有很大的理论价值。因为素数在数论中占有特殊的地位，鉴别它们则成为最基本的问题；而把合数分解成素因子的乘积是算术基本定理的构造性方面的需要。人类总是有兴趣问如下的问题：$2^131-1$是否素数？由23个1组成的数是否素数？怎么分解31487694841572361？对素数判别和大数分解的研究必然会丰富人类的精神财富。更重要的是，素数判别和大数分解具有很大的应用价值。在编码中，需要讨论某类有限域及其上的多项式，这类有限域就是由素数
　　在快速数论变换中，要讨论Z/nZ上的卷积运算，就要知道Z/nZ的乘法群的构造，而这就依赖于将n分解成素因子的乘积。下面介绍的RSA公开密钥码体制更加说明了这个问题的两个方面在实际应用中的作用。1977年，艾德利曼(Adleman)、希爱默(Shamir)和鲁梅利(Rumely)发明了一个公开密钥码体制。在这个密码体制中，对电文的加密过程是公开的，但是，你仅知道加密过程而未被告知解密过程则不可能对电文进行解密。他们的体制就是依靠这样一个事实：我们能够很容易地将两个大素数(譬如两个百位素数)乘起来；反过来，要分解一不大整数(譬如200位)则几乎不可能。(关于RSA体制的详细介绍，请参阅文献[1])。因此RSA体制就与素数判别和大数分解有密切联系。首先，要具体建立一个RSA体制就需要两个大素数，因而就涉及到寻找大素数的问题；而RSA体制的破译之可能性就依赖于分解一个大数可能性。于是，RSA体制的建立与破译就等价于素数判别与大数分解问题。近来，由于计算机科学的发展，人们对许多数学分支的理论体系重新用计算的观点来讨论。从计算的观点来讨论数论问题形成了当前很活跃的分支－—计算数论。而素数判别和大数分解成为这一分支的重要组成部分。在这一部分里提出了两个重要的、悬而未决的问题：是否存在判别素数的多项式算法？是否存在分解大整数的多项式算法？已知道“分解整数”这个问题是一个NP完全问题，因此对上面第二个问题的讨论是解决计算机科学中的难题：“NP完全问题是否一定是多项式算法可解的？”的一个突破口。因此，素数判别和大数分解对计算机科学来说也是很有价值的。
　　最直接的素数判别和大数分解方法就是试除法，即对整数n，用2，…，n-1去试除，来判定n是否素数，分解式如何。这个方法是最简单的一个方法，古希腊时就被人所知，但这个方法对较大的数(20位左右)就要耗费很多时间。在本世纪四十年代电子计算机出现之前，尽管产生了许多素数判别和大数分解方法，但因为用手算，速度太慢，很多方法在实用中即使对十几位的数也需要好几天，而对更大的数就无能为力了。随着计算机的出现及发展，人们开始用这个有力的工具来研究素数判别和大数分解。到六十年代末期，已产生了许多新方法，历史上的许多方法也得到了应用，使得对四十几位数的素数判别可以很快得到结果。而到七十年代末，数论学家和计算机专家们已深入地研究了这个问题，得到许多实际有效的方法。用这些方法在较好的计算机上判别一个100位数是否素数只需不到一分钟；分解70位左右的整数也是日常工作了。这些成果已引起人们的普遍关注。在这个领域中的研究空前活跃。虽然离问题的彻底解决还很远，但在本领域中已取得了一个又一个的突破。在这方面的研究必有光辉的前景。
　　我们写这个小册子的目的是要介绍素数判别和大数分解的发展历史、一般理论、各种方法及最新成果，是想让许多非专业的读者了解这个方向的内容和进展情况。当然，只有在这些定理的证明较为初等而又不太长时，我们才给出其证明。因为这个方向与计算机科学的密切关系，我们还要结合计算量来介绍一些数论中常用的基本算法。
　　除了极个别内容，如第二章第七节，本书的绝大部分内容只需要某些初等数论的知识，它们可以在任何一本介绍初等数论的书中都能找到，如文献[1] 。对于广义黎曼猜想，我们写了一则简短的附录。作为“世界数学名题欣赏丛书”中的一本，如果读者在欣赏之余，还打算进一步学习和探讨的话，那么，后面所列的文章和书目，可供参考。
　　限于水平，本书的缺点和错误一定不少，我们期待着读者的批评指正。
1．算法及其计算量的概念
   通常，解决问题的方式有两种．其一是对问题的每个对象(也称作输入)，直接给出答案，其二是给出一套规则，使得对问题的任何一个对象(输入)，解答者可依照这些规则、机械地执行运算，能在有限步内得到答案．这里的第二种方式就是问题的算法解答，这时也称问题是算法可解的，而所给出的规则就称为算法．
   例 在复数范围内解一元二次方程．这个问题的输入即是具体给出的一元二次方程．任给一个方程种解答方式．
    例 判别任意给出的自然数是否素数．
　　熟知，我们没有象上例那样的公式来表明哪个数是素数，哪个数不是素数．但是，我们可以以如下方式解答此问题：对任意给定的数n，用2，3 3，…，n－1去试除n，若其中有一个除尽n，则n不是素数；否则，n是素数．这就是问题的算法解答．注意，算法不可解的问题是存在的．希尔伯特的第十问题就是一个算法不可解的问题．这一点是马递佳塞维奇于1970年证明的．
    对算法可解的问题而言，解答的算法可能很多，我们在实际解决问题时究竟采取哪一种算法呢？这就要求对算法的好坏进行评判．算法的好坏与所谓的计算量有密切关系．人们注意到，对某类问题的解答依赖于一些基本运算．譬如，在排序问题中，比较运算——即比较两个元的先后——是一种基本运算．当然，“互换位置”也可以当作是一种基本运算．一个算法在对问题的某个输入解答所执行的基本运算次数，称为算法对此输入执行的计算量．算法对不同的输入执行的计算量一般不同．在把计算量描述为输入的函数之前，需要对输入给个度量，这就是所谓的输入尺寸．例如，在排序问题中，输入尺寸可定义为待排序的贯的长度．这样一来，计算量可以描述为输入尺寸的函数．算法对问题的所有输入执行的计算量的最大值称为算法在最坏性态下的计算量．如果解决一个问题有两个算法，其中一个算法在最坏性态下的计算量比另一个在最坏性态的计算量少，则称前者在最坏性态下比后者好．若一个问题存在一个算法解，其算法在最坏性态下的计算量是输入尺寸的多项式函数，则称此问题存在多项式算法，也说问题是P问题，否则称它不存在多项式算法．
　　最后，我们谈谈概率算法和确定算法。所谓概率算法就是它的某些步骤是要依靠服从某种分布的随机抽样来完成的，这种随机过程应是有限步内可完成的，而且算法得出的结论应与所作的随机抽样无关，利用随机手段仅仅是为了加快算法的进程或为了方便．确定算法是相对于概率算法而言的，即它的每一步骤都是确定的，不须用随机手段就可完成的．以后，这两种算法都会遇上，凡没有用随机手段的都是确定算法，我们将不作特别说明了．
2．数论中的基本算法
   在数论问题中，输入一般是一个或几个自然数．如果输入是一个自然数n，则定义其输入尺寸为它的二进位表示的位数，即$log_2n+1$，有时也将$log_2n$作为输入尺寸．熟知，数论问题的解答中，自然数的加减乘除这四则运算是基本的运算，而两个个位数的加法、减法和乘法及两位数除以个位数的除法又最基本．因此，我们如下定义数论问题的基本运算：假如我们是在r－进位制中讨论自然数的运算(通常在十进位下讨论，即r=10；而在计算机上，一般在二进位下讨论，即r=2)，则基本运算就是个位数的相加、相减、相乘，两位数除以个位数的除法及向左移位运算(即乘上r)．有了基本运算，就可以来讨论数论中的基本算法了．
   (1)四则运算加法：
    定理1.1 用竖式算法计算两个不大于n的数相加时，其计算量是$O(log_2n)$．

　　减法：同加法一样地讨论，

　　定理1.2 用竖式算法计算两个不大于n的数相减时，其计算量是$O(log_2n)$

    乘法：式算法做n位数与m位数(m≤n)相乘的计算量不多于13mn．设M(n)表示两个n位数相乘的计算量，则$M(n)=O(n^2)$．故可得下面的定理．
定理1.3 竖式算法做两个不超过n的数的相乘时，其计算量是$O(n^2)$
带余除法：带余除法的竖式算法要用文字表述出来比先前的加法和乘法都要麻烦，但它只不过是将小学里做带余除法的过程详细地写出来而已，这里不准备重复这些枯燥的叙述，而只将带余除法的竖式算法的计算量写出来．
　　定理1．4 　实际上，我们是得到这样的结论：一个2n位数除以一个n位数所得的商和余数的计算需要计算量$O(n^2)$,之后，才有定理1.4．而且由此可得，对一个不超过m2的数a取模m得最小非剩余的计算量是$O(log_2 2m)$．
　　关于自然数的乘法，我们还想介绍两个优美的结果，其证明已超出本书的范围．
　　定理1.5 任给一个正数ε，无论如何小，都存在一个乘法算法，它做两个n位数相乘的计算量是$O(n^{1+epsilon})$，或者说，它做两个不大于n的数相乘的计算量是$O(log_2{(1+epsilon)n})$．
　　定理1.6 存在乘法算法，使其作两个n位数相乘的计算量是$O(nlog_2nlog_2log_2n)$，或者说，它做两个不大于n的数相乘的计算量是$O(log_2nlog_2log_2nlog_2log_2log_2n)$
　　定理1.6中的乘法所需的计算量被认为是作乘法运算的最优计算量，即不存在有更少计算量的乘法算法．[2]
　　下面的定理表明，除法所需的计算量与乘法所需的计算量相当，它的证明也不在本书范围内，读者可参见[2].
　　定理1.7 存在除法算法，它求一个2n位数除以一个n位数得的商和余数所需的计算量是O[M(n)]，其中M(n)是做两个n位数乘法所需的计算量．
　　尽管定理1.5和定理1.6说明了有比竖式算法快得多的乘法算法，但为方便起见，我们以后还是使用竖式算法的计算量来代表两个数相乘的计算量．
　　(2)幂运算
　　给定一个整数a，由$a^k=a*a^{k-1},a1=a$，归纳地定义了a的任意次幂．在素数判别和大数分解的讨论中，我们常常遇到要计算$a^n mod m$．如果根据定义，先计算$a mod m$，再依次计算$a^k mod m=(a mod m)(a^{k-1} mod m) mod m$，则至少需要n次乘法才能得到$a^n mod m$，而n经常是很大很大，这时计算量也就很大，于是需要有更好的计算$a^n mod m$的方法．我们确实有更好的方法．
    定理1.8 给定a，存在求幂取模的算法，使得其计算$a^n mod m$的计算量为$O(log_2nlog_2 2m)$．
　　
　　(3)卢卡斯序列的项的计算．
　　所谓卢卡斯序列是指

　　
　　其中α和β是以下整系数二次方程的根：$x^2-Px+Q=0,(P,Q)=1$
　　在以后讨论素数判别时，我们需要计算努卡斯序列的第n项取模m：Un mod m和Vn mod m．它们的计算可利用努卡斯序列的性质，象讨论$a^n mod m$的计算一样，得到比较好的算法，因为讨论它的基本思路与上一段一样，且要用到努卡斯序列的一些较繁杂的性质．这里，我们只叙述一个结果，读者有兴趣可自己证明这个结果。
　　定理1.9 给定P、Q，(P，Q)=1，存在算法使其计算Un mod m和Vn mod m的计算量是$O(log_2nlog_2 2m)$．

　　(4)进位制表示的互化
　　我们常常需要将一个自然数的一种进位制表示化为另一种进位制表示．譬如，日常给出的自然数是十进位数，要将它输到计算机中就必须将它化成二进位数，反过来，从计算机输出的结果又要从二进位数化为十进位数，才能使常人看懂结果．
　　设自然数n，由r1进位制给出，要将它化为r2进位制，我们可以如下完成：在r1进位制体系中进行四则运算，特别是带余除法运算，有

　　

　　则$(q_{k-1}q_{k-2}...q_1q_0)_{r2}$便是n在r2进位制中的表达式．由带余除法的计算量(见定理1.4)知，完成(2)的计算量是$O(log_2 3n)$．
　　

无心人

(5)最大公因数的算法
　　求最大公因数的最普遍的算法是欧几里得算法，它最初是公元前由欧几里得提出来的，有时也称它为辗转相除法．表述如下：
　　设给定m，n(m＞n)，令$r_0=m$，$r_1=n$，有

　　

　　则得$r_k=gcd(r_{k-1}, r_k)=gcd(r_{k-2}, r_{k-1})=...=gcd(r_2, r_3)=gcd(r_1, r_2)=gcd(r_0, r_1)=gcd(m, n)$．

　　欧几里得算法(3)中作带余除法的次数k可由m和n确定出来．我们介绍下面的定理．
　　定理1.10 (3)式中的$k<5log_2 n+1$，即得辗转相除的次数不大于n的十进位表示的位数的5倍．
　　推论 用欧几里得算法求m，n(m≥n)的最大公因数的计算量是$O(log_2 3m)$．
　　熟知，由(3)式的最后一个等式往回推演，可以得到u和v使gcd(m，n)=um ＋vn，而且计算出u，v的计算量也可以证明是O(log23m)，故对一次不定方程ax ＋by=c(其中gcd(a，b)|c)和一次同余式ax≡c(modb)(gcd(a，b)| c)求解的计算量是$O(log_2 3m)$，这里m=max(a，b，c)．
　　另外，为了以后的需要及其本身的重要性，我们要讨论雅可比符
是可以显然地得出的，故仍需要一个算法．我们可以利用雅可比符号的两点性质：

　　

　　写出一个类似于欧几里得算法的算法如下．
　　以下用e(x)表示自然数x的最高2因子的幂次，即2e(x)，2e(x)+1,用x＇表示x的最大奇因子，显然有x=2e(x)．x＇．现在，给定两个数m，n，这里m为奇数且设m＞n．令r0=m，r1=n，
　　则有

　　　　　　(4)

　　其中r2=r0 mod r＇1，即r0除r′1得的余数．再将r2代换r1，

r＇1代换r0重复(4)的手续，不断地重复(4)的演算，最后得到r2=1
　　(m＞n)的计算量是$O(log_2 3m)$．
　　(6)中国剩余定理
　　定理 1.11 设$m, ... m_r(m_i>1)$是两两互素的自然数，$a_1,...,a_r$是r个整数，$M=m_1...m_r$，则存在唯一的0≤a<M使得$a-=a_i(mod m_i) i=1,...,r$．且有算法使得其计算a的计算量是$O(rlog_2 3M)$．

　　　
i=1，…，r；设a，b都满足$0<=a<M, 0<=b<M, a-=a_i(mod m_i), b-=a_i(mod m_i)(i=1,...,r)$，即$a-b-=0(mod mi)$, i=1, …，r，而$m_1,...,m_r$两两互素，因而$a-b-=0(mod M)$，再由0≤a＜M，0≤b<M即得a=b．于是唯一性证得．

　　关于数论中的基本算法的研究，是计算数论的最基本的研究，不仅是它本身很重要，它在很多其它分支如计算机科学、代数学等中有很大的用处．然而到目前为止，除了有些文章散见于某些杂志和书籍中，还没有较完全的书来专门讨论这些问题．在这一方面，最好的文章是勒默的“计算机技巧应用于数论”.
二 素性判别
　　素数这个概念，早在公元前很多世纪就为人们所熟知．后来人们发现所有自然数都是由素数乘起来得到的．欧几里得证明了素数有无限多个，因此，任意大的素数都存在．可是，在自然数的序列1，2，3，……中，素数和合数混杂在一起，对前数千个素数的分布之考察发现素数的分布没有规则，因此，鉴别一个自然数是素数还是合数就成为问题．这个问题在中世纪就引起人们的注意．当时人们试图寻找素数公式．到高斯时代，基本上确认了简单的素数公式是不存在的．在那时，即使对一个十位数的整数来作素性判别都是相当困难的，因此，高斯认定素性判别是数论中最困难的问题之一．从此后，这个问题吸引了大批数学家，但当时的人们没有计算机这个有力的工具，对一般十位以上的数都束手无策．因此，他们或者只对很特殊的数作了些研究，或者，对素性判别作了一般性讨论．而真正用得出的结论去判别一个大数是否素数时，常常因为计算量太大而归于失败．到本世纪初，手摇计算机的产生帮助了象勒默等人发展素性判别．而在1950年之后，由于电子计算机的诞生，数学家们又将注意力转到素性判别的问题上来了．目前，这个分支已经产生了很多好结果．我们将在此作介绍．因为素性判别的理论真正得到发展是近几十年的事，因此，我们主要是介绍近几十年的工作．在本书中，素性判别和素数判别指的是同一件事．
1．素性判别的一般理论
　　素性判别的算法是指一个算法，用它可以判别任意一个自然数是否素数．迄今为止，素性判别的方法有很多种，但它们有共同的形式，我们试将它们从总体上来讨论．
　　欲要寻求一个素性判别的算法，应先注意到素数所应该满足的一些性质，即一些必要条件．根据这些性质设计出一个条件组(也称试验组)．这个条件组有两个特点：凡是素数就满足条件组中的每个条件(也称为通过条件组)，凡通过这组试验组数，若不是素数，则它必有一个真因子落在某个特定的集合中．现对任给的数n，先看n 是否通过试验组，如果不通过，则n是合数；如果通过，则其可能的真因子有一个落在特定的集合中．然后，用这个特定的集合的每个元素去试除n，若有某个元素不等于1和n且整除n，则n是合数，否则，n是素数．这样的素性判别算法的计算量由两部分构成：对n逐个检验它是否满足条件组中的条件的计算量和对特定的集合中的元素逐个试除n．设第一部分的计算量是O(f(n))，特定集合的元素个数是g(n)，(一般这g(n)个元素是1到n之间的数)则这个算法的计算量是$O(f(n)+g(n)log_2 2n)$．
　　到目前为止，仍然没有一个素性判别的多项式算法，换言之，没有一个素性判别的算法，它对n执行时的计算量是$O(P(log_2n))$，其中P(x)是多项式函数．“是否存在素性判别的多项式算法？”是一个没有解决的公开问题．人们偏向于说存在素性判别的多项式算法，但至今没有找到．在已有的判别算法中，或者f(n)不是$log_2n$的多项式，或者g(n)不是$log_2n$的多项式．因而要得到一个素性判别的多项式算法，就需要设法使上述的f(n)和g(n)都是$log_2n$的多项式
2．费马小定理和卡米歇尔数
　　试除法出现之后，一直到16世纪，其间除了一些很特殊的、很局限的素性判别法外，没有什么重要的结果．但到1640年，法国数学家费马首先注意到素数的一个性质，那就是下面讲叙的费马小定理．这个性质是以后的所有素性判别法产生的根源．
定理2．2 (费马小定理) 若n是素数，则对所有不被n整除的a，有$a^{n-1}-=1(mod n)$．
　　我们将费马小定理的另一个形式写成下面的推论．
　　推论 若n是素数，则对任意的整数有$a^n-=a(mod n)$．
　　由第一章第二节的讨论，我们知道，对某个自然数a，1≤a＜n，要验证(a，n)=1和$a^{n-1}-=1(mod n)$是否成立，需要计算量为$O(log_2 3n)$．因此，以对某些a，1≤a＜n，(a，n)=1验证$a^{n-1}-=1(mod n)$作为试验组，将可能产生较好的素数判别法．为此，我们要来看n通过试验组的话，n具备什么性质．这就要考察一下费马小定理的逆命题．
　　大约2500年前，中国古代数学家就发现2^2－2是2的倍数，2^3－2是3的倍数，2^5－2是5的倍数，2^7－2是7的倍数，2^11－2是11的倍数，而2，3，5，7，11都是素数．故他们由此肯定：“若
　　$2^n-2$是$n$的倍数(即$2^n-=2(modn))$，则n是素数”．莱布尼兹研究了《易经》中的这一记载之后，也相信了这个结果．假如这个结果是正确的，则对任给的自然数n＞1，只要验证$2^n-=2(mod n)$是否成立，即可判定n是否素数，其计算量是$O(log_2 3n)$．这就有了素性判别的多项式算法．然而，很不幸运，这个结果不是正确的．1819年，法国数学家赛路斯指出，2^341≡2(mod 341)，但是341= 11×31是个合数．自此以后，人们发现了许多具有不同底值a的反例，如3^91≡3(mod 91)但91=7×13，4^15≡4(mod 15)但15=3×5等等．事实上，对于任意的a，都有这样的反例，而且有无限多个．我们将证明这一点，在此之前，先给出一个定义．
　　定义 对整数a>1，满足$a^n-=a(mod n)$的合数n称为底为a的伪素数．
　　定理2．3 对每一个整数a＞1，有无限多个底为a的伪素数．　　　
　　虽然底为2的伪素数有无限多个，但是，它们相对于素数而言是相当少的，隆德大学的波赫曼证明了小于10^10 X 2的素数有882206716个，而塞尔弗来季和瓦格斯塔夫计算出底为2的伪素数在1到2×10^10之间只有19865个．因此，在大多数情况下，我们的断言“如果$2^n-=2(mod n)$，则n是素数．”是正确的，用这个断言作素性判别，出错的概率很小，例如在n＜2×1010的范围内，出错的概率小于19865／(882206716 ＋19865)≈0.0000025．不过，这样的结果，在实际用来作素性判别时，用处不大，尽管它出错的概率很小，但它毕竟是会出错的．而且，对于特定的一个n，用上面的断言去判别它的素性，就不能排除错误就在此出现．(对于其它底a，可以作同样讨论．)
　　令人惊奇的是，存在这样的合数n，对任意的满足(a，n)=1的a＞1，n都是底为a的伪素数．这样的合数的存在是费马小定理的逆命题不成立的最合适的例证．因为它说明，即使对所有满足(a，n)=1的a有$a^{n-1}-=1(mod n)$，仍不能断定n是素数．这样的合数是由卡米歇尔首先发现的，故叫卡米歇尔数．
　　例 561是卡米歇尔数．这是卡米歇尔发现的第一个卡米歇尔数，也是最小的卡米歇尔数．
      
　　一般地，我们有下面的定理．

　　定理2．4 (卡米歇尔)n是卡米歇尔数的充分必要条件是：i)n无平方因子；ii)n的每一个素因子p有p－1|n－1；iii)n是奇数且至少有三个不同的素因子．
　　　　例 由定理2.4可得2821=7·13·31，10585=5·29·73，27845=5·17·29·23，172081=7·13·31·61都是卡米歇尔数．
　　由于发现了卡米歇尔数，人们认识到利用费马小定理来作素性判别，不是件简单的事情．假如卡米歇尔数只有有限个，则可以给出一个上界M，这样，在n＞M的范围内对n作素性判别就变得容易起来．然而，卡米歇尔数可能有无限多个，这只是一个猜想，至今无人给出证明，但人们大都认为这个结果是正确的．
3．素性判别与广义黎曼猜想
　　1976年，缪内发现了素性判别与广义黎曼猜想(见附录)的一个深刻的关系．他得到的结果是：如果广义黎曼猜想(REH)成立，则有一个算法存在，它对每个n，可在$log_2n$的多项式时间内判明n是否素数．即存在素性判别的多项式算法，而且可设计出这个算法．
　　这个关系的发现，也是以研究费马小定理为出发点的．
　　1976年初，勒默发表了一篇短小精悍的文章，证明了定理1的逆定理也成立．
　　定理2.12 (勒默) 若n是奇合数，则存在自然数a，满足(a，
　　证明 若n含有因子pα，p是奇素数，α＞1．取a为pα的原根，　 　
　　若n=p1p2…Pt，t≥2，P1，P2，…，Pt为互不相同的奇素数．由　 　 　
即2≡0(mod p2)，但p2是奇素数．这是不可能的．故必有a使(a，

　　尽管勒默的这个结果说明了，若n是合数，则在1到n之间到少存
也没有指明a在何处．对某个数n，当然，我们可以对1到n之间的每　
　　这个计算量太大了．因此，我们希望能够改进勒默的这个结果．如果对　
    时只要对较少的a检验．这样就可望得出较有效的素性判别法．
　　缪内注意到，给定一个数n，在n的缩系组成的群Un={a(modn)
    全体构成一个子群，设其为Mn．于是就可以利用下面的安克尼和蒙特哥梅利的结果．
　　定理2.13 (安—蒙)在广义黎曼猜想(REH)成立的条件下．存在一个常数C，对任何自然数n及Un到任何一个群G的非单位同态ψ，都存在q使$1<q<=C(log_2n)2$且$psi(q mod n)<>1$(其中1是G的单位元)．
　　由此，缪内得到了下面的结果：
　　定理2.14 (缪内)在广义黎曼猜想的成立之前提下，存在一个常数C，对任何的自然数n，若n是合数，则存在$1<=a<=C(logn)^2$

　　
Un到Un的同态映射．因为n是合数，由定理2.12知，ψ不是单位同态映射．因此，由定理2.13，存在a使$1<a<=C(log2n)^2$使ψ(a mod n)

　　
　　注 定理2.14中的常数C可取作与定理2.13中的C相同．

　　维路于1978年指出，定理2.14中的常数C可以定为70．
　　由定理2.14，我们说，在广义黎曼猜想成立的前提下，素数判别的多项式算法是存在的．我们可以如下设计出这样一个算法：　　

(mod n)是否成立．若对其中的一个a成立，则停止检验，这时n是合数(由定理2.11)，若对每一个a都不成立，也就是说，对a=1，2，…，
　　上述算法可以完全确定地判别n是否素数， 其计算量就是作70


即工作量是O(log25)，因而这是一个多项式算法．
　　由此可见，只要广义黎曼猜想成立，则素性判别的多项式算法是找到了的．但证明广义黎曼猜想是相当困难的，这是数学家们一直关注的问题．这里的讨论也表明，素性判别是需要用较高深的方法来研究．

无心人

http://hi.baidu.com/caronation/blog/item/b9397682159f5fa60cf4d25e.html

【世界数学难题】素数判定与大数因子分解问题（下）

6．一种概率算法

　　缪内的结果虽然很好，但它毕竟是依赖于一个悬而未决的假设．因而在实用中，它是不能被采用的．故我们回到勒默的结果，看看从这个结果还能引伸出什么方法来．
　　勒默的结果说，若n是合数，则存在a，满足(a，n)=1使样的a至少有多少．
　　
　n是合数时，由勒默的结果定理2.12，Mn是Un的真子群，即Mn≠Un，因而Mn在Un中的指标至少是2，即(Un∶Mn)≥2．故Mn中的元素个数至多是Un中元素个数的一半，即Un中不在Mn中的元素个数至少   
　　　

(modn)．
　　证明 对1到n之间的数a，若(a，n)≠1，则显然a不满足　 　
　　这个推论可以产生一种作“素性判别”的概率算法：
　　对任何输入n，从1到n之间随机地抽取k个数a1，a2，…，ak

是否成立，若有某个ai使此同余式不成立，则断言n是合数；若对a1，…，ak，同余式都成立，则断言n是素数．
　　在这个算法中，ai的选取是随机的，而且结论(断言)正确性不是完全确定的，故此算法叫概率算法．在这个概率算法中，当得到断言说输入n是合数时，由定理2.11，结论是正确的；当得到断言说输入是素数时，没有什么定理可以确保结论是正确的．也就是说，此算法在执行完毕后，可能将一个事实上是合数的输入断言为是素数了．但是，由以上定理2.15的推论，这种出错的概率是很小的．因为，若n事实上是合 　 　
乎为零(但不是零！)，因此用此算法作素数判别21000次，仅可能出现一次错误(从统计的角度来说)．然而，对某个特定的n，通过算法后被断言为素数，我们并不能确定这个断言一定不是错误的．因为以上的原因，这个算法常被称为“合数判别”算法而不称为素数判别算法．但是，因为这个算法的计算量很小，只有$O(klog_2 3n)$，故它确实常被采用．例如用它来寻找一组数，使其中绝大多数是素数．最近，还有人(如赖宾)用它来支持一些孪生素数和素数分布的猜想．
7．目前最有效的艾德利曼经—鲁梅利算法　　1983年，素数判别的研究里，出现了突破性的进展，那就是艾德利曼和鲁梅尼提出来了一个方法．这个方法是一个近似多项式算法，它在实际应用中，对一千位以下的数而言，与多项式算法一样有效．
　　要系统地讲述这个算法，需要涉及到代数数论、乘法数论及多项式理论等多方面的专门知识．因而，我们这里只是概要地介绍这个算法，很多证明就略去了．但我们尽量保证读者能从介绍中对算法的基本思想、方法和技巧有个大概了解．我们将介绍的不是艾德利曼—鲁梅利原来的形式，而是由勒恩斯爵简化了的形式．
　　设$p, q$是两个素数，$p|q-1$，记$zeta p$和$zeta q$分别为p次和q次本原单位根．设$g_q$是$q$的原根，即$g$是群$U_g$的生成元．定义映射$Xpq:U_q-><zeta p>$(其中$<zeta p>$为由$zeta p$生成的循环群)为$Xpq(g^q^j)={zeta_p}^j$．因为$p|q-1$且$U_q$是$q-1$元循环群．则$Xpq$是同态映射．对于任给的整　
${ zeta p_i zeta q_i | a_{ij} in Z}$是一个环)
　　由高斯和的性质，有：若n是素数，则$tau(Xpq)^{n^(p-1)-1}-=Xpq(n)(mod n)$(注意：因为$tau(Xpq)$是$Rpq$中的元素，因而，我们是在环$Rpq$中讨论同余式的)．易知，$p=2$时，这就是费马小定理，因此，上述的素数的这个性质，事实上就是费马小定理在环$Rpq$中的推广．我们来看看，当一个数$n$，对一些$p, q, p | q-1$满足$tau(Xpq)^{n^(p-1)-1}-=Xpq(n)(mod n)$时，能对$n$作出什么结论．勒恩斯爵对此给予了一个回答，他证明了下面的定理．
　　
一个集合满足，对任意的一个素数$q in Q$有 $q-1 | Z$．若奇数$n$满足下列条件：
　　(i)对每个$p in P, q in Q$，若$p|q-1$，则$tau(Xpq)^{n^(p-1)-1}-=X_pq(n)(mod n)$
　　(ii)对每个$p in P$和$n$的素因子$r$有$p^ep|r^{p-1}-1$，其中$p^ep || n^{p-1}-1$．
则每个$n$的素因子$r$，有$r-=n_i(mod w)$，其中$i$有$0<=i<Z$．$w=prod_{q in Q} q, z = prod_{p in P} p)$
　　注 定理2.16中的条件(ii)看起来似乎难以验证，而事实下，可以证明，若对某个$p$，存在$q$($q$不必在$Q$中)使$p|q-1$且$Xpq(n)<>1, tau(Xpq)^{n^(p-1)-1}-=Xpq(n)(mod n)$则条件(ii)就对$p$及任何$n$的素因子$r$成立．在实际应用时，对某个$p$要使$Xpq(n)<>1$对某个素数$q(p|q-1)$成立是很容易做得到的．
　　由勒恩斯爵的结果，我们可以如下编出一个算法，这个算法是基于艾德利曼—鲁梅利的思想，采用了勒恩斯爵的表述．
　　对任何输入$n$，$n$是奇数．第一步，寻找素数集合$P$，使得由其产

　　(Ⅰ)对每个$p in P$，$q in Q$使$p|q-1$，验证(即定理2.16中的条件(i)
　　(Ⅱ)对每个$p in P$，寻找一个$q$(不必属于$Q$)使$p|q-1$且$Xpq(n)<>1$．(这是为了让定理2.16中的条件(ii )成立．)
　　如果(Ⅰ)对某对 $p in P$，$q in Q(p|q-1)$不成立或(Ⅱ)对某个$p in P$不存在$q$使$p|q-1, Xpq(n)<>1$，，则$n$是合数．否则，即(Ⅰ)，(Ⅱ)都通过了，由定理2.16知，n的任何一个素因子$r$满足$r-=n_i(mod w)$，其中
　　对$r=n_i mod w, i=1, 2,...,Z-1$，逐个检验$r$是否整除$n$．若
　　在上述算法中，第二步的计算量，可用高斯和的性质(它所满足的最小多项式)估计出来，它是logn的多项式．第一步和第三步可以在O〔(logn)C·logloglogn〕的计算量内完成，这个由下面的波门伦斯的结果得出．
　　

满足．　　(logn)C1logloglogn＜Z＜(logn)C2·logloglogn
在第三步中，至多要验证Z个整除式，每个整除式的计算量是O(log3n)，因而，完成第三步至多需要O〔(logn)Clogloglogn〕的计算量．
　　总之，用上述算法验证一个数n是否素数，几乎只需要多项式时间．因为当n的位数不太大时(例如少于1000位)，C(logloglogn)是很小的，故其计算量还不及一个多项式算法多．
8．一些特殊的素数及其判别
　　麦森勒素数
　　所谓麦森勒数是指形如$2^p-1$(p是素数)的数，记为Mp，M2=3，M3=7，M5=31，M7=127等，麦森勒素数即是麦森勒数又是素数者．
　　早在1644年，麦森勒就对p=2，3，5，7，11，13，17，19计算了Mp，他证明了除p=11外，其它的Mp是素数，他由此断言，不大于257的各素数，只有p=2，3，5，7，13，17，19，31，67，127，257使Mp是素数．当时没有谁(包括他本人)证明了这个断言．直到1772年，欧拉经过多年探索，证明了是$2^31-1=M_{31}$是素数，大约在1875年，努卡斯证明了$2^127-1$是素数，但是证明了M67不是素数．因此，麦森勒的断言就不全对了．1886年，有人证明了$2^61-1$是素数，因而，人们怀疑麦森勒在抄写时，将61误抄成了67．然而，1911年，泡尔斯证明了$2^89-1$也是素数，三年后，又证明了$2^107-1$也是素数．最后，1922年，葛莱启克证明了$2^257-1$不是素数．这样就彻底说明了麦森勒的断言是不对的．但麦森勒的断言激发了人们对麦森勒素数的研究．到目前为止，已经得到的前29个麦森勒素数Mp是：p=2，3，5，7，13，17，19，31，61，89，107，127，521，607，1279，2203，2281，3217，4253，4423，9689，9941，11213，19937，21701， 23209，44497，86243， 132049．
　　M132049是一个39751位的素数，是目前已知的最大的素数．要对诸如M132049这么大的数判别其是否素数，肯定要用到数的特殊形式，用特殊的方法(艾德利曼—鲁梅利方法也无济于事了)．另外，从上面看出，那些使Mp为素数的素数p的分布是不规则的．因而有必要对麦森勒数研究其特殊的素性判别方法．有一种目前最有效的、专门用于麦森勒数的素性检验方法是下述的努卡斯—勒默方法．
　　定理2.18 设p是一个奇素数，定义序列${L_n}$如下：
　　$L_0=4, L_{n+1}=(L_n^2-2) mod 2^p-1$则$Mp=2^p-1$是素数的充分必要条件是$L_{p-2}=0$．

　　到目前为止，人们得到的最大的素数M132049就是用这个努卡斯—勒默方法得到的，这是1983年9月由斯诺文斯基在大量计算后得到的．

　　近期，威廉斯对努卡斯—勒默的方法作了推广，他得到一些用于对诸如$10^n+-10^m+1$，${a^n-1}/{a-1}$等形式的数作素性判别的方法．

　　费马素数
形如$2^2^n+1$的数称为费马数，记为Fn，若它又是素数，则称为费马素数．

　　早在17世纪，费马验证了F0=3，F1=5，F2=17，F3=257，F4=65537是素数．据此，他猜测Fn都是素数．但到1732年，欧拉分解了F5：

　　
　　故费马的这个猜测不成立．自此之后，人们对n=6，7，8，9，10，11，12，13，14，15，16，17，18，19，21，23，25，26，27，29，30，32，36，38，39，42，52，55，58，62，63，66，71，73，75，77，81，91，93，99，117，125，144，147，150，201，205，207，215，226，228，250，255，267，268，275，284，287，298，316，329，334，398，416，452，544，556，637，692，744，931，1551，1945，2023，2089，2456，3310，4724，6537，6835，9428，9448，23471证明了Fn是合数．然而，除前5个费马数为素数外， 再也没发现任何费马素数了．因而人们更倾向于认为费马素数只有有限个，但没人对此作出证明．近年来，人们把精力放在分解费马数上，没人研究特殊的判别法来对费马数作素性判别．
　　$k2^m+1$型素数
　　研究$k2^m+1$型素数，对分解费马数有着重要作用．熟知，费马数Fn的每个素因子都具有形状$k2^m+1$，其中m≥n＋2，k是奇数．当已知某些$k2^m+1$是素数时，用它去试除Fn(n≤m－2)，这样就可以找到一些费马数的因子．另外，在验证了某个$k2^m+1$是素数后，再对$k2^m-1$作素性判别，则可能找出一对孪生素数来，在这个方面的研究是从普罗丝开始的，他首先提出了一个判别$k2^m+1 (k<2m)$型数是否素数的方法．
　　定理2．19 给定$N=k2^m+1, k<2m$，先寻找一个出一个合适的D)，则N是素数的充分必要条件是$D^{(N-1)/2}-=-1(mod N)$．
　　用普罗丝的这个结果及一些具体的方法，贝利、鲁宾逊、威廉斯等人对一些奇数k和m决定的数$k2^m+1$作了系统的考察，他们对1≤k≤150，1≤m≤1500，找出了所有$k2^m+1$型的素数．又对3≤k≤29和1500＜m≤4000，列出了所有的$k2^m+1$型的素数，得出了7个新的费马数的因子，而且还得到了一对很大的孪生素数：297．2546＋1和297·2546－1
　　最后，介绍斯塔克的一个结果．若m固定，序列${ak}={k2^m+1}$含有无限多个素数，这是由狄利克雷定理得出的．自然地，人们提出这样一个问题：当k固定时，序列${b_m}={k2^m+1}$是否含有无限多个素数呢？斯塔克对这个问题给了否定的回答，他给了一个k=2935363331541925531，它使序列${k2^m+1=b_m}$中每一项都是合数．
　　由1组成的素数
　　每位数都是1的n位数记为Rn，例如R1=1，R2=11，R7=1111111等等．熟知R2=11是素数．
　　因为当m|n时，Rm|Rn，故Rn是素数的必要条件是n是素数．然而，n是素数时，Rn不一定是素数，例如n=3时，R3=111=3×37不是素数．至今为止，只有得出当n=2，19，23，317，1031时，Rn是素数．其中R19已由前面的“n±1”判别法证明了，R23是1929年被证明为素数的．R317是1979年由威廉斯证明的，R1031是1986年由威廉斯和达内用第四节介绍的方法证明为素数的．这五个素数是Rn系统中的前五个素数，即其它不大于1031的素数n都使Rn为合数．事实上，达内还证明了，第六个R_素数必定大于R10000，也就是说，在1到R10000之间只有以上五个R_素数．

相关资源

9．在计算机上实施素数判别的战略
　　迄今为止，所有得到的素性判别法有简单明了的试除法，有赖宾等人的概率算法，有努卡斯到威廉斯的利用$n+-1$，$n^2+1$，$n^2+-n+1$的因子方法，还有艾德利曼—鲁梅利的最有效的近似多项式方法．这些方法各有利弊，它们各适用于适当的输入．上述第一种算法虽然很耗费
　　接了当，对较小的数n(最大不超过108)合适．第二种算法，用于作素性判别时，它可能出现差错，但出差错的可能性很小，因而可用它来确认哪些数最有可能是素数．努卡斯和威廉斯的$n+-1$，$n^2+1$，$n^2+-n+1$方法，对于20—50位的素数是有效的工具．艾德利曼—鲁梅利的方法是普遍的方法，它不依赖于待判别的数的特殊性，而且计算量是O((logn)Clogloglogn)，故一般利用它来对50位以上的数来作素性判别．
　　另外，对有些特殊的数作素数判别时，用特殊的方法(如对2^P-1，用勒默的方法)就可能很便利，就不必用艾德利曼—鲁梅利的方法．下面，我们指出在计算机上作素性判别的三大步骤．
　对于一个待判定的数n(设n不具有我们了解的特殊形式)，实行下面三步：
(1)先用1到1000之间的素数(它们通常储存在计算机内)去试除．若n恰好有小的素因子，则不是素数，算法可停止；否则，进行下一步。
　　　
出结论说n是素数．下面的步骤就是证明n确为素数．

无心人

(3)若n具有20—50位以下，可使用努卡斯和威廉斯的方法．

　　若n具有30—1000位或以上，即使用艾德利曼和鲁梅利的方法．
　注 对30—50位的数，用努卡斯和威廉斯的方法，还是用艾德利曼—鲁梅利的方法，要视计算机的性能和实际情况而定．
三 大数分解
　　大数分解是与素性判别紧密相关的课题．对于给定的一个自然数，先对它作素性判别．若它是素数则罢，若它是合数，我们还想知道它的因子分解式．历史上及现在都有这样的数，它被判别为合数，但是没有发现它的因子(即没有分解)．例如，F8在1909年就被证明为合数，但直到1975年，才发现它的一个因子．又如，F14早在1963年就被证明为合数，但至今它的因子还不知是什么．因此，我们要系统地研究如何去分解一个已知是合数的数．下面，我们假定下面待分解的数是合数．为了方便起见，还假定，对待分解的数已经用试除法排除了它在1到10000(或105)范围内的因子．(这在计算机上是非常容易实行的事，因为1到105之间的素数和试除法都可以存储在计算机内．)
　　与素性判别法的产生一样，大数分解的方法的产生也是从注意合数的一些性质开始的．因而，我们要对合数的一些性质(特别是结构方面的性质)作考察和研究，由此引伸分解的方法。
1．经典的方法
　　费马方法
　　费马注意到，给定n，若n是两数平方差n=a^-b^2，则n=(a ＋b)(a－b)是n的一个因子分解．于是，我们要设法将n表为两个平方差．用逐个考察方法，从b=1开始，依次考察n＋b^2是否平方数，若恰对某个b，有n＋b^2是平方数，设为a^2，即n＋b^2=a^2，故n=(a＋b)(a－b)．
　　用这个方法，只有当n有两个几乎相等的因子时，才比较快．因为
就很小，即从1开始作逐个试验的次数就少．另外，我们可以不须对所有的b来计算n＋b^2并考察它是否平方数．我们注意到，若n＋b^2是平　
几乎相等(相对于n而言，相差log2n的常数倍数即算作几乎相等)时，用费马方法去分解n是很有效的．
　　例 分解385374826089807．

　　　

7，9，11，17，19，21，23，27，29，31，33，37，41，43，47，49，51，53，57，……，试验n＋b2是否为平方数，结果发现n＋572=196309662，故n=19630909×19631023．
　　一种筛法
　　对于给定的n，若已知n的一些较小的平方剩余，则就可以筛去一些n的不可能的因子，因而缩小了n的可能因子的范围，再进一步对它们进行试除．譬如，若a是n的一个二次剩余，则对每个n的奇素因子P，　

　　
即可．用这个方法，可以得到下面的一个有用的定理(前面第二章第八节中谈费马素数时曾提到这个定理)．
　　定理3．1
2^n+2·k＋1．
　　证明 设p|Fn，则＋1≡0(modp)即≡1(modp)．故2对模p的次数为2n+1，因而，2n+1|P－1．故P=1＋2n+1·k对某个k成立．当n≥2时，P≡1(mod8)，因此2是P的二次剩余，
p=2n+2·k＋1．□
　　当n的较小的二次剩余容易找到时(例如2，3，5等是n的二次剩余时)，可用筛法去分解n，我们举一简单的例子，说明这个方法的用途．
　　例 分解1711．
　　因为162·7－92=1711，372·5－1=4·1711，故7和5都是
因此P≡±1，±9，±25(mod28)，P≡±(mod5)．因为满足这两组同余式的前几个数是1，9，19，29，…，经对它们依次试除1711知29|1711，故1711=29·59．
　　勒让德方法
　　勒让德首先注意到，若一个奇数n是合数且至少有两个不同的素因子，则x2≡a2(modn)至少有四个解．其中x≡±a(modn)是两个解，这两个解称为平凡解，另外的解就称为非平凡解．若对同余式x2≡a2(modn)，能找到一个非平凡解b，则gcd(b＋a，n)或gcd(b－a，n)都是n的真因子．因而，分解n就等价于要寻找形如x2≡a2(modn)的同余式的非平凡解．这便是以下的连分数方法和二次筛法所要解决的问题．
2．蒙特卡罗方法
　　设S是一个有限集，令Map(S)是S到S的映射全体．对于每一个ψ∈MaP(S)和X0∈S，由于S是有限集，则存在1≥1使X0=ψ0(X0)，ψ(x0)，…，ψ1－1(x0)(ψi表示ψ的i次的复合)互不相同．但ψ1(x0)与某个ψe(x0)(0≤1＇≤1－1)相同，这时，称1为X0在ψ下的轨迹长度．当k≥1＇时，序列{ψk(x0)}是一个周期为d=1－1＇的循环序列．
　　 设S有m个元素．x0∈S，则x0在ψ下的轨迹长度至少是1的充分必要条件是x0，ψ(x0)，…，ψ1－1(x0)互不相同．因此，Map

　　在Map(S)中，使得x0在其下的轨迹长至少是(2λm)1/2＋1的映射占的比例小于e－λ．故，只有很少的对(x0，ψ)使得x0在ψ下的轨迹长很大(譬如大于5m1/2的对只占e－12.5≈0.0000034)，我们称使得x0在ψ下的轨迹长很大(譬如大于5m1/2)的对(x0，ψ)叫“例外”．
　　波纳德就是用上述的事实得到他的分解方法的．假定n是合数，设r是n的一个因子，令S=Zr为模r的完全剩余系，设x0是一个整数，ψ是一个整系数多项式，若(x0，ψ)不是个“例外”，则x0在ψ下的轨迹长不大于r1/2的一个较小的倍数(譬如5倍)。不过，我们还不知道r，故不能计算Xk=ψk(x0modr)，但是，我们可以计算序列{yk}：y1=ψ(x0)modn，yk=ψ(yk－1)modn，k≥1．序列{yk}满足yk≡xk(modr)，k=0，1，2，…．
　　

时，{Xk}是一个周期序列，其周期1≤cr1/2(c比较小)，因而，令Gk

|gcd(Gk，n)，即gcd(Gk，n)是一个n的大于1的因子．若幸运的话，gcd(Gk，n)就是n的一个真因子，即n被分解了．若对某个k，gcd(Gk，n)=n，则取另外的k试验；若万一对所有的k都有gcd(Gk，n)=n，则从新开始选择X0，ψ0，重复这样的过程，直到n被分出一个真因子为止．
　　以上，我们只知道有些k＜cr1/2使gcd(Gk，n)可能产生n的真因子，但我们不知道哪些k．不过，我们知道，若Gk≡0(modr)，则Gk+1≡0(modr)，因而，从某个k=k0开始，之后的k都有gcd(Gk，n)＞1，因此在寻找因子时，不必依次对k=1，2，3，…来试验gcd(Gk，n)，而只需要有规则地取一些k，(如取k=1，2，4，8，16，32，64，128，…或k=1，5，20，50，100，200，400，…．)来看gcd(Gk，n)是否产生n的真因子．
　　上面的{Gk}是波纳德原先用来寻找n的因子时作出的序列，后来布勒恩特改进了波纳德原先的积式，他用


　　取代Gk，从而使这种方法的效率提高了25％，即计算时间缩短了25％．
　　虽然上面已经说明，很少有对(x0，ψ)使x0在ψ下的轨迹长很大，但是，对于特定ψ，有可能对几乎所有的x0，都使(x0，ψ)成为“例外”，可以证明，当S=Zr时，ψ为一次线性多项式和ψ(x)=x2－2时，对所有的x0∈Zr都产生很多的“例外”来．另外，一方面，我们不能取ψ为很高次的多项式，否则，计算{yk}时，就要花费很大的计算量．经验表明，我们可以把ψ(x)取成二次多项式x2＋a(其中a≠2，a∈Z)，事实上，在实际中，我们总是用这个多项式．
　　　　

　　波纳德算法的最大成功是分解了78位的第8个费马数F8=228＋1，它在1909年就证明为合数．他得到了下列分解式

　　F8=1238926361552897×9346163971535797776916

　　－3558199606896584051237541638188580280321

　　此外，用波纳德的方法还得到下列数的因子：

　　612053256358933|10103＋1

　　150220315444217|592＋1

　　9906434529663163|771－1

　　441651480271681|10137＋1

　　22086765417396827057|2433－1

　　122551752733003055543|2439－1

　　358228856441770927|2461－1

　　73208283304744901303|2587－1
3．连分数法
　　我们知道，利用勒让德方法的一个大困难就是寻找形如x2≡a2(modn)的同余式的非平凡解．如果我们可以找到一系列二次剩余：a12≡c1(modn)，…，a2k≡ck(modn)，而且恰巧c1…ck是一个完全平方数．设a=a1…ak，b2=c1…ck，则有a2≡b2(modn)，若a±b(modn)，则就找到了同余式x2≡a2(modn)的一个非平凡解．但这里又出现两个困难：其一，怎么产生这么多的二次剩余呢？其二，哪些二次剩余之积恰好是个平方数？
　　到1931年，勒默和泡尔斯首次用连分数解决了这两个困难，但是，因为当时还没有电子计算机，计算速度的缓慢使得这个连分数方法不被人们注意，直到1975年，莫利桑和卜利尔哈特，对勒默的方法作了深入的研究，将其发展成为一个较系统的好算法，并用此方法，在计算机上成功地分解了屡功不克的1=2128＋1，从此以后，连分数法就被人们广泛应用于分解因子．到目前为止，它被认为是最有力的分解工具之一．用它可以方便地在计算机上分解50位左右的数．下面，我们对此方法作一介绍．
　　　
　　　
Qm，其中Qm可由一个可以简单计算的递归关系得出．因为对每个m，　　剩余(modn)，所以，这样就解决了第一个问题．
　　现在来讨论第二个问题的解决方法．从上列模n的二次剩余{(－1)m＋1Qm＋1}中，哪些二次剩余可以选出来成为一个集合使得其元素之积正好是一个完全平方数，从而得到形如x2≡a2(modn)的一个非平凡解．我们先看一个例子．
　　例 分解n=12007001．
　　　

　
　　这时将第0，11，27，33，40个同余式

　


　　另一方面，用连分数的渐进分数的递推公式，可以计算出A0，A11，A27，A33，A40，从而可以算出A0A11A27A33A40≡9815310(modn)，因而，由勒让德的方法可求出n的因子：(9815310－29·31·71·97，12007001)=3001，即3001|12007001。
　　从上例可见，要确定哪些(－1)m+1Qm+1入选，先要将(－1)m+1Qm+1在某个确定的素因子(包括－1)集上分解，再将这些分解了的(－1)m+1Qm+1拼凑。这里，在某个集上分解是指在这个集中的因子全部分解出来。我们称上面那个确定的素因子(包括－1)集为分解基集。因为，若p｜(－1)m+1Qm+1，则Am2-knBm2≡(－1)m+1Qm+1

的分解仍然是件麻烦的事情。因而，分解基集中的素数不宜取得太大太多。通常，按需要，指定一个素数pm，使得分解基集中的素数小于pm。有时，为了加快算法执行的速度或为了更有可能找到合适的一组二次剩　
　　取定一个分解基集，若一个(－1)m+1Qm+1的素因子全在这个分解基集中，则称它在这个分解基集上可完全分解，也称它为(对这个基集的)B_数。设分解基集的元素是p0=－1和一系列素数p1，p2，…，ph，这时，每一个B_数可以表示为一个二元数组(即Z2h+1中的元)。若(－1)m+1Qm+1=p0u0p1u1…phuh，则表(－1)m+1Qm+1为(e(u0)
B_数之积的表示就是两个B_数的表示之和。若干个B_数之积为平方数等价于说它们对应的表示之和为(0，0，…，0)若有g个(在实际应用中，通常取g=h＋2)B_数，设为c1，…cg，则可产生一个二元数组成的矩阵，这个矩阵的第i行为ci的二元数组表示，因而，这个矩阵有g行，h ＋1列。当g＞h＋1时，其行向量(诸ci的表示！)就必然对Z2线性相关。因此，有若干个行使其行向量之和为(0，0，…，0)(注意到Z2中唯一不为零的元只有1)这样一来，这若干个行对应的B_数之积就是一个完全平方数．因而，第二个问题就得以解决了．
　　在连分数算法中，计算量主要是在分解诸(－1)m+1Qm+1上．计算机往往在不太可能在基集上分解的(－1)m+1Qm+1上耗费很多运算．波门伦斯对此问题作了研究后，他找出了一个方法，用此方法可以排除那些不太可能在基集上分解的(－1)m+1Qm+1．他的方法更进一步提高了连分数法的速度．
　　有时，在给定的基集上，很多(－1)m+1Qm+1不太可能被分解以致于能分解的(－1)m+1Qm+1不够用，波门伦斯的方法可以让计算机尽早回头扩充基集．
　　有时会发生这样的情况：尽管我们由一组B_数乘起来得到了一个完全平方数，但它却导出二次同余式的一个平凡解．这时，我们可以找另外一组B_数来试验，若仍然屡次失败，则可以换或扩充分解基集以得到更多的、更合适的B_数，或换另外的k值再重复试验，直至成功。
　　莫利桑用连分数得到的F7分解式是
　　F7=5964958812749721·5704689200685129054721
　　最后提一下，波门伦斯对连分数方法作了一个分析，他证明了，连
较高深的算法分析中得到的，这里不多介绍。
4．二次筛法
　　二次筛法与连分数法是基于同样的想法和思路，只有两个差别，下面对此讲述。
　　首先，二次筛法不是用连分数产生二次剩余。而是直接产生二次剩　　就是一系列模n的二次剩余，并且诸Q(x)modn不太大。
　　第二，给定一个分解基集，如何判别哪些Q(x)可以在这个分解基集上分解？哪些不能？这里的方法也有别于连分数方法。
　　我们注意到，若Q(x)≡0(modpα)，即pα|Q(x)，则Q(x＋kpα)=(x＋kpα＋m)2－n≡Q(x)≡0(modpα)，即pα|Q(x＋kpα)。因此，只要确定一个x使得pα|Q(x)，就可以得到其它的一系列Q(x)使其含有pα的因子。如何确定x使pα|Q(x)，这就是解同余式Q(x)≡0(modpα)，而这个同余的解归结为同余式Q(x)≡0(modp)的解。关于素数模的二次同余式的解这个问题，勒默于1969年发表的一篇文章中仔细讨论过，得到了一个很有效的解法。读者请参看[3]。
　　对于某个分解基集，设它的元素是素数p1，…，ph，我们只要依次解同余式Q(x)≡0(modpiαi)(i=1，…，h)然后，确定出h差序列，这个序列对应的Q(x)就是基本上在分解基集上可以完全分解的了。因而，基本上全是B_数。这里提供了一个找B_数的方法。
　　波门伦斯也对二次筛法作了算法分析，他得到二次筛法的渐近计算 量要小些，但这只是渐近的情况，实际上，这里的O_所示的常数比连分数算法的计算量中所示的常数要大。
　　用连分数方法和用二次筛法，人们都可以分解p≤257的麦森勒数Mp中的合数。见附表。
5．p－1法和p＋1法
　　波纳德首先注意到这样一个性质：若给定n为合数，对于n的任一

理可知的，因而gcd(aQ－1，n)＞1，若gcd(aQ－1，n)≠n，则它就是n的真因子了。因而gcd(aQ－1，n)就极可能产生n的真因子。然而，对待分解的数n，我们不知道n的任何素因子，因而不知道哪个哪些Q合适于使gcd(aQ－1，n)产生真因子。当然，我们可以对Q=1，2，…，φ(n)来试验，但这样要花费的时间就比试除法还多，因而，我们必须确定哪些Q最有可能使gcd(aQ－1，n)产生n的真因子，然后对这些Q进行试验。
　　我们假设，n含有这样一个素因子p，它的p－1是由比较多的小素数相乘而得的数。这时，我们可以取Q如下：给定一个上界B1(B1不必很大)，设βi是使pi(pi表示第i个素数)满足piβi≤B1，piβi＋1＞B1的数，(i=1，2，…)，这时，可设Qk=p1β1…pkβk(其中pk是小于B1的最大素数)。其次，取到Qk之后，依次计算bk+1
　　2，…)，然后有规则地选取k，譬如k－1，2，4，8，16，50，100，150，…)，计算gcd(Gk，n)，直到得出n的真因子为止。
　　通常，若p－1的最大素因子是q(设q是第j个素数，即q=pj)，
小就可以得到很大的因子，见下例．
　　例 分解10^95＋1．
　　取B1=30000或更小些，威廉斯用上述的p－1法得到了10^95＋1的素因子p=121450506296081，其中p－1=24·5·13·192·15773·20509(这里人们可以看出，为什么B1取30000就可以了)．威廉斯是大约计算到Gk，(k≈2050)就由gcd(Gk，n)得到了因子p．
　　另外他还得到了3^136＋1的素因子q=267009－1735108484737，这里q－1=2·32·72·19·172·569·631·23993．
　　威廉斯通过对波纳德的p－1方法作细致研究后，利用努卡斯序列的一些类似于幂运算的性质，得到了一个p ＋1法．它适合于分解这样一些合数，它们含有某些素因子p使得p ＋1是由比较多的小素数相乘而得．由于，p +1方法牵涉到努卡斯序列的繁杂的计算，又因为p +1方法的思想与p－1方法相同，我们这里不作介绍．
　　威廉斯用p±1法，对很多合数作了分解，他认为p±1方法在很多情况下比连分数方法和二次筛法更有效。因为对于合数n而言，它经常含有这样一些素因子p，使得p－1或p +1由较多的小素数相乘而得，所以，p±1方法就合适于它了。

mathe

内容不错，就是有点乱。
不知道有没有原文链接？最好能够有英文对照版的。

无心人

有链接啊
前面就有
是从一Blog摘的
这是中文资料

shshsh_0510

无心人

我手里有个更长的纸版
大概32k本28页
：）
比这个详细了
我怀疑这个是和我的纸版有关联

无心人

发现好多复制后出现的错误
怎么能修改啊？
===================
修改数学文章是一种痛苦

liangbch

好文，顶一个。
收藏之。慢慢看。