《整除信安数学》PPT课件.ppt

《《整除信安数学》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《整除信安数学》PPT课件.ppt（98页珍藏版）》请在三一办公上搜索。

1、巫玲W,第一章 整除 Divisibility of integers,学习目标掌握整除、最大公约数、唯一分解定理、素数掌握欧几里德定理的计算与编程实现能够解数学建模等领域的相关题目课程内容的设置整除、最大公约数、最小公倍数欧几里得算法算术基本定理素数,1.1 整数的基本性质与余数定理,定义1 设 a,b为整数，b0.若有一整数去 使得 a=bq,则称 b整除a或a能被b整除,记为b|a，b叫做a的因数，a叫做b的倍数若b不能整除a，记为b|a.注意与/的区别2|4 4/2=2,1.1 整数的基本性质与余数定理,显然有 对所有a,1|a.对所有a,a|0.对所有 a,a|a.若a|b,则对任意

2、的c,有ac|bc.若ac|bc且c0,则a|b,反之亦然问题：若a|bc,a|b则a|c成立？,1.1 整数的基本性质与余数定理,性质1（1）a|b且b|c=a|c（2）a|b且b|a=a=b（3）a|b且a|c任意t,sZ，a|tb+sc（=）:tb+sc=taq1+saq2（=）:t=1,s=0和t=0,s=1分别有a|b和a|c,1.1 整数的基本性质与余数定理,例1设n为整数，证：若3|n，4|n，则12|n 3|n=n=3m 4|3m,4|4m=4|4m-3m=m=m=4k=n=3m=12k作业(1)：P16 第2、4题,1.1 整数的基本性质与余数定理,证:利用性质（3），m|s

3、a+tb=1=m=1 a|n=ab|nb，同理ab|na n=n(sa+tb)=sk.ba+tq.ba=ab|n,1.1 整数的基本性质与余数定理,例3：m奇，p+q|pm+qm；p-q|pm-qm,归纳法：(1)m=1,p+q|p+q(2)设m=2k-1时，p+q|p2k-1+q2k-1(3)当m=2k+1时，p2k+1+q2k+1=p2(p2k-1+q2k-1)-q2k-1(p2-q2)所以 p+q|p2k+1+q2k+1所以m奇，p+q|pm+qm 进一步：m为偶数时p-q|pm-qm 但一般p+q|pm+qm,思考,11112(n个1)是质数还是合数10012(n个0)呢？,1.1 整

4、数的基本性质与余数定理,定义2 素数一个大于1且只能被1和它本身整除的整数,称为素数;否则,称为合数.整数集合可分三类:素数、合数和0,1,-1.正整数集合可分三类:素数、合数和1.素数常用p或p1,p2,来表示.如没有特别说明都是指正的第4节再讲,1.1 整数的基本性质与余数定理,定义3 设xR，x表示不超过x的最大整数，称作x的整数部分x表示x-x，称作x的小数部分如：3.14=3，3.14=0.14注意：-3.14=-4，3.14=0.86,1.1 整数的基本性质与余数定理,不是任意两个数都有整除关系定理7 带余除法，欧几里德除法若a为是二个整数,b0,则唯一存在二个整数q和r,使得下式

5、成立:a=bq+r,0r|b|.,1.1 整数的基本性质与余数定理,1.1 整数的基本性质与余数定理,显然，若a=bq+r，0r r=0,1.1 整数的基本性质与余数定理,证明：若m为奇数，m=2q+1,m2=4q2+4q+1=4q(q+1)+1，q、q+1必有1个偶，除8余1；若m为偶数，m=2q,m2=4q2q奇，除8余4；q偶，除8余0；m2-n2除8余0、1、3、4、5、7，都不为2用第二章的同余表达更清晰,1.1 整数的基本性质与余数定理,整数的表示不同进制？,1.1 整数的基本性质与余数定理,整数的表示,1.1 整数的基本性质与余数定理,1.1 整数的基本性质与余数定理,1.1 整

6、数的基本性质与余数定理,因此则：但,1.1 整数的基本性质与余数定理,1.1 整数的基本性质与余数定理,1.2 最大公因数和最小公倍数,定义3 最大公因数 gcd(a,b),1.2 最大公因数和最小公倍数,在个数不少于3个的互素正整数中,不一定是每二个正整数都是互素的.例:(6,10,15)=1,但(6,10)=2,(6,15)=3,(10,15)=5.,1.2 最大公因数和最小公倍数,定义4 最小公倍数 lcm(a,b)a,b,1.2 最大公因数和最小公倍数,性质2（补充）（1）若a|b，则（a,b）=|a|,a,b=|b|（补充）对任意整数x，(a,b)=(a,ax+b)若d=(a,b)，

7、D=(a,b+ax)则d|a,d|b,所以d|b+ax，所以dD 同理D|a，D|b+ax，所以D|b+ax-ax=b 所以D d 所以d=D推论：（2）若c=ax+b，则(a,c)=(a,b)因为(a,c)=(a,ax+b)=(a,b),1.2 最大公因数和最小公倍数,性质2（3）(a,b)|ax+by 根据 d|b,d|a，则d|ax+by，关键x,y可以任意整数推论：若存在ax+by=1，则(a,b)=1思考：若(a,b)1，方程ax+by=1有整数解吗?,1.2 最大公因数和最小公倍数,如何计算一条线段上整数点的个数 线段可平移使得两个端点为(0,0),(x,y)（x,y整数），记gc

8、d(x,y)表示最大公约数，则(x/gcd(x,y),y/gcd(x,y)一定在线段上，并且线段上的所有整点都可以表示为k*(x/gcd(x,y),y/gcd(x,y)，其中k=0,1,2,gcd(x,y)，所以包括端点的整点个数为gcd(x,y)+1个,1.2 最大公因数和最小公倍数,性质3（补充）a|c,b|c a,b|c证：:L=a,b，设c=qL+r,0 r d|(a,b)证：:设di为a,b的全体公约数，1in L=d1,d2,dn，所以L|a,L|b而|di|L。所以L=(a,b)，所以若d|a,d|b，则d|L,1.2 最大公因数和最小公倍数,例1-11,例1-11证明:设(a+

9、b,a-b)=d,所以d|(a+b)+(a-b),即d|2a同理d|2b所以d|(2a,2b)=2(a,b)=2所以d=1或2,1.2 最大公因数和最小公倍数,推论(a,b,c)=(a,b),c);a,b,c=a,b,c证明：若d=(a,b,c),D=(a,b),c)d|a,d|b，则d|(a,b)因d|c，则d|(a,b),c)=D D|(a,b)所以D|a,D|b，因D|c，因此D|d 所以d=D,1.2 最大公因数和最小公倍数,性质3（2）证明：(b,c)=(b(a,c),c)=(ba,bc,c)=(ba,(b,1)c)=(ba,c)为什么要b，c不同时为0？若c|ab,则(ab,c)=

10、c,所以(b,c)=c，所以c|b,1.2 最大公因数和最小公倍数,性质3(3-6)作业(2)：P16 第8题,一个有趣的小问题,最短路径问题：左上角的T到右下角的S,走迷宫,Euclid算法,辗转相除法，更相减损数（九章算术）反复用带余除法求公约数,Euclid算法,定理 因为,Euclid算法,Euclid算法,Euclid算法,Euclid算法,解因此,Euclid算法,Euclid 算法 int gcd(int a,int b)int mod;while(mod=a%b)a=b,b=mod;return b;/a%b=a-a/b*b；注意这里面必须a,b都为正数，否则要加其他判断语句,

11、Euclid算法,也可递归int gcd(int a,int b)if(b=0)return a;else return gcd(b,a%b);,Euclid算法,Extended-Euclid 算法:同时求出 v,u 使 gcd(a,b)=u*a+v*b,扩展欧几里得算法,法一：(定理1-8)依次把a,b代入a-bq1=r1 b-r1q2=r2 b-(a-bq1)q2=a(-q2)+b(1+q1 q2)=r2 r1-r2q3=r3(a-bq1)-(a(-q2)+b(1+q1 q2)q3=a(1-(-q2)q3)+b(-q1(1+q1 q2)q3)=r3,1-q1-q2 1-(-q1)*q21

12、-(-q2)q3-q1(1+q1 q2)q3,扩展欧几里得算法,如 a=27 b=11,所以：27*(-2)+11*5=1,27-2*11=5 11-2*5=1 5-1*5=0,扩展欧几里得算法,法二：注意到对于gcd(a0,b0)=d 我们对(a0,b0)用欧几里德辗转相除会最终得到(d,0)此时对于把an=d,bn=0 带入a*x+b*y=d，显然x=1，y可以为任意值这里y可以为任意值就意味着解会有无数个。我们可以用a=d,b=0的情况逆推出来任何gcd(a,b)=d 满足a*x+b*y=d的解。,扩展欧几里得算法,如果x0,y0是b*x+(a%b)*y=d 的解，那么对于a*x+b*y

13、=d的解呢？因为 b*x0+(a-a/b*b)*y 0=a*y 0+b*(x0-a/b*y0)所以a*x+b*y=d的解x1=y0，y1=x0-a/b*y0这样我们可以程序迭代了。,扩展欧几里得算法,如 a=27 b=11,27=11*2+511=5*2+15=1*5+0d=1,1=1*1+01=5*0+1*(1-5/1*0=1)1=11*1+5*(0-11/5*1=-2)1=27*(-2)+11*(1-27/11(-2)=5),x1=y0，y1=x0-a/b*y0,所以：27*(-2)+11*5=1,扩展欧几里得算法,viod Euclid(int a,int b,inty=0；else i

14、nt i,j,d；Euclid(b,a%b,d,i,j)；gcd=d；x=i；y=i-n/m*j；,Euclid算法,有了 GCD,LCM 就好办了LCM(a,b)=a*b/GCD(a,b)实际上最好写成a/GCD(a,b)*b作业(3)p17 第13(1)(2)题，要求写出sa+tb=(a,b)的式子,1.2 最大公因数和最小公倍数,定理 设a,b为不全为零的整数，则(a,b)=mins:s=ax+by,x,yZ,s0证明：关键:最小的s0=ax+by,(a,b)|s0 存在a=q1s0+r1,b=q2s0+r2 0 r1,r2s0,所以r1=a-q1(ax+by)=(1-q1x)a-bq1

15、y 所以r1,r2 S，因为s0最小正整数，矛盾，所以r1,r2=0 所以a=q1s0,b=q2s0所以s0|(a,b),所以s0=(a,b)推论：S由(a,b)的倍数构成,1.2 最大公因数和最小公倍数,定理 设a,b为不全为零的整数，则 方程ax+by=c有整数解 c s:s=ax+by,x,yZ,s0(a,b)|c特别的(a,b)=1 存在整数x和y，使得ax+by=1,1.2 最大公因数和最小公倍数,求方程243x+198y=909的一组整数解 解：先求出线性表达式，则先作系数的辗转相除法 243=198+45 9=(243-198)*9-198*2=243*9-198*11 198=

16、45*4+18 9=45-(198-45*4)*2=45*9-198*2 45=18*2+9 9=45-18*2 18=9*2 反推：因为(243,198)=9|909 因此方程有解因此243*9-198*11=9 因此 243*9*101-198*11*101=101*9因此 x0=101*9=909；y0=-11*101=-1111因此 x=909+22t；y=-1111+27t tZ,1.2 最大公因数和最小公倍数,例：求解12x+6y-5z=13,解：设u=2x+y，则6u-5z=13(6,5)=1|13，所以有解 13=6*3-5*1，所以u=3+5t,z=1+6t 对于2x+y=3

17、，x=1+s y=1-2s 所以 x=1+6t y=1-7t z=1+6t作业(4)：求解312x+753y=345,1.2 最大公因数和最小公倍数,程序实现nx+my=k的求解Void solve_linear(int n,int m,int k)int s,i,j,d;Euclid(m,n,d,i,j);/前面的扩展Euclid算法，也可用书上的实现 if(k%d=0)for(s=0;s=d-1;s+)cout j*k/d+i*n/d;,1.3 算术基本定理,更常称为：整数唯一分解定理整除理论的中心内容,1.3 算术基本定理,预备定理若p为素数,则a不能被p整除当且仅当:(p,a)=1证明

18、 因p为素数,故p只有二个正因数,即1和p.若(p,a)1,则只有(p,a)=p.反之,若(p,1)=1,则p和a是互素的,故p|a.,1.3 算术基本定理,1.3 算术基本定理,定理1-11,1.3 算术基本定理,1.3 算术基本定理,1.3 算术基本定理,1.3 算术基本定理,1.3 算术基本定理,1.3 算术基本定理,1.3 算术基本定理,1.3 算术基本定理,推论,1.3 算术基本定理,例1-13 n|ab,n|cd,n|(ac+bd),证:n|ac,n|bd证:n=piai,n|ab,n|cd,则n2|abcd,从而 pi2ai|abcd 所以任意i，piai|ac或piai|bd，

19、由于n|(ac+bd)所以piai|ac和piai|bd同时成立所以n|ac,n|bd,1.3 算术基本定理,1.3 算术基本定理,1.4 素数,1.4 素数,例：形如4n+1的素数有无穷多个,反证：设mi=4ki+1是形如4n+1的有限i个素数，而p=1+4mi=1+4(4ki+1)=4x+1由于mi|p-1,所以(mi,p)=1，所以p的所有素因子都不在mi中，所以素数不止i个，矛盾,问题：p的素因子，可能不是4n+1型的,原因：4n+1和4n-1都可能是素数,(4n-1)(4m-1)=4x+1,1.4 素数,例：形如4n-1的素数有无穷多个,反证：设mi=4ki-1是形如4n-1的有限i

20、个素数，而 p=4mi 1=4(4ki-1)-1=4x-1 由于mi|p-1,所以(mi,p)=1，所以p的素因子都不是mi的一个再证p素因子中有形如4n-1的。因为素数只能4n1的形式，不可能全为4n+1的，否则p只能是4n+1形式思考：如何证形如4n+1的素数有无穷多呢？提示：构造p时让p只有4n+1形式的素因子一种方法：利用m!偶，(m!)2+1为4n+1形式，引入奇素数p|(m!)2+1时，证明p只能是4n+1的形式，否则p|(m!)p1；而pm，得证需要用到后面的费马定理,1.4 素数,换一种写法,1.4 素数,例：证明191是素数,因为 132=169,142=196所以：若素数p

21、|191，则p13而2，3，5，7，11，13均不整除191所以191是素数,1.4 素数,1）pN存储不大于n的所有的素数，二重循环，用已经求出的不大于平方根的所有素数试除 for(i=2;in;i+)for(j=0;jm,1.4 素数,厄拉托塞师（Eratosthenes）筛法,1.4 素数,1.4 素数,1.4 素数,1.4 素数,1.4 素数,1.4 素数,Eratosthenes的算法,2）增加布尔型数组bN记录是否为素数，初始化所有值=1，从头开始遍历，如果bi=1，则i是素数，将所有的i的倍数j均修改为bj=0 for(i=2;in;+i)如果bi=1则添加到素数列表p，然后利用

22、循环for(j=i;jn;j+=i)bj=0将i的所有倍数删掉思考：试与前面1)比较两种方法效率,1.4 素数构造素数,试想一下：2+n！，3+n！，4+n！，n+n!的连续数列这时，数列中的第一项n！2 则可被2 整除；第二项n！3 可被3 整除；第三项n！+4 可被4 整除；等等。在这个数列中有n-1个数，没有一个是素数。通过任意选择n 的大小，你可以得出你想要的无素数的连续整数数列。,1.4 素数构造素数,梦想发明能够计算出素数的公式欧拉公式：诱人的简单 n2n41生成：41,47,53但可能生成合数，How?后来出现了素性检测，另章介绍,1.4 素数构造素数,思考：n(n+1)+41

23、n=1,n=3,n=40，41|n2n41在1，00O 万以下的所有素数中，该公式可得出占总素数的475。而当n 值较低时，该公式工作得更有成效。当n 值小于2，398时，得素数的机会一半对一半。而当n 值小于100 时，该公式得出86 个素数，合成数只有14 个。,1.4 素数构造素数,类似公式4n2170n1,847 计算出1,000万以下素数的成功率为46.6，并得出760个欧拉公式所不能推出的素数公式4n24n59 成功率为437，同时得出大约1，500 个不能由其他两个公式推出的素数。其他还有x!1等,1.4 素数构造素数,证明若2m+1为素数，则m=2n,设p|m，若m2，p为奇素

24、，则 2m/p+1|2m+1，由于2m/p+13，所以2m+1为合数，矛盾 故p只能为2推论：费马数 如3,5,17,257任意2个费马数互素 提示：F(j)|F(i)-2(jI时),1.4 素数构造素数,了解：欧拉关于 不是质数的证明 a=27,b=5，a-b3=3，1+ab-b4=1+3b=24 所以 232+1=(28)4+1=(2a)4+1=24a4+1=(1+ab-b4)a4+1=(1+ab)a4+(1-a4b4)=(1+ab)a4+(1+ab)(1-ab)(1+a2b2)所以 1+ab|F5,1.4 素数,Mersenne素数：,p素求证：若mn-1为素，则m=2且n为素,因为p-

25、q|pn-qn，所以m-1|mn-1，所以m-1=1 m=2时 若p|n，则 2p-1|2n-1，矛盾，所以n素,1.4 素数,费马、梅森素数的价值:计算方便 除法可以转化为移位加减法 Mp=2p-1 a=Mp*q+r a=2p*a0+a1=(2p-1)*a0+a1+a0 所以 q=a0；r=a1+a0 当然,若r超过p位，则需要r=a1+a0-(2p-1),a0 a1,p位,1.4 素数,例：10100010 00111100 10101011除以217-1所得的余数是多少？解：1010001 0 00111100 10101011 余数=1010001+0 00111100 1010101

26、1=111100 11111100,17位,1 素数 合数:唯一分解，p1,2奇素数,总结,对于一个数：a,总结,对于2个数：a，b r=0 b|a=(a,b)=ba=bq+r a|b,b|a a=b r(0,b)=(a,b)=(b,r)若a是素，则 a|b 或者(a,b)=1(1,a)=1;(a,0)=a;(-a,b)=(a,b)(a,b)|ax+by，存在(a,b)=ax0+by0欧几里得除法,总结,3个数：a,b,ca|b,b|c=a|cc|a,c|b=c|(a,b),c|ax+by(a,b),c)=(a,b,c)=(a,(b,c)c素,c|ab，则c|a或c|b,练习,例:证明(mn-1,m3)=1,证：设（mn-1,m3）=d，d|mn-1,d|m3,所以d|m3n-m2-nm3,所以d|m2,同理d|m,最后d|1，所以d=1,