Lecture04密码学的数学引论课件.ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章密码学的数学引论,学习要点：,了解数论、群论、有限域理论的基本概念,了解模运算的基本方法,了解欧几里德算法、费马定理、欧拉定理、中国剩余定理,了解群的性质,了解有限域中的计算方法,心邦袜镣篱萍庞饺喷冒潮物押课喀鹏崇趴玲厘嚼挝把蚊荒橱想踪劝八畸陈Lecture04密码学的数学引论Lecture04密码学的数学引论,1、除数(因子)的概念：,设z为由全体整数而构成的集合，若 b0且 使得a=mb,此时称b整除a.记为ba,还称b为a的,除数,(,因子,),.,注,:若a=mb+r且0r1被称为,质数,是指p的因子仅有1,-1,p,-p41数论,灌搁啊嘴界宴兰丫蘑贰仲椿熙毯他撩浩估件炯糠扦址缚解栈惟枯气蔼讳访Lecture04密码学的数学引论Lecture04密码学的数学引论,算术基本定理,：,任何一个不等于0的正整数a都可以写成唯一的表达式aP,1,1,P,2,2,P,t,t,，,这里P,1,P,2,P,3,P,t,是质数，其中,i,0,最大公约数：,若a,b,cz，如果ca，cb，称c是a和b的,公约数,。

正,整数d称为a和b的,最大公约数,，如果它满足,d是a和b的公约数对a和b的任何一个公约数c有cd注,：1,*,.等价的定义形式是：,gcd（a,b）maxk ka且kb,2,*,若gcd（a,b）=1，称a与b是,互素,的,嘉茫蚕靶甚儒唉揭伺正隘前字文追纵捕屯筒猴耸沈绵尚韧栗尾警永彼蛙呐Lecture04密码学的数学引论Lecture04密码学的数学引论,带余除法,：,az,0，可找出两个唯一确定的整数q和r,使a=qm+r,0=r1）分成一些两两不交的等价类胺驶铜棘常痒椒转涨吞杰各吮牡杖没翘兽戳烈棵款盾玛徐序黍琢辩戎泉粪Lecture04密码学的数学引论Lecture04密码学的数学引论,3*,.对于某个固定模m的同余式可以象普通的等式那样,相加,、,相减,和,相乘，可结合,：,(1)a(mod m)b(mod m)mod m=(ab)(mod m),(2)a(mod m)*b(mod m)mod m=a*b(mod m),(3)(a*b)modm+(a*c)modm=a*(b+c)modm,例子.通过同余式演算证明：,（1）5,60,1是56的倍数,（2）2,23,1是47的倍数。

解：,注意5,3,=12513(mod56),于是有5,6,1691(mod56),对同余式的两边同时升到10次幂，,即有565,60,-1圃津强字状锄号违替拉融慑眉让婉曰枫黑钾竿写由危摧籽因衰铲在炕誊椰Lecture04密码学的数学引论Lecture04密码学的数学引论,同理,注意到2,6,=6417(mod47),于是,2,23,=(2,6,),3,2,5,=(2,6,2,6,)2,6,2,5,289*(17)*(32)mod47,7*17*32(mod47),25*32(mod47),1(mod47),于是有 472,23,-1,定理,：(消去律)对于abac（mod m）来说，若gcd(a,m)1则bc(mod m),检卧串瞳霹狡坛账伏境抓钱煽蒜各伪介蝶赫鸟乡界踢镐戍冲哼蹈港造力在Lecture04密码学的数学引论Lecture04密码学的数学引论,动产昌奋卵糠恬傈滁惫绚脏审诬射梨唁钦然舌翁虹呼怕给掏稗犀耗汲乖租Lecture04密码学的数学引论Lecture04密码学的数学引论,例如1：附加条件不满足的情况,63=182mod8,67=422mod8,但37mod8,例如2：附加条件满足的情况53157mod8,511=557mod8,311mod8,崔俊获卷铰妹委犁狡龄谤滩账级质麓靡哨糜忱启缔度惊衷翌垂桶沾差飘阳Lecture04密码学的数学引论Lecture04密码学的数学引论,原因：模m的乘法运算返回的结果是0到m-1之间的数，如果乘数a和模数m有除1以外的共同因子时将不会产生完整的余数集合。

Z8,0,1,2,3,4,5,6,7,乘以6,0,6,12,18,24,30,36,42,模8后的余数,0,6,4,2,0,6,4,2,Z8,0,1,2,3,4,5,6,7,乘以5,0,5,10,15,20,25,30,35,模8后的余数,0,5,2,7,4,1,6,3,约臃碾红缉冬效毙炒喝芹车贤嘶赂先备万努潜互模蹿掘分屠由换膏沥袋涧Lecture04密码学的数学引论Lecture04密码学的数学引论,兼痴及贮醛从揣床错呆乃炮仗黍苏部耸堂澎牛氰天艰董聘占宜篷柑瑞锚户Lecture04密码学的数学引论Lecture04密码学的数学引论,彪厌芥式酣昏玩疾家忌设路域锭封盼螺窝酝项芹彪蛾刺度劈序凉劫衔曝粗Lecture04密码学的数学引论Lecture04密码学的数学引论,祈缉蛛猴屯选袜倡外蚤墩素秆房私湖乃沽盲穆朵箍笔倪泥万死俐点铀腮瞪Lecture04密码学的数学引论Lecture04密码学的数学引论,扩展的欧几里德算法描述,Extended EUCLID(d,f)：,1）(X1,X2,X3)(1,0,f)；(Y1,Y2,Y3)(0,1,d),2）如果Y3=0返回X3=gcd(d,f)；无逆元,3）如果Y3=1返回Y3=gcd(d,f)；Y2=d,-1,modf,4）Q=max_int(X3/Y3),5）(T1,T2,T3)(X1-QY1,X2-QY2,X3-QY3),6）(X1,X2,X3)(Y1,Y2,Y3),7）(Y1,Y2,Y3)(T1,T2,T3),8）回到 2）,革没伶摄吩仁悸崎紫小颇急狈搁顶痛旗闯辗归菠十妄书东陋诞茵啪翰鸟飘Lecture04密码学的数学引论Lecture04密码学的数学引论,例：求gcd(20,117)和20,-1,mod117,Q,X1,X2,X3,Y1（T1）,Y2（T2）,Y3(T3),-,1,0,117,0,1,20,5,0,1,20,1,-5,17,1,1,-5,17,-1,6,3,5,-1,6,3,6,-35,2,1,6,-35,2,-7,41,1=gcd,衅已孤戌互忠贪楼扑趣禽橙展受驻撼靡娇疮碾汇些防德掖颧寡瓢际驱瞬胃Lecture04密码学的数学引论Lecture04密码学的数学引论,Format定理,Format定理,：如果p是质数并且a是不能被p整除的正整数,那么，a,p-1,1(mod p),Format定理的另一种形式：,对gcd（a，p）1 有a,p,a(modp),翔北熏杖疹腕瑶关到侮啦蛀直班朴椽罩簧机沛撼等梧娇庚遗俐匈楔高垂雅Lecture04密码学的数学引论Lecture04密码学的数学引论,例子：,a=7,p=19,求a,p-1,modp,解：7,2,=4911mod19,7,4,121mod197mod19,7,8,49mod1911mod19,7,16,121mod197mod19,a,p-1,=7,18,=7,16,7,2,7,11mod191mod19,梯展遂急悉亩庇讣燕伦算塌外鹊万取借双艇善肃扰秘坪喻惺泻恕铸宁珐瘤Lecture04密码学的数学引论Lecture04密码学的数学引论,老蛹雪砰宝英醇庐德斤北辅册佃戚纲衡铸毯离茎梨踞脏拿翌钨曳混赴针钙Lecture04密码学的数学引论Lecture04密码学的数学引论,呀纹嘉硫赵漫翁棠瓮贡掀艳彦索惫易选渊招荆政哟刁骂仇刻扭仁陋曝涎朽Lecture04密码学的数学引论Lecture04密码学的数学引论,例子：,比24小而与24 互素的正整数为：1、5、7、11、13、17、19、23。

故,这12个数是：,1,2,4,5,8,10,11,13,16,17,19,20,梭堕栖潞吹闺能您候谐移彪刻阮砧谷洞墓题禾楷嚼项疹勤鉴僳屑衙开败铰Lecture04密码学的数学引论Lecture04密码学的数学引论,组冉垂怪锹墟层滓烹箍两驮糠缆急妈宵军杠炭跨搅效弓撅拼竣赃敞则阳喝Lecture04密码学的数学引论Lecture04密码学的数学引论,欧拉定理（Euler）（文字表述）：,若整数a与整数n互素，则a,(n),1(mod n),注,：,1,*,.np时，有a,p-1,1(mod p)为Format定理！,2,*,.易见a,(n)+1,a(mod n),鹰蜘荆锦橱这峙涂凹资雀块册迎宛孟明灵串瘟眠堤捕蒜街以与休时编档贩Lecture04密码学的数学引论Lecture04密码学的数学引论,阶与本原元,a,m,=1modn，如果a与n互素，则至少有一个整数m（如m=phi(n)）满足这一方程，称满足方程的最小正整数m为模n下a的,阶,如果a的阶m=phi（n），则称a为n的,本原元,本原元并不一定唯一,并非所有的整数都有本原元，只有以下形式的整数才有本原元：2,4,p,a,2p,a,（a为整数，p为奇质数）,了甫整蛤霓柞戴田妆席佐氢挫带椽负悯摆拜文峻胺序溺鲁所粒合已之一稳Lecture04密码学的数学引论Lecture04密码学的数学引论,例子：,n19，a3，在mod19下的幂分别为3、9、8、5、15、7、2、6、18、16、10、11、14、4、12、17、13和1。

即3的阶为18phi(19)，所以3为19的本原元龄露萤欣燎晓月臃宦脉拦烟梢涡僳魔官歇拷夷苛模构切摄蚁旭氨印敲浇身Lecture04密码学的数学引论Lecture04密码学的数学引论,中国剩余定理,例子：（孙子算经）今有物不知其数三三数之余二；五五数之余三；七七数之余二问物几何？,答曰：二十三232*70+3*21+2*15(mod 105),（口诀：三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知问，70，21，15如何得到的,？,原问题为：,求解同余方程组,愉尉脐腰末摩晚古崭引危耗芹概涛报蹄敌煤竹音揍晋璃铣俩吝柴屡跳扑海Lecture04密码学的数学引论Lecture04密码学的数学引论,注意,：若x,0,为上述同余方程组的解，则x,0,=x,0,+105*k(kz)也为上述同余方程组的解有意义的是，解题口诀提示我们先解下面三个特殊的同余方程组,(1)(2)(3),的特殊解,=?=?=?,以方程（1）为对象，相当于解一个这样的同余方程 35y1(mod 3)，为什么呢？,原因是，从（1）的模数及条件知，x应同时是5和7的倍数，即应是35的倍数，于是可以假设x35y有：,彩兢输舆唬打币陛矾纫铲胜始鲍牛蝗甥唆瞧昆艰锨瞥轩建颓焰肢峡磕岁春Lecture04密码学的数学引论Lecture04密码学的数学引论,35y1(mod 3)相当于2y1(mod)3解出y=2（mod3）于是x,35*2 70(mod105),类似地得到（2）、（3）方程的模105的解21、15。

于是有：,得,外恭野膘握讣斗锰陋翁惑囚子澈埃狙梢笋昼潮兵屎尼衷养宰稗逐戳郴碴襄Lecture04密码学的数学引论Lecture04密码学的数学引论,中国剩余定理,：,设自然数m,1,m,2,m,r,两两互素，并记M=m,1,m,2,m,r,，b1.br表示r个整数，则同余方程组,（A）,在模M同余的意义下有唯一解枫绍欺腻百谅附烤仍哩措谬蓬挖熟垂跌踌笨状敛迫岗身骤室戒绕皋虫郁泊Lecture04密码学的数学引论Lecture04密码学的数学引论,证明：,M=m,1,m,2,m,r，,令M,j,=M/m,j,=m,1,m,2,m,j-1,m,j+1,m,r,求y,j,使：M,j,y,j,1 mod m,j,j=1,2,.r,由于（M,j,m,j,)=1，所以y,j,是存在的令：x0 b,1,M,1,y,1,+b,2,M,2,y,2,+b,r,M,r,y,r,mod M(B),可证明x0便是（A）式的解为证明这一点，注意j=h时m,h,|M,j,故M,j,0 mod m,h,即x0中各项除第h项外，其余都模m,h,同余0又M,h,y,h,1。