大学课件：数论基础及应用

1数论基础及应用2数论是研究数的性质的学科是一门古老而充满现代魅力的数学学科。数论基本上可分为初等数论、解析数论、代数数论等几个较大的分支。3在古代，我国对数论的研究曾有过辉煌的成就,如孙子定理（国外文献一般称为中国剩余定理）、商高定理(勾股数)、圆周率的计算等等。在现代，我国一些著名的数学家，如华罗庚、王元、陈景润、潘承洞、丁夏畦等都在数论领域做出了一些举世公认的重要成果。4过去，人们把数论归类为纯粹数学，但现在在许多领域，数论的原理和定理都得到了广泛的应用。例如计算机的计算模型、硬件体系结构和软件的设计与实现、代数编码、计算机通信安全与密码学等方面,都有着数论知识的广泛应用。近年来发展起来的一门新兴学科“算法数论”就是用计算机算法来研究和深化数论的理论。一个高层次的计算机专业人员，应该掌握数论的一些基础知识。51．欧几里德转辗相除法利用gcd(a,b)=gcd(b,amodb)求a，b的最大公约数：Functiongcd(a,b:longint):longint;beginifb=0thengcd:=aElsegcd:=gcd(b,amodb);end;思考：如何把上述算法写成迭代形式？62．扩展的欧几里德算法如果gcd(a,b)=d，一定存在整数x和y满足gcd(a,b)=ax+by。算法的理论根据：由欧几里德转辗相除法gcd(a,b)=gcd(b,amodb)，设整数x’、y’满足gcd(b,amodb)=bx’+(amodb)y’则ax+by=bx’+(amodb)y’=bx’+(a-(adivb)*b)y’=ay’+b(x’-(adivb)y’)于是x=y’y=x’-(adivb)y’7求d及满足gcd(a,b)=ax+by的整数对（x，y）的算法functionexgcd(a,b:longint;var,y:longint):longint;vart:longint;beginifb=0thenbeginexgcd:=a;x:=1;y:=0;end8求d及满足gcd(a,b)=ax+by的整数对（x，y）的算法（续）elsebeginexgcd:=exgcd(b,amodb,x,y);t:=x;x:=y;y:=t-(adivb)*y;end;end;思考：1）如何把上述算法写成迭代形式？2）满足gcd(a,b)=ax+by的整数对（x，y）是否是唯一的？9应用1：求解二元一次不定方程ax+by=c整数解解二元一次不定方程ax+by=c①其中a,b,c都是整数，所求的解(x,y)也是整数10关于方程①的可解性，有下面的两个重要的结论：（1）设gcd(a,b)表示整数a,b的最大公约数。方程①有解的充分必要条件是gcd(a,b)|c。（记号“x|y”表示x能整除y，即存在整数k，使y=kx）。（2）如果(x0,y0)是方程①的一组解，则对任何整数t,(x0+bt,y0-at)也都是方程①的解。下面我们讨论具体求解的方法。为了避免计算中对负数和0的讨论，我们假定a0，b0，并且a=b。假定方程①有解，即系数满足：gcd(a,b)|c，这时，c’=c/gcd(a,b)一定是个整数。我们先讨论下面的方程：ax+by=gcd(a,b)②根据上述扩展的欧几里德算法，一定存在整数x0和y0满足ax+by=gcd(a,b)。显然，如果(x0,y0)是方程②的一组解，则(c’x0,c’y0)也是方程①的一组解，即a(c’x0)+b(c’y0)=(c’f)=c。11求二元一次不定方程ax+by=c一组整数解（x0,y0）的算法procedureequation(a,b,c:longint;varx0,y0:longint);vard,x,y:longint;begind:=exgcd(a,b,x,y);{参见扩展的欧几里德算法}ifcmodd0thenbeginwriteln('noanswer');halt;endelsebeginx0:=x*(cdivd);y0:=y*(cdivd);end;end;说明：（1）如果a,b中有一个小于0，例如a0，可以令x’=-x，解方程ax’+by=c。求解后，再令x=-x’就可以了。（2）利用前面讲过的性质：“如果(x0,y0)是方程①的一组解，则对任何整数t,(x0+bt,y0-at)也都是方程①的解”。可以通过任何整数t得到方程①的其余解。12递推法求二元一次不定方程ax+by=c一组整数解（x0,y0）我们先讨论下面的方程：ax+by=f②其中f=gcd(a,b)例如方程107x+73y=1③其中a=107,b=73,f=1我们用类似于求最大公约数的辗转相除的方法求这个解。利用辗转相除，可以得到：107=73*1+34(1)73=34*2+5(2)34=5*6+4(3)5=4*1+1(4)4=1*4(5)13递推法求二元一次不定方程ax+by=c一组整数解（x0,y0）(续）为了消去(3)中的”4”，令(3)*1-(4):34=5*7-1(6)为了消去(2)中的”5”，令(2)*7-(6):73*7=34*15+1(7)为了消去(1)中的”34”，令(1)*15-(7):107*15=73*22-1,即：107*(-15)+73*22=1,于是，③的一组解为（-15，22）。下面归纳一般的算法：将(1)-(5)写成一般的形式：si=ti*qi+ri，qi=si/ti，ri=simodti，si+1=ti，ti+1=riSi的初值为a,ti的初值为b14递推法求二元一次不定方程ax+by=c一组整数解（x0,y0）(续）认真分析上面的规律，可以归纳出具体的求解方法。我们先用下面的表格列出相应的关系：i01234S[i]107733454T[i]7334541Q[i]12614R[i]345410X[i]0121315y[i]113192215递推法求二元一次不定方程ax+by=c一组整数解（x0,y0）(续）关键算法是x[k]，y[k]的递推计算公式：x[0]=0，x[1]=1；x[i+1]=x[i]*q[i]+x[i-1]，当i1时。y[0]=1，y[1]=q[0]；y[i+1]=y[i]*q[i]+y[i-1]，当i1时。当t[k]≠0且r[k]=s[k]%t[k]=0时，k就是最后一轮计算，这时，x[k]=15，y[k]=22就是所要的结果，但要加上适当的符号后，才能得到原方程的解(x,y)：x=(-1)k-1x[k]，y=(-1)ky[k]。163.计算abmodc（1)直接迭代法求abmodn根据模算术的基本知识（a*b）modc=((amodc)*b)modc得到abmodn的迭代式functionf1(a,b,n:longint):longint;vard,i:longint;begind:=a;fori:=2tobdod:=dmodn*a;d:=dmodn;f1:=d;end;17（2）加速叠代法求abmodn把b化为二进制（btbt-1.···b1b0）,这样有：b=bt2t+bt-12t-1+···+b121+b020（其中bi=0或1）于是abmodn=amodn算法描述：functionf2(a,b,n:longint):longint;vard,t:longint;begind:=1;t:=a;whileb0dobeginift=1thenbeginf:=d;exitend;ifbmod2=1thend:=d*tmodn;b:=bdiv2;t:=t*tmodn;end;f2:=dend;bt2t+bt-12t-1+···+b121+b02018应用3.素数的快速测试---Miller-Rabbin算法同余若amodc=bmodc,称a和b关于模c同余，记作a≡b(modc).伪素数对正整数n，如果an-1≡1（modn）,则称n是基于a的伪素数。如果一个数是伪素数，它几乎肯定是素数。另一方面，如果一个数不是伪素数，它一定不是素数。Miller-Rabbin算法是基于概率论的素数测试算法，对于an-1≡1（modn），随机选取s个基a,若an-1≡1（modn）都成立，则n为素数，否则为合数。下面给出的Miller-Rabbin算法采用计算an-1modn的函数f2(a,n-1,n),对于随机选取s个基a,f2(a,n-1,n)都等于1，则认为n为素数。19Miller-Rabbin算法描述FunctionMiller_Rabbin(n:longint):boolean;VarI,a:longint;Bl:Boolean;functionf2(a,b,n:longint):longint;vard,t:longint;begind:=1;t:=a;whileb0dobeginift=1thenbeginf:=d;exitend;ifbmod2=1thend:=d*tmodn;b:=bdiv2;t:=t*tmodn;end;f2:=dend;begini:=0;bl:=tuue;while(is)andbldobeginint(i);a:=random(n-2)+2;iff2(a,n-1,n)1thenbl:=false;end;miller_rabbin:=blend;