- 注册时间
- 2008-2-6
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 51456
- 在线时间
- 小时
|

楼主 |
发表于 2008-4-4 11:04:37
|
显示全部楼层
(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),因而这是一个多项式算法.
由此可见,只要广义黎曼猜想成立,则素性判别的多项式算法是找到了的.但证明广义黎曼猜想是相当困难的,这是数学家们一直关注的问题.这里的讨论也表明,素性判别是需要用较高深的方法来研究. |
|