第二章_同余

巫玲[e-mail]第二章同余modulus学习目标掌握同余、剩余类（系）、欧拉函数、费马定理、孙子定理了解同余理论和孙子定理在计算机和密码学的应用课程内容的设置同余的基本概念、性质和应用剩余类、完全剩余系、简化剩余系及应用欧拉函数、费马定理及应用孙子定理同余式2.0问题的提出50天后星期几？234567天后呢？计算机中的溢出问题循环队列的的实现？数学中的同余整除中：a=qb+r0≤rb：同余就是余相等如：19=12*1+77=12*0+72.0问题的解决——同余理论07012)7-127112)192.1同余的基本概念与性质定义2.1.1,若r1=r2,则称a，b模m同余：也记为：或ZbaZm,,*2211,rmqbrmqa)(modmbabam)(mod0mbabam|kmba)(modmrba2.1同余的基本概念与性质例：27≡?(mod7)253天后星期几？同时：a≡r(mod7)0≤r7a-r是一个满射因此：可以按不同的余数对整数分类，也就是每一类余数相同，也就是同余23=8≡1(mod7)所以253≡23*17+2≡4(mod7)2.1同余的基本概念与性质定理2.1.1同余关系是一种等价关系：自反性：对称性：则传递性：则)(modmaa)(modmba)(modmab)(modmba)(modmcb)(modmca2.1同余的基本概念与性质例:证明(mn-1,m3)=1证：设（mn-1,m3）=d所以mn-1≡0(modp),m3≡0(modp)所以m2≡mn.m2=n.m3≡0(modp),所以m≡mn.m=n.m2≡0(modp),所以1≡mn=m.n≡0(modp),所以p=12.1同余的基本概念与性质性质2.2设（1）特别的：（2）特别的：以及：（6）,且则有ZkmdcmbaNm),(mod),(mod,)(modmdybxcyax)(modmkbka)(modmbdac)(modmbkak)(mod,mbaNnnn011)(axaxaxfnn011)(bxbxbxgnnZbaii,)(mod,1mbaniii)(modmyx))(mod()(mygxf2.1同余的基本概念与性质性质2.2（3）特别的：,若（m,n）=1则扩大：扩大：，d|(a,b,m)则（4）d|m，则特别的：若)(modmbnan)(modmba)),((modnmmba)(modmba)(moddmdbda)(mod)(mod,*mnbnanmbaZn)(moddba)(mod,nbanml有2.1同余的基本概念与性质性质2.2（7）若（8）（补充）若，则(a,m)=(b,m)例作业(1):p57第1题NmniNmi,1,)(modmba]),,(mod[)(mod1nimmbamba)))(modmod).(mod(()(modmmbmamab2.1同余的基本概念与性质作业(2):p57第5题2.1同余的基本概念与性质问题：一个十进制数，什么时候能被3整除结论：当各位和为3的倍数时如：248901why？2.1同余的基本概念与性质关键：10=3×3+1，100=33×3+1，……所以：若n=am10m+am-110m-1+…+a110+a03|n=3|am+am-1+…+a1+a02.1同余的基本概念与性质例：快速判断某个数整除7的余数？10≡3(mod7),100≡30≡2(mod7),1000≡20≡-1(mod7)10002k+1≡-1(mod7),10002k≡1(mod7)若n=am1000m+am-11000m-1+…+a11000+a0对于637592≡692-637=55=6(mod7)2.1同余的基本概念与性质扩展：怎样快速判断一个数可以被19整除？提示：凑成19的倍数2位数字？多于2位时？作业(3)：怎样快速判断一个数可以被31整除？,p57第3题2.1同余的基本概念与性质补充（1）若P,q不同素数，)(modpba)(modqba)(modpqba2.1同余的基本概念与性质例：p,p+10,p+14均是素数？求p因为10=2*5，14=2*7，所以p≠2,5,7对于p=3，若p≡1(mod3)，则p+14≡0(mod3)，排除若p≡2(mod3)，则p+10≡0(mod3)，排除所以p≡0(mod3)因为p素，所以p=32.1同余的基本概念与性质（补充），则存在唯一使因为存在ax+my=1即ax-1=my若存在x1和x2两个逆元，则x1*a*x2≡x1≡x2(modm)如若(a,m)≠1，则a-1不存在1),(,maZa1a)(mod111maaaa2.1同余的基本概念与性质求5模11的逆元11=5*2+15*2≡-1(mod11)5*(-2)≡1(mod11)5模11的逆元为-2（但更常写为9）求233模1211的逆元1211=233*5+46233=46*5+346=3*15+11=46-3*15=46-(233-46*5)*15=46*76-233*15=(1211-233*5)*76-233*15=1211*76-233*395所以–395为所求2.1同余的基本概念与性质求解方程17x≡4(mod19)19=17+217=8*2+1所以17*9-19*8=1所以17*9≡1(mod19)因为(4,9)=1所以17*36≡4(mod19)，所以x≡36≡-2(mod19)作业(4):p59第25题(1)(3)2.2同余的应用主要应用补码、随机数、文件系统、hash、密码、检错码等编程时求余的主要实现modexcel、vb、asp、delphi、vfp等%c、c++、c#、java等2.2同余的应用多维数组补码Two’scomplement为什么会有补码如何计算口诀原理：异或：模2加)20(2)02({][1nnnxxxxx补2.2同余的应用循环队列数组queue[max_size]队首指针front，指向队首元素的前一个位置队尾指针rear，指向队尾元素初始化front=rear=0插入元素rear=(rear+1)%max_size删除元素front=(front+1)%max_size什么时候为空？什么时候为满元素数量最多为max_size-12.2同余的应用随机数（RandomNumber）什么是随机数有什么用：仿真、游戏、协议、密码……srand(seed)intrand(viod)产生方法：利用随机过程事先定制好的随机数表利用数学递推公式模拟伪随机数（Pseudo-RandomNumber)随机数（RandomNumber）伪随机数产生方法迭代取中法：代表性为平方取中乘同余线性乘同余，也叫混合同余改进：2.2同余的应用)10)(mod10/(221ssnnII)(mod1mILInnmcaIInnmod)(13112mod)65539(nnII1961年由IBM提出mIbIaInnnmod)(212.2同余的应用仿射密码AffineCiphery≡ax+b(mod26)尝试解密：casear考虑编程的解法LXWPAJCDUJCRXWBy≡x+3(mod26)凯撒密码CaesarCipher移位密码、加法密码ABCDEFABCDEFXYZWXYZABCZABCDEF2.2同余的应用012345678910111213141504812159132610143711150481259131101426153711循环左移1字节循环左移2字节循环左移3字节2.3剩余类（系）Residue同余是一种等价关系=〉可以借助同余实现划分，令Ca={c|}定理2-1(1)任意整数都包含于一个Cr中，0≤r≤m-1(2)Ca=Cb=(3)要么Ca=Cb，要么Ca∩Cb=Ø(4)两两不同的Cr最多m个ZaNm,)(mod,mcaZc)(modmba04812159132610143711152.3剩余类（系）Residue定义2.2.1Ca叫模m的一个剩余类，Ca中的任一数叫该类的代表元（），若为m个整数，并且其中任两个数都不在同一个剩余类中，叫模m的一个完全剩余系，若（r,m）=1,则这样的剩余类叫做模m的简化（紧缩/既约）剩余系,缩系元素的个数叫做欧拉函数(m)110,,mrrr110,,mrrra04812159132610143711152.3剩余类（系）Residue2.3剩余类（系）Residue2.3剩余类（系）Residue例:a1,a2，…，an是一个模n的完系，则∑ak≡0(modn)n=2k+1n/2(modn)n=2k∑ak≡1+2+…+n≡n(1+n)/2（modn）若n=2k+1则，∑ak≡n*(k+1)≡0(modn)若n=2k则，∑ak≡k*(n+1)≡k(modn)2.3剩余类（系）Residue例2-10:a1,a2，…，an，b1,b2，…，bn是两个模n的完系，证明：当m是偶数时，a1+b1,a2+b2，…，an+bn一定不是模n的完系2.3剩余类（系）Residue例2-11设m=3,证明(2)模m的最小正简化剩余系的各数之和等于mψ(m)/2证明：若(m,a)=1,则(m,m-a)=1所以，设ai是在1~m/2和m互素的整数所以，ai和m-ai组成了m的最小正简化剩余系共ψ(m)/2对，和为mψ(m)/2思考：为什么没有考虑m/22.3剩余类（系）Residue例：将1(mod5)写成模15的剩余类的和例：写出模9的完系，要求全是奇数对于10呢？作业(5):p58第9题2.3剩余类（系）Residue定理,(m,n)=1,(1)Ca,Cb为2个不同的剩余类=nCa,nCb为2个不同的剩余类(2)为模m的一个完系=为模m的一个完系为模m的一个缩系=为模m的一个缩系(3)为模m的一个完系=为模m的一个缩系=(4)为模m的一个完系=为模m的一个缩系=(5)则x遍历m的一个完系，则nx+b也遍历如m=10,n=7,b=6,则13,20,27,34,41,48,55,62,69,76为一个完系Nm2m}1),(,11:{)}(1:{mlmllmkrkmaaa,,21mnanana,,21)(21,,maaa)(21,,mnananamaaa,,21)(21,,maaa},,,{},,{)(21)(21mmrrraaamaaa,,21},,,{},,{)(21)(_________21mmrrrnanana)(21,,maaa}1,,1,0{},,{_______)_________21mnananam}1,,1,0{},,{_______21maaamZb2.3剩余类（系）Residue定理2-2有所以2.3剩余类（系）Residue定理2-32.3剩余类（系）Residue2.3剩余类（系）Residue2.3剩余类（系）Residue定理2-4若（m,n）=1那么呢？)()()(nmmn)20()5()4()20(2.3剩余类（系）Residue关键n=pn时，其缩系的元素？排除与其最大公约数大于1的,也就是该数为xp(0,n-1)中，非缩系元素最小为0,最大pn-p,x取值0到pn-1–1，共pn-1个所以，如=22-2=2)(np1)(nnnppp)4(2.3剩余类（系）Residu