数论基础及应用.ppt

1、1,数论基础及应用,2,数论是研究数的性质的学科是一门古老而充满现代魅力的数学学科。数论基本上可分为初等数论、解析数论、代数数论等几个较大的分支。,3,在古代，我国对数论的研究曾有过辉煌的成就, 如孙子定理（国外文献一般称为中国剩余定理）、商高定理(勾股数)、圆周率的计算等等。在现代，我国一些著名的数学家，如华罗庚、王元、陈景润、潘承洞、丁夏畦等都在数论领域做出了一些举世公认的重要成果。,4,过去，人们把数论归类为纯粹数学，但现在在许多领域，数论的原理和定理都得到了广泛的应用。例如计算机的计算模型、硬件体系结构和软件的设计与实现、代数编码、计算机通信安全与密码学等方面, 都有着数论知识的广泛应

2、用。近年来发展起来的一门新兴学科“算法数论”就是用计算机算法来研究和深化数论的理论。一个高层次的计算机专业人员，应该掌握数论的一些基础知识。,5,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; 思考：如何把上述算法写成迭代形式？,6,2扩展的欧几里德算法,如果gcd(a,b)=d，一定存在整数x和y满足gcd(a,b)=ax+by。,算法的理论根据： 由欧几里德转辗相除法

3、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,7,求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,8,求d及满足gc

4、d(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）是否是唯一的？,9,应用1：求解二元一次不定方程ax+by=c整数解,解二元一次不定方程 ax+by=c 其中a,b,c都是整数，所求的解(x,y)也是整数,10,关于方程的可解性，有下面的两个重要的结论：,（1）设gcd(a,b)表示整数a,b的最大公约数。方程有解的充分必要条件是gcd(a,b)

5、|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)是方程的一组解，则(cx0,cy0)也是方程的一组解，即 a(cx0)+b(

6、cy0)=(cf)=c。,11,求二元一次不定方程ax+by=c一组整数解（x0,y0）的算法,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，例如a0，可以令x=-x，解方程 ax+by=c。

7、 求解后，再令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)

8、,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=si mod ti， si+1=ti，ti+1=ri Si 的初值为a, ti 的初值为b,

9、14,递推法求二元一次不定方程ax+by=c一组整数解（x0,y0）(续）,认真分析上面的规律，可以归纳出具体的求解方法。我们先用下面的表格列出相应的关系：,15,递推法求二元一次不定方程ax+by=c一组整数解（x0,y0）(续）,关键算法是xk，yk的递推计算公式：x0=0，x1=1； xi+1=xi*qi+xi-1， 当i1时。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-1xk，y=(-1)

10、kyk。,16,3.计算ab mod c,（1) 直接迭代法求ab mod n 根据模算术的基本知识（a*b）mod c=(a mod c)*b) mod c 得到ab 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;,17,（2）加速叠代法求ab mod n,把b化为二进制（btbt-1.b1b0）,这样有： b=bt2t+bt-12t-1+b121+b020 （其中bi=0或1）

11、于是ab 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;,bt2t+bt-12t-1+b121+b020,18,应用3.素数的快速测试-Miller-Rabbin算法,同余 若a mod c=b mod c,称a

12、和b关于模c同余，记作 ab(mod c). 伪素数 对正整数n，如果an-11（mod n） ,则称n是基于a的伪素数。如果一个数是伪素数，它几乎肯定是 素数。另一方面，如果一个数不是伪素数，它一定不是素数。 Miller-Rabbin算法是基于概率论的素数测试算法，对于an-11（mod n），随机选取s个基a,若an-11（mod n）都成立，则n为素数，否则为合数。下面给出的Miller-Rabbin算法采用计算an-1 mod n的函数f2(a,n-1,n),对于随机选取s个基a, f2(a,n-1,n)都等于1，则认为n为素数。,19,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