数论中的程序设计new.ppt
《数论中的程序设计new.ppt》由会员分享,可在线阅读,更多相关《数论中的程序设计new.ppt(94页珍藏版)》请在文库网上搜索。
1、第第3次课次课 数论中的程序设计数论中的程序设计沈云付沈云付上海大学计算机工程与科学学院上海大学计算机工程与科学学院 本章主要内容本章主要内容1 1、最大公因数与最小公倍数、最大公因数与最小公倍数2 2、求整系数一次不定方程、求整系数一次不定方程ax+by=cax+by=c的解的解3 3、求解模线性方程、求解模线性方程4 4、求模、求模m m的逆元素算法的逆元素算法5 5、模线性方程组与中国剩余定理、模线性方程组与中国剩余定理6 6、模取幂运算与素数测试、模取幂运算与素数测试7 7、实例研究、实例研究1234567891、最大公因数与最小公倍数、最大公因数与最小公倍数公约数和最大公约数的概念公
2、约数和最大公约数的概念最大公约数的一种求法最大公约数的一种求法分解因子分解因子最大公约数性质与欧几里德转辗相除法最大公约数性质与欧几里德转辗相除法欧几里德转辗相除法欧几里德转辗相除法欧几里德算法实现欧几里德算法实现实例实例 求最大公因数求最大公因数问题描述:问题描述:从输入文件中读取一组数据,求最大公因数。从输入文件中读取一组数据,求最大公因数。输入:输入:输输入入有有若若干干行行。每每一一行行上上有有两两个个整整数数x x,y y,是是一一组组测测试试数数据,他们之间用一个空格隔开。据,他们之间用一个空格隔开。输出:输出:对对每每一一组组测测试试数数据据,每每行行输输出出这这两两个个整整数数
3、的的最最大大公公因因数数。如无最大公因数,则标明如无最大公因数,则标明“no GCDno GCD”。输出样例:输出样例:(6,11)=1(0,0)noGCD(5,0)=5输入样例:61100501)公因数和最大公因数的概念)公因数和最大公因数的概念公公因因数数:如如果果d是是a的的因因数数并并且且也也是是b的的因因数数,则则d是是a与与b的的公因数公因数例:例:30的正因数:的正因数:1,2,3,5,6,10,15、30;24的正因数:的正因数:1,2,3,4,6,12,24;24与与30的正公因数有:的正公因数有:1、2、3、6。1是任意两个整数的公因数;是任意两个整数的公因数;最大公因数:
4、两个不同时为最大公因数:两个不同时为0的整数的整数a与与b的最大公因数是其的最大公因数是其值为最大的公因数,记作值为最大的公因数,记作gcd(a,b)。gcd(24,30)6。最大公约数的一种求法最大公约数的一种求法分解因子分解因子 因因为为gcd(agcd(a,b)b)gcd(|a|gcd(|a|,|b|)|b|),所所以以可可考考虑虑非非负负整整数的情况。数的情况。通过求因数,可求通过求因数,可求a a和和b b的素数因子分解:的素数因子分解:a=a=,b=b=于是整数于是整数a a和和b b的最大公因数为:的最大公因数为:gcd(agcd(a,b)b)注意:求一个数的素因子分解问题是注意
5、:求一个数的素因子分解问题是NP问题。目前问题。目前用穷举方法可求不太大的整数的整数分解,这种方用穷举方法可求不太大的整数的整数分解,这种方法不是有效的。只能用优化方法改善计算效率。法不是有效的。只能用优化方法改善计算效率。最大公因数性质最大公因数性质性质:性质:(1)gcd(a,b)gcd(a,b)(2)gcd(a,b)gcd(a+kb,b),k为任何整数为任何整数(3)gcd(a,b)gcd(b,a mod b)(4)如)如a是非零整数,那么是非零整数,那么gcd(a,0)|a|欧几里德转辗相除法的依据:欧几里德转辗相除法的依据:gcd(agcd(a,b)b)gcd(bgcd(b,a mo
6、d b)a mod b)可可求整数求整数a a和和b b的最大公因数的最大公因数 2)最小公倍数)最小公倍数公倍数:如果公倍数:如果m是是a的倍数并且也是的倍数并且也是b的倍数,那么称的倍数,那么称m是是a与与b的公倍数。的公倍数。最小公倍数:两个非零整数最小公倍数:两个非零整数a与与b的最小公倍数是的最小公倍数是a与与b的公的公倍数中数值最小正的数。倍数中数值最小正的数。记作记作lcm(a,b)(或简写为(或简写为a,b)。)。lcm(a,b)lcm(|a|,|b|)通过通过a和和b的标准分解,可以求出整数的标准分解,可以求出整数a和和b的最小公倍数:的最小公倍数:lcm(a,b)=最小公倍
7、数与最大公因数关系最小公倍数与最大公因数关系 3)欧儿里德算法)欧儿里德算法给定任意两个正整数给定任意两个正整数a a和和b b gcd(gcd(a,b)=)=结论:求最大公因数的递归程序求最大公因数的递归程序用欧几里德转辗相除法构造一个求最大公因数的递归程序。用欧几里德转辗相除法构造一个求最大公因数的递归程序。输入:输入:非负整数非负整数a a、b b返回:返回:a a和和b b的最大公因数的最大公因数long gcd(long a,long b)long gcd(long a,long b)long m;long m;if(b=0)&(a=0)/if(b=0)&(a=0)/表示无最大公因数
8、表示无最大公因数 return-1;return-1;if(b=0)return a;if(b=0)return a;else m=gcd(b,else m=gcd(b,a%ba%b););return m;return m;求最大公因数的无递归程序求最大公因数的无递归程序int gcd(int a,int b)int c;if(a=0)return b;while(b!=0)c=b,b=a%b,a=c;return a;2、利用欧几里德算法求整系数一次、利用欧几里德算法求整系数一次不定方程不定方程ax+by=c的解的解算法思想:算法思想:1.利用求利用求a,b的最大公因数的转辗相除过程,进行
9、多次逆推,的最大公因数的转辗相除过程,进行多次逆推,使最大公因数的表示式最终表示为使最大公因数的表示式最终表示为a与与b的线性组合的线性组合ax+by (x与与y可能为可能为0或负数或负数)。2.此时,此时,dgcd(a,b)3.做法:将欧几里德算法进行推广,使得该算法不仅能得做法:将欧几里德算法进行推广,使得该算法不仅能得出任意两个正整数出任意两个正整数a和和b的最大公因数的最大公因数d,而且还能计算出,而且还能计算出满足下式的整数满足下式的整数x和和y:d=ax+by反向递推反向递推辗转相除过程的逆推辗转相除过程的逆推记记类似地,记类似地,记一般地,一般地,于是有整数于是有整数x x和和y
10、 y满足:满足:d dgcd(agcd(a,b)b)ax+by ax+by 扩展欧几里德算法扩展欧几里德算法-递归实现递归实现输入整数输入整数a、b,返回,返回gcd(a,b)和对应等式和对应等式ax+by=d中的中的x,y。long extend_gcd(long a,long b,long&x,long&y)long t,m;if(b=0)&(a=0)return-1;/表示无最大公因数表示无最大公因数 if(b=0)x=1;y=0;return a;else m=extend_gcd(b,a%b,x,y);t=x;x=y;y=t-(a/b)*y;return m;扩展欧几里德算法扩展欧几
11、里德算法-无递归实现无递归实现int extend_gcd(int a,int b,int*x,int*y)int x0,x1,x2,y0,y1,y2;int r0,r1,r2,q;if(a=0)&(b=0)*x=0;*y=0;return-1;/gcd(a,b)不存在不存在if(a=0)&(b!=0)/a=0时不存在时不存在a的乘法逆元的乘法逆元*x=0;*y=1;return b;if(b=0)&(a!=0)/b=0时不存在时不存在b的乘法逆元的乘法逆元*x=1;*y=0;return a;if(a!=0)&(b!=0)x0=0;x1=1;r0=a;y0=1;r1=b;r2=r0%r1;y
12、1=0-r0/r1;x2=1;y2=y1;扩展欧几里德算法扩展欧几里德算法-无递归实现无递归实现(续续)while(r1%r2)!=0)r0=r1;r1=r2;q=r0/r1;x2=x0-x1*q;y2=y0-y1*q;x0=x1;x1=x2;y0=y1;y1=y2;r2=r0%r1;*x=x2;*y=y2;returnr2;mx+ny=c的整数解算法的整数解算法 设设d=gcd(m,n),记,记m=ad,n=bd1.求特解:求整系数方程求特解:求整系数方程mx+ny=d的一个整数解的一个整数解x0,y0,2.求一般解:求一般解:若若 d不是不是c的因数,则整系数方程的因数,则整系数方程mx+
13、ny=c无无整数解;整数解;若若 d是是c的因数,记的因数,记c=gd,则整系数方程则整系数方程mx+ny=c一般解为一般解为:x=gx0+bt,y=gy0-at,t为任何整数为任何整数举例举例求下列整系数方程的整数解:求下列整系数方程的整数解:答案:略答案:略3、求解模线性方程、求解模线性方程1)模和同余模和同余模和同余:模和同余:设设a a、b b和和m m均为整数,且均为整数,且m0m0。如果。如果a a和和b b被被m m除所得的余数相同,那么称除所得的余数相同,那么称a a和和b b关于关于模模m m是是同余的,记同余的,记作作 几个等价定义:几个等价定义:b-ab-a能被能被m m
14、整除,记整除,记m|a-bm|a-b a a和和b b关于关于模模m m是是同余的同余的2)同余性质)同余性质4、设、设 ,那么那么1、2、3、(1)(2)(3)5、费马小定理:设、费马小定理:设a,p为正整数,且为正整数,且p为素数,为素数,(p,a)=1,那么那么剩余类与简化剩余系剩余类与简化剩余系1.剩余类:对于整数剩余类:对于整数a及模及模m,则集合,则集合A=x|xa(mod m)称为模称为模m关于关于a的一个剩余类。的一个剩余类。2.完全剩余系:完全剩余系:0,1,2,m-1是一个特殊的集合,元是一个特殊的集合,元素个数素个数m,其中任何两个数都不同余,称为完全剩余系。,其中任何两
15、个数都不同余,称为完全剩余系。3.任何任何m个元素的集合个元素的集合X,如果其中任何两个数都不同余,如果其中任何两个数都不同余,那么那么X也是一个完全剩余系。也是一个完全剩余系。4.既约剩余系:设既约剩余系:设m为正整数,在与为正整数,在与m既约的所有剩余类中,既约的所有剩余类中,每一个类中取一个数,构成一个集合每一个类中取一个数,构成一个集合X,则,则X称为模称为模m的的一个简化剩余系。一个简化剩余系。举例举例例例1:若:若p是素数,则是素数,则1,2,3,p-1是模是模p的一个既约剩的一个既约剩余系。余系。例例2:1,5,7,11是模是模12的一个既约剩余系。的一个既约剩余系。问题:与正整
16、数问题:与正整数m既约且小于等于既约且小于等于m的自然数全体之积的自然数全体之积Y被被m除后余数是几?除后余数是几?举例:举例:m=7,Y=1*2*3*4*5*6(mod 7)-1(mod 7),正余数,正余数为6;m=13,Y=1*2*3*4*5*12(mod 13)(-1)(13-1)/2(mod 13),正,正余数余数为1;m=21,Y=1*2*4*5*8*10*11*13*16*17*19*20Y(mod 21)1 (mod 21)2)模线性方程)模线性方程 相当于求相当于求根据前面求根据前面求 的步骤:的步骤:(1 1)求)求 ,使,使否则,否则,有有d d个解个解(4 4)的所有解
17、可写为:的所有解可写为:(3 3)由)由 ,改写得:,改写得:于是于是 的一个解为:的一个解为:(2 2)若)若d bd b,则,则无解;无解;方程与同余式求解举例方程与同余式求解举例(2 2)求)求(3 3)求)求例:(例:(1 1)求)求4、求、求mod m的逆元素算法的逆元素算法对整数对整数a,满足,满足ax 1(mod m)的解的解x称为称为a关于模关于模m的逆的逆元素元素。是前面模线性方程的特例。是前面模线性方程的特例。结论:对整数结论:对整数a,m(m0),ax 1(mod m)有解,当且有解,当且仅当,仅当,gcd(a,m)=1也可用直接用扩展欧几里得算法进行求解。也可用直接用扩
18、展欧几里得算法进行求解。求求 的算法的算法 举例求解:求解:(1 1)(2 2)(3 3)(4 4)求求mod m的逆元素的无递归程序:的逆元素的无递归程序:long mod_reverse(long a,long m)long y=0,x=1,r=a%m,q,t,mm=m;/初始化初始化if(r0)r=r+m;while(m%r)!=0)a=m;m=r;q=a/m;r=a%m;t=x;x=y-x*q;y=t;if(r!=1)return 0;if(x0)x=x+mm;return x;5、模线性方程组与中国剩余定理、模线性方程组与中国剩余定理“韩信点兵韩信点兵”问题问题:有兵一列,三三数之余
19、二,五五数之余三,七七数之有兵一列,三三数之余二,五五数之余三,七七数之余二,问兵几何?余二,问兵几何?可写成数学表示形式,求可写成数学表示形式,求x求解模线性方程组求解模线性方程组 中国剩余定理中国剩余定理求解步骤求解步骤 例:解同余方程组例:解同余方程组 中国剩余定理中国剩余定理程序实现程序实现long ChinaRemainder(int m0,int b)long d,x,y,n,m=1,a=0;int i;for(i=1;i=n;i+)m=m*m0i;for(i=1;i=n;i+)MM=m/m0i;extend_gcd(MM,m0i,&x,&y);/或或x=mod_reverse(M
20、M,m0i);a=(a+MM*x*bi)%m;return a;6、模幂运算与素数测试、模幂运算与素数测试模幂运算就是在一个模下模幂运算就是在一个模下计算一个幂的值,即计算计算一个幂的值,即计算 (a,r和和m是正整数是正整数)素数测试就是指,在尽可能短的时间内,尽可能精确素数测试就是指,在尽可能短的时间内,尽可能精确地判断一个整数是否是素数。通过地判断一个整数是否是素数。通过费马小定理来判定小定理来判定一个一个整数的素性整数的素性,因此求模幂是重要任务。,因此求模幂是重要任务。1)模幂运算)模幂运算(1)模幂运算)模幂运算1累次计算法累次计算法:d d a ar r mod m mod m
21、(a mod m)*a)mod m)*a)mod m(a mod m)*a)mod m)*a)mod m*a)mod m *a)mod m 算法算法long modular_power1(long a,long r,long m)long d=1,k;a=a%m;for(k=0;k0)if(r%2)=1)d=(d*t)%m;r=r/2;t=t*t%m;return d;练习练习计算计算2)素数测试)素数测试费马小定理:设费马小定理:设a,p为正整数,且为正整数,且p为素数,为素数,(p,a)=1,那么那么有例外,如有例外,如2340 1(mod 341),但),但341是合数。是合数。素数测试
22、:设素数测试:设a a、n n为正整数为正整数(1 1)若)若 ,则,则n n一定为合数一定为合数(2 2)若)若 ,则几乎可以肯定地确认,则几乎可以肯定地确认n n为素为素数,因出错概率很小数,因出错概率很小 Miller-Rabin素数测试算法框架素数测试算法框架输入:输入:n与与a(a在在2,n-1这些数中随机取值)这些数中随机取值)输出:出:true或或false S1.设设(bk,bk-1,b1,b0)为为n-1的二进制表示的二进制表示S2.d=1S3.For i=k downto 0 do x=d d=(d*d)mod n if(d=1)and(x 1)and(x n-1)then
23、 return true if(bi=1)then d=(d*a)(mod n)End ForS4.if(d 1)then return true S5.return false 3)欧拉定理)欧拉定理设设a和和m 是整数,(是整数,(m00)。记)。记(m)是是1 1到到m的整数中的整数中与与m m互素的整数的个数,则互素的整数的个数,则a(m)1(mod 1(mod m)。费马小定理是欧拉定理的特例费马小定理是欧拉定理的特例 4)公钥密码与)公钥密码与RSA公开密钥算法是在公开密钥算法是在1976年由美国斯坦福大学的迪菲年由美国斯坦福大学的迪菲(Diffie)和赫尔曼)和赫尔曼(Hellm
24、an)提出提出目前最流行的目前最流行的RSA是是1977年由年由MIT教授教授Rivest,Shamir和和Adleman三人共同开发。三人共同开发。密密钥的的产生生选择两个大素数,选择两个大素数,p 和和q,计算出,计算出n=qp,n称为称为RSA算法算法的模数。的模数。n公开,公开,p、q 必须保密。必须保密。n的长度大于的长度大于1024位位计算计算n的欧拉数的欧拉数 (n)=(p-1)(q-1)。随机选择加密密钥随机选择加密密钥e,从,从0,(n)-1中选择一个与中选择一个与(n)互质互质的数的数e,e公开公开计算解密密钥计算解密密钥d,满足满足de1(mod (n)。其中。其中n和和
25、d也要互质。也要互质。数数e和和n做公钥,做公钥,d做私钥。做私钥。两个素数两个素数p和和q不再需要,应该丢弃,不让任何人知道。不再需要,应该丢弃,不让任何人知道。加密与解密加密与解密1.加密信息 m(二进制表示):首先把m分成等长数据块 m1,m2,.,mi,块长s,其中 2s n;do n/=5;count+=n;while(n);coutcount1,那么不能表示成,那么不能表示成Ax+By 形式的邮资的个形式的邮资的个数有无穷多,如以下数都不是数有无穷多,如以下数都不是Ax+By 形式:形式:1、1+A B、1+2 A B、1+n A B、如如d=gcd(A,B)=1,结果如何?,结果
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数论 中的 程序设计 new