信息安全专题讲座—05.pptVIP

  1. 1、本文档共21页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
信息安全专题讲座—05

第五章 数论导引 ;§算术基本定理: 任何一个不等于0的正整数a都可以写成唯一的表达式a=P1α1P2α2…Ptαt,这里P1P2P3…Pt是素数,其中αi0 §最大公约数: 若a,b,c∈z,如果c∣a,c∣b,称c是a和b的公约数。正 整数d称为a和b的最大公约数,如果它满足 d是a和b的公约数。 对a和b的任何一个公约数c有c∣d。 注:1*. 等价的定义形式是: gcd(a,b)=max{k∣ k∣a,k∣b} 2*.若gcd(a,b)=1,称a与b是互素的。 ;模 算术 全体整数而构成的集合对整数的加法和乘法的两种运算 是封闭的且满足算术运算的所有定律,此时我们称整数 集合z为整数环。整数环z对除法运算不封闭。 带余除法: ?a∈z,0,可找出两个唯一确定的整数q和r, 使a=qm+r, 0=r m,q和r这两个数分别称为以m去除a所得到的商数和余数。 (若r=0则m∣a) 整数同余式和同余方程: 定义(同余)称整数a模正整数m同余于整数b,并写a≡b(mod m)是指m∣a-b, m称为模数。 注:1*.m∣a-b?a=q1m+r,b=q2m+r即a和b分别 除以m有相同的余数。“同余”二字的来源就在于此。 ;2*.相对于某个固定模数m的同余关系,是整数间的一种等价关系。具有等价关系的三点基本性质: 自反性:对任意整数a有a≡a(modm) 对称性:如果a≡b(modm)则b≡a(modm) 传递性:如果a≡b (modm)b≡c(modm)则a≡c(modm) 于是,全体整数集合z可按模m(m1)分成一些两两不交的等价类。 3*.整数模m同余类共有m个,他们分别为mk+0,mk+1, mk+2,…mk+(m-1); k∈z,每一个算一类,每一类都可以选一个代表元,一般选这一类中的最小的非负整数。于是称[0],[1],[2],…[m-1]为标准完全剩余系。Z模12的标准剩余系为:[0],[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11] ;4*. 对于某个固定模m的同余式可以象普通的等式那样相加相减和相乘: (1)a(mod m)±b(mod m)=(a±b)(mod m) (2)a(mod m)*b(mod m)=a*b(mod m) 例子.通过同余式演算证明560-1是56的倍数,223-1是47的倍数。 解: 注意53=125≡13(mod56) 于是有56≡169≡1(mod56) 对同余式的两边同时升到10次幂, 即有56∣560-1。 其次, 注意26=64≡-30(mod47), 于是 ;223=(26)3·25=(26 · 26)26 · 25 ≡900*(-30)*(32) mod(47) ≡(7)(-30)*(32) (mod47) ≡1(mod47) 于是有 47∣223-1 定理:(消去率)对于ab≡ac(mod m)来说,若(a,m)=1则b≡c(mod m) 5*.一次同余方程ax≡b(mod m)这个方程有没有解,相当于问有没有那样一个整数x,使得对于某个整数y来说,有ax+my=b 定理:如记(a,m)=d,则同余方程ax≡b(mod m)有解的充分必要条件是d∣b。当这个条件满足时,恰有d个模m同余类中的整数是上述方程的解。 证明:略。(从ax+my=b入手) ;6*.整数环z模正整数m得到的剩余类集合可以记为zm(或z/(m)) zm={[0],[1],…,[m-1]} 在4中已说明zm对剩余类的加法,乘法是封闭的,可列出它们的加乘表。(见书214页)。我们称为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,t∈z,使d=sa+tb。 证明:不妨设b0,用辗转相除法,先用b去除a,得 a=q1b+r1,0=r1b; (1) 如果r1=0,停止,否则再用r1去除b,得

文档评论(0)

jdy261842 + 关注
实名认证
文档贡献者

分享好文档!

1亿VIP精品文档

相关文档