信息安全专题讲座-05.ppt
《信息安全专题讲座-05.ppt》由会员分享,可在线阅读,更多相关《信息安全专题讲座-05.ppt(21页珍藏版)》请在三一文库上搜索。
1、第五章 数论导引,1 素数和数的互素 除数(因子)的概念: 设z为有全体整数而构成的集合,若 b0且 使得a=mb,此时称b整除a.记为ba,还称b为a的除数(因子). 注:若a=mb+r且01被称为素数是指p的因子仅有1,-1,p,-p。,算术基本定理: 任何一个不等于0的正整数a都可以写成唯一的表达式aP11P22Ptt,这里P1P2P3Pt是素数,其中i0 最大公约数: 若a,b,cz,如果ca,cb,称c是a和b的公约数。正 整数d称为a和b的最大公约数,如果它满足 d是a和b的公约数。 对a和b的任何一个公约数c有cd。 注:1*. 等价的定义形式是: gcd(a,b)maxk ka
2、,kb 2*若gcd(a,b)=1,称a与b是互素的。,模 算术 全体整数而构成的集合对整数的加法和乘法的两种运算 是封闭的且满足算术运算的所有定律,此时我们称整数 集合z为整数环。整数环z对除法运算不封闭。 带余除法: az,0,可找出两个唯一确定的整数q和r, 使a=qm+r, 0=r m,q和r这两个数分别称为以m去除a所得到的商数和余数。 (若r=0则ma) 整数同余式和同余方程: 定义(同余)称整数a模正整数m同余于整数b,并写ab(mod m)是指mab, m称为模数。 注:1*.ma-ba=q1m+r,b=q2m+r即a和b分别 除以m有相同的余数。“同余”二字的来源就在于此。,
3、2*.相对于某个固定模数m的同余关系,是整数间的一种等价关系。具有等价关系的三点基本性质: 自反性:对任意整数a有aa(modm) 对称性:如果ab(modm)则ba(modm) 传递性:如果ab (modm)bc(modm)则ac(modm) 于是,全体整数集合z可按模m(m1)分成一些两两不交的等价类。 3*.整数模m同余类共有m个,他们分别为mk+0,mk+1, mk+2,mk+(m-1); kz,每一个算一类,每一类都可以选一个代表元,一般选这一类中的最小的非负整数。于是称0,1,2,m-1为标准完全剩余系。Z模12的标准剩余系为:0,1,2,3,4,5,6,7,8,9,10,11,4
4、*. 对于某个固定模m的同余式可以象普通的等式那样相加相减和相乘: (1)a(mod m)b(mod m)=(ab)(mod m) (2)a(mod m)*b(mod m)=a*b(mod m) 例子.通过同余式演算证明5601是56的倍数,2231是47的倍数。 解: 注意53=12513(mod56) 于是有561691(mod56) 对同余式的两边同时升到10次幂, 即有56560-1。 其次, 注意26=64-30(mod47), 于是,223=(26)325=(26 26)26 25 900*(-30)*(32) mod(47) (7)(-30)*(32) (mod47) 1(mod
5、47) 于是有 47223-1 定理:(消去率)对于abac(mod m)来说,若(a,m)1则bc(mod m) 5*.一次同余方程axb(mod m)这个方程有没有解,相当于问有没有那样一个整数x,使得对于某个整数y来说,有ax+my=b 定理:如记(a,m)=d,则同余方程axb(mod m)有解的充分必要条件是db。当这个条件满足时,恰有d个模m同余类中的整数是上述方程的解。 证明:略。(从ax+my=b入手),6*.整数环z模正整数m得到的剩余类集合可以记为zm(或z/(m) zm=0,1,m-1 在4中已说明zm对剩余类的加法,乘法是封闭的,可列出它们的加乘表。(见书214页)。我
6、们称为zm为剩余类环(或同余类环) 7*.在整数环z中是没有零因子的,即两个非零整数的乘积一定不等于0,但是剩余环则不然。 例z12中:3*4=12=0 说明,zm中的元素可分为两类,一类是零因子,即若zm,0存在zm且0,有*=0,称,都为zm中的零因子。另一类是可逆元,即若zm,存在zm使*=1,此时,互为各自的逆元,记-1=;-1=,定理:剩余类环zm中元素=a为zm的可逆元(a,m)=1 要证明这个定理,只需证明下列引理: 引理:任意两个整数a和b都有一个最大公约数,这样一个最大公约数d可以表示成a,b二数关于整系数的线性组合,即有s,tz,使dsatb。 证明:不妨设b0,用辗转相除
7、法,先用b去除a,得 a=q1b+r1,0=r1b; (1) 如果r1=0,停止,否则再用r1去除b,得 b=q2r1+r2,0=r2r1; (2) 如果r2=0,停止,否则再用r2去除r1,得 r1=q3r2+r3;0=r3r2; (3) 等等,这样一直进行下去,可得一系列关系式: rk-3=qk-1rk-2+rk-1,0=rk-1rk-2; (k-1) rk-2=qkrk-1+rk,0=rkrk-1; (k),由于历次所得的余数 r1 r2 r3 r4 rk=0 是严格递降的一串非负整数,故最后总会 出现余数为0的情形: rk-1=qk+1rk (k+1) 所以,进行有限步必停止,此时d=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息 安全 专题讲座 05
链接地址:https://www.31doc.com/p-2160955.html