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

1、学习要点：了解数论、群论、有限域理论的基本概念了解模运算的基本方法了解欧几里德算法、费马定理、欧拉定理、中国剩余定理了解群的性质了解有限域中的计算方法1、除数(因子)的概念：设z为由全体整数而构成的集合，若 b0且 使得a=mb,此时称b整除a.记为b a,还称b为a的除数除数(因子因子).注注:若a=mb+r且0r1被称为质数是指p的因子仅有1,-1,p,-p。Zmba,|ba算术基本定理算术基本定理：任何一个不等于任何一个不等于0的正整数的正整数a都可以写成唯一的表达式都可以写成唯一的表达式aP11P22Ptt，这里这里P1P2P3Pt是质数，其中是质数，其中i0最大公约数：最大公约数：若

2、若a,b,cz，如果，如果c a，c b，称，称c是是a和和b的的公约数公约数。正。正整数整数d称为称为a和和b的的最大公约数最大公约数，如果它满足，如果它满足d是是a和和b的公约数。的公约数。对对a和和b的任何一个公约数的任何一个公约数c有有c d。注注：1*.等价的定义形式是：等价的定义形式是：gcd（a,b）maxk k a且且k b 2*若若gcd（a,b）=1，称，称a与与b是是互素互素的的。带余除法带余除法：az,0，可找出两个唯一确定的整数，可找出两个唯一确定的整数q和和r,使使a=qm+r,0=r1）分成一些两两不交的等价类。3*.对于某个固定模对于某个固定模m的同余式可以象普

3、通的等式那样的同余式可以象普通的等式那样相相加加、相减相减和和相乘，可结合相乘，可结合：(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）5601是56的倍数（2）2231是47的倍数。解：注意53=12513(mod56)于是有561691(mod56)对同余式的两边同时升到10次幂，即有56 560-1。同理,注意到26=6417(mod47),于是223=(26)325=(26 26)26 25

4、289*(17)*(32)mod47 7*17*32(mod47)25*32(mod47)1(mod47)于是有 47 223-1定理定理：(消去律)对于abac（mod m）来说，若gcd(a,m)1则bc(mod m)例如1：附加条件不满足的情况63=182mod867=422mod8但37mod8例如2：附加条件满足的情况53157mod8511=557mod8311mod8原因：模m的乘法运算返回的结果是0到m-1之间的数，如果乘数a和模数m有除1以外的共同因子时将不会产生完整的余数集合。Z801234567乘以606121824303642模8后的 余数06420642Z801234

5、567乘 以505101520253035模8后 的余数05274163Extended 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-1modf4）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）QX1X2X3Y1（T1）Y2（T2）Y3(T3)-101170120501201-5171

6、1-517-1635-1636-35216-352-7411=gcd Format定理定理：如果p是质数并且a是不能被p整除的正整数,那么，ap-11(mod p)Format定理的另一种形式：对gcd（a，p）1 有apa(modp)a=7,p=19,求ap-1modp解：72=4911mod1974121mod197mod197849mod1911mod19716121mod197mod19ap-1=718=71672711mod191mod19比24小而与24 互素的正整数为：1、5、7、11、13、17、19、23。故 这12个数是：1,2,4,5,8,10,11,13,16,17,1

7、9,208)24(12)17)(13()7()3()21(欧拉定理（欧拉定理（Euler）（文字表述）：）（文字表述）：若整数若整数a与整数与整数n互素，则互素，则a(n)1(mod n)注：1*.np时，有ap-11(mod p)为Format定理！2*.易见a(n)+1a(mod n)am=1modn，如果，如果a与与n互素，则至少有一互素，则至少有一个整数个整数m（如（如m=phi(n)）满足这一方程，）满足这一方程，称满足方程的最小正整数称满足方程的最小正整数m为模为模n下下a的的阶阶。如果如果a的阶的阶m=phi（n），则称），则称a为为n的的本本原元原元。本原元并不一定唯一本原元并

8、不一定唯一并非所有的整数都有本原元，只有以下形式并非所有的整数都有本原元，只有以下形式的整数才有本原元：的整数才有本原元：2,4,pa,2pa（a为整数，为整数，p为奇质数）为奇质数）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的本原元。中国剩余定理例子：（孙子算经）今有物不知其数。三三数之余二；五五数之余三；七七数之余二。问物几何？2(mod 3)3(mod 5)2(mod 7)xxx答曰：二十三。232*70+3*21+2*15(mod 105)（口 诀：三 人 同

9、 行 七 十 稀，五 树 梅 花 廿 一 枝，七子团圆月正半，除百零五便得知。）问，70，21，15如何得到的？原问题为：求解同余方程组注意注意：若x0为上述同余方程组的解，则x0=x0+105*k(kz)也为上述同余方程组的解。有意义的是，解题口诀提示我们先解下面三个特殊的同余方程组(1)(2)(3)的特殊解=?=?=?以方程（1）为对象，相当于解一个这样的同余方程 35y1(mod 3)，为什么呢？原因是，从（1）的模数及条件知，x应同时是5和7的倍数，即应是35的倍数，于是可以假设x35y有：1(mod3)0(mod5)0(mod7)xxx0(mod3)1(mod5)0(mod7)xxx

10、0(mod3)0(mod5)1(mod7)xxx10001000135y1(mod 3)相当于2y1(mod)3解出y=2（mod3）于是x35*2 70(mod105)类似地得到（2）、（3）方程的模105的解21、15。于是有：得700012101015100)105(mod2315*221*370*2100201030012232中国剩余定理中国剩余定理：设自然数m1,m2,mr两两互素，并记M=m1m2mr，b1.br表示r个整数，则同余方程组（A）在模M同余的意义下有唯一解。1122(mod)(mod).(mod)rrxbmxbmxbm证明：M=m1m2mr，令Mj=M/mj=m1m

11、2mj-1mj+1mr求yj使：Mjyj 1 mod mj j=1,2,.r由于（Mj,mj)=1，所以yj是存在的。令：x0 b1M1y1+b2M2y2+brMryr mod M(B)可证明x0便是（A）式的解。为证明这一点，注意j=h时mh|Mj。故Mj 0 mod mh,即x0中各项除第h项外，其余都模mh同余0。又Mhyh 1 mod mh,所以：X0 bhMhyh mod mh bh mod mh。即满足(A)式，x0是其解。下面证明x0是模M的唯一解。如若不然，设x1和x2是（A）式模M的两个解，则有：x1 x2 bj mod mj(j=1r)那么，x1-x2 0 mod mj,即

12、mj|(x1-x2)（j=1r)因此，M（x1-x2),即x1-x2 0 mod M所以x1，x2是模M的相同解，从而证明了对于模M式（A）的解是唯一的。例如：x1 mod 2x2 mod 3x3 mod 5解：M=235=30M1=15,M2=10,M3=615y11mod2,y1=110y21mod3,y2=16y31mod5,y3=1所以,x=1151+2101+361=5323 mod 30群的概念是由一个非空集合G组成，在集合G中定义了一个二元运算符“”，并满足以下性质的代数系统，记为G,交换群：有限群无限群有限群的阶循环群循环群的生成元群中的单位元是唯一的群中每一个元素的逆元是唯一

13、的(消去律)对任意的，如果 ，或，则 Gcba,cabacb acab域的概念域是由一个非空集合F组成，在集合F中定义了两个二元运算符：“+”和“”，并满足：域记为F,+,两个定义：两个定义：有限域有限域的阶域的实质：域是一个可以在其上进行加法、减法、乘法和除法运算而结果不会超出域的集合。如有理数集合、实数集合、复数集合都是域，但整数集合不是 减法：a-b=a+(-b)除法：a/b=a(b-1)密码学常用素域GF(p)或阶为2m的域GF(2m)生成元可证明：在GF(p)中至少存在一个元素g，使得GF(p)中任意非零元素可以表示成g的某次方幂的形式，g称为GF(p)的生成元逆元 有限域GF（23），5是GF（23）的生成元 50151552253105445520568571758165911510951122512185132151413515195163517155186519752012521145221生成元：逆元取：GF（24）的元素：1)(4xxxf（0000）(0001)(0010)(0011)(0100)(0101)(0110)(0111)(1000)(1001)(1010)(1011)(1100)(1101)(1110)(1111)生成元为：a=x