Lecture04密码学的数学引论.ppt
《Lecture04密码学的数学引论.ppt》由会员分享,可在线阅读,更多相关《Lecture04密码学的数学引论.ppt(43页珍藏版)》请在三一文库上搜索。
1、第四章 密码学的数学引论,学习要点: 了解数论、群论、有限域理论的基本概念 了解模运算的基本方法 了解欧几里德算法、费马定理、欧拉定理、中国剩余定理 了解群的性质 了解有限域中的计算方法,1、除数(因子)的概念: 设z为由全体整数而构成的集合,若 b0且 使得a=mb,此时称b整除a.记为ba,还称b为a的除数(因子). 注:若a=mb+r且01被称为质数是指p的因子仅有1,-1,p,-p。,41 数论,算术基本定理: 任何一个不等于0的正整数a都可以写成唯一的表达式aP11P22Ptt,这里P1P2P3Pt是质数,其中i0 最大公约数: 若a,b,cz,如果ca,cb,称c是a和b的公约数。
2、正 整数d称为a和b的最大公约数,如果它满足 d是a和b的公约数。 对a和b的任何一个公约数c有cd。 注:1*. 等价的定义形式是: gcd(a,b)maxk ka且kb 2*若gcd(a,b)=1,称a与b是互素的。,带余除法: az,0,可找出两个唯一确定的整数q和r, 使a=qm+r, 0=r m,q和r这两个数分别称为以m去除a所得到的商数和余数。 (若r=0则ma) 整数同余: 定义:如果a mod m =b mod m,则称整数a模正整数m同余于整数b,并写ab(mod m)是指m(ab), m称为模数。 注:1*.ma-ba=q1m+r,b=q2m+r即a和b分别 除以m有相同
3、的余数。“同余”二字的来源就在于此。,二、模算术,2*.相对于某个固定模数m的同余关系,是整数间的一种等价关系。具有等价关系的三点基本性质: 自反性:对任意整数a有:aa(mod m) 对称性:如果ab(mod m),则ba(mod m) 传递性:如果ab (mod m)bc(mod m),则ac(mod m) 于是,全体整数集合z可按模m(m1)分成一些两两不交的等价类。,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
4、m) (3)(a*b)modm+(a*c)modm=a*(b+c)modm 例子.通过同余式演算证明: (1)5601是56的倍数 (2)2231是47的倍数。 解: 注意53=12513(mod56) 于是有561691(mod56) 对同余式的两边同时升到10次幂, 即有56560-1。,同理, 注意到26=6417(mod47), 于是 223=(26)325=(26 26)26 25 289*(17)*(32) mod47 7*17*32 (mod47) 25*32(mod47) 1(mod47) 于是有 47223-1 定理:(消去律)对于abac(mod m)来说,若gcd(a,m
5、)1则bc(mod m),例如1:附加条件不满足的情况 63=182mod8 67=422mod8 但37mod8 例如2:附加条件满足的情况 53157mod8 511=557mod8 311mod8,原因:模m的乘法运算返回的结果是0到m-1之间的数,如果乘数a和模数m有除1以外的共同因子时将不会产生完整的余数集合。,扩展的欧几里德算法描述,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-1modf 4)Q=ma
6、x_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),例:求gcd(20,117)和20-1mod117,Format定理, Format定理:如果p是质数并且a是不能被p整除的正整数,那么,ap-11(mod p) Format定理的另一种形式: 对gcd(a,p)1 有apa(modp),例子:,a=7,p=19,求ap-1modp,解:72=4911mod19 74121mod197mod19 7849mod1911mod19 716
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Lecture04 密码学 数学 引论
链接地址:https://www.31doc.com/p-2145791.html