数论基础及应用.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,数论基础及应用,1,数论,是研究数的性质的学科是一门古老而充满现代魅力的数学学科。数论基本上可分为初等数论、解析数论、代数数论等几个较大的分支。,2,在古代，我国对数论的研究曾有过辉煌的成就,如孙子定理（国外文献一般称为中国剩余定理）、商高定理(勾股数)、圆周率的计算等等。在现代，我国一些著名的数学家，如华罗庚、王元、陈景润、潘承洞、丁夏畦等都在数论领域做出了一些举世公认的重要成果。,3,过去，人们把数论归类为纯粹数学，但现在在许多领域，数论的原理和定理都得到了广泛的应用。例如计算机的计算模型、硬件体系结构和软件的设计与实现、代数编码、计算机通信安全与密码学等方面,都有着数论知识的广泛应用。近年来发展起来的一门新兴学科“算法数论”就是用计算机算法来研究和深化数论的理论。一个高层次的计算机专业人员，应该掌握数论的一些基础知识,。,4,1欧几里德转辗相除法,利用,gcd(a,b)=gcd(b,a mod b),求,a，b,的最大公约数：,Function gcd(a,b:longint):longint;beginif b=0 then gcd:=a,Else gcd:=gcd(b,a mod b);,end;,思考：如何把上述算法写成迭代形式？,5,2,扩展的欧几里德算法,如果,gcd(ab)=d，,一定存在整数,x,和,y,满足,gcd(a,b)=ax+by。,算法的理论根据：,由欧几里德转辗相除法,gcd(a,b)=gcd(b,a mod b),，,设整数,x,、,y,满足,gcd(b,a mod b)=bx+(a mod b)y,则,ax+by=bx+(a mod b)y,=bx+(a-(a div b)*b)y,=ay+b(x-(a div b)y),于是,x=y y=x-(a div b)y,6,求,d,及满足,gcd(a,b)=ax+by,的整数对（,x，y）,的算法,function exgcd(a,b:longint;var,y:longint):longint;vart:longint;beginif b=0 thenbegin exgcd:=a;x:=1;y:=0;end,7,求,d,及满足,gcd(a,b)=ax+by,的整数对（,x，y）,的算法（续）,elsebeginexgcd:=exgcd(b,a mod b,x,y);t:=x;x:=y;y:=t-(a div b)*y;end;,end;,思考：,1）,如何把上述算法写成迭代形式？2）满足,gcd(a,b)=ax+by,的整数对（,x，y）,是否是唯,一的？,8,应用1：求解二元一次不定方程,ax+by=c,整数解,解二元一次不定方程,ax+by=c ,其中,a,b,c,都是整数，所求的解(,x,y),也是整数,9,关于方程的可解性，有下面的两个重要的结论：,（1）设,gcd(a,b),表示整数,a,b,的最大公约数。方程有解的充分必要条件是,gcd(a,b)|c。（,记号“,x|y”,表示,x,能整除,y，,即存在整数,k，,使,y=kx）。,（2）,如果(,x,0,y,0,),是方程的一组解，则对任何整数,t,(x,0,+bt,y,0,-at),也都是方程的解。,下面我们讨论具体求解的方法。,为了避免计算中对负数和,0,的讨论，我们假定,a0,，,b0,，,并且,a=b,。,假定方程有解，即系数满足：,gcd(a,b)|c,，,这时，,c=c/gcd(a,b),一定是个整数。我们先讨论下面的方程：,ax+by=gcd(a,b),根据上述扩展的欧几里德算法，一定存在整数,x,0,和,y,0,满足,ax+by=gcd(a,b),。,显然，如果,(,x,0,y,0,),是方程的一组解，则,(,cx,0,cy,0,),也是方程的一组解，即,a(cx,0,)+b(cy,0,)=(cf)=c,。,10,求二元一次不定方程,ax+by=c,一组整数解（,x,0,y,0,）,的算法,procedure equation(a,b,c:longint;var x0,y0:longint);var d,x,y:longint;begind:=exgcd(a,b,x,y);,参见扩展的欧几里德算法,if c mod d0 thenbegin writeln(no answer);halt;end elsebegin x0:=x*(c div d);y0:=y*(c div d);end;end;,说明：,（1）如果,a,b,中有一个小于0，例如,a1,时。,y0=1，y1=q0；,yi+1=yi*qi+yi-1，,当,i1,时。当,tk0,且,rk=sk%tk=0,时，,k,就是最后一轮计算，这时，,xk=15，yk=22,就是所要的结果，但要加上适当的符号后，才能得到原方程的解(,x,y)：x=(-1),k-1,xk，y=(-1),k,yk。,15,3.计算,a,b,mod c,（1),直接迭代法求,a,b,mod n,根据模算术的基本知识（,a*b）mod c=(a mod c)*b)mod c,得到,a,b,mod n,的迭代式,function f1(a,b,n:longint):longint;,var d,i:longint;,begin,d:=a;,for i:=2 to b do d:=d mod n*a;,d:=d mod n;,f1:=d;,end;,16,（,2,）,加速叠代法求,a,b,mod n,把,b,化为二进制（,b,t,b,t-1.,b,1,b,0,）,这样有：,b=b,t,2,t,+b,t-1,2,t-1,+b,1,2,1,+b,0,2,0,（,其中,b,i,=0,或1）,于是,a,b,mod n=a mod n,算法描述：,function f2(a,b,n:longint):longint;,var d,t:longint;,begin,d:=1;t:=a;,while b0 do,begin,if t=1 then begin,f:=d;exit end;,if b mod 2=1 then d:=d*t mod n;,b:=b div 2;,t:=t*t mod n;,end;,f2:=d,end;,b,t,2,t,+,b,t,-1,2,t-1,+b,1,2,1,+b,0,2,0,17,应用3.素数的快速测试,-,Miller-Rabbin,算法,同余,若,a mod c=b mod c,称,a,和,b,关于模,c,同余，记作,ab(mod c).,伪素数,对正整数,n，,如果,a,n-1,1（mod n）,则称,n,是基于,a,的伪素数。如果一个数是伪素数，它几乎肯定是 素数。另一方面，如果一个数不是伪素数，它一定不是素数。,Miller-Rabbin,算法是基于概率论的素数测试算法，对于,a,n-1,1（mod n），,随机选取,s,个基,a,若,a,n-1,1（mod n）,都成立，则,n,为素数，否则为合数。下面给出的,Miller-Rabbin,算法采用计算,a,n-1,mod n,的函数,f,2,(a,n-1,n),对于,随机选取,s,个基,a,f,2,(a,n-1,n),都等于1，则认为,n,为素数。,18,Miller-Rabbin,算法 描述,Function Miller_Rabbin(n:longint):boolean;,Var I,a:longint;,Bl:Boolean;,function f2(a,b,n:longint):longint;,var d,t:longint;,begin,d:=1;t:=a;,while b0 do,begin,if t=1 then begin f:=d;exit end;,if b mod 2=1 then d:=d*t mod n;,b:=b div 2;,t:=t*t mod n;,end;,f2:=d,end;,begin,i:=0;,bl:=tuue;,while(is)and bl do,begin,int(i);,a:=random(n-2)+2;,if f2(a,n-1,n)1 then bl:=false;,end;,miller_rabbin:=bl,end;,19,