信息安全数学基础ppt课件.pptVIP

计算机网络安全基础-07 信息安全数学基础 信息科学与工程学院 网络信息的安全威胁 网上犯罪形势不容乐观； 有害信息污染严重； 网络病毒的蔓延和破坏； 网上黑客无孔不入； 机要信息流失与信息间谍潜入； 网络安全产品的自控权； 信息战的阴影不可忽视。 网络安全体系的五类服务 网络安全体系的五类服务 本课程的相关知识点 什么是密码技术？ 密码系统的安全 密码系统的攻击 第八章 同余方程 8.5 mod p的高次根 1.定理： (1)对于素数p，若gcd(n,p-1)，则每一个y都有 模p的n次根。若r是n模p-1的乘法逆元，则y模p的 一个n次根为yr mod p。 证明：验证(yr)n = y mod p。 (2)对于素数p，若gcd(n,p-1)=n，即n|p-1，且 gcd(n,(p-1)/n)=1，若y是模p的一个n次剩余，r是n 模(p-1)/n的乘法逆元，则y模p的n次根为yr mod p。 2.举例： (1)求2模101的立方根； (2)求58模199的11次根。 第八章 同余方程 总结： p为素数，且 或者 存在： 若p≡3 mod 4，则满足x2=y mod p的平方根为： x=y(p+1)/4 mod p (不一定存在) 若gcd(n,p-1)=1，则满足xn=y mod p的n次根为： x=yr mod p, r=n-1 mod p-1 若n|p-1,gcd(n,(p-1)/n)=1，则满足xn=y mod p 的n次根为：(不一定存在) x=yr mod p, r=n-1 mod (p-1)/n 第八章 同余方程 8.6 欧拉判别准则 并不是任何数y都存在模p的n次根，因此在求 解之前可以用欧拉判别准则进行判定。 欧拉判别准则用来有效判断当p=1 mod n时， 整数y是否存在模素数p的n次根。 判定方法： (1)当gcd(n,p-1)=1时，所有的数y都有模p的n 次根。 例如：x3=y (mod 101) x7=y (mod 181) (2)定理：设p为素数，p=1 mod n，当且仅当 gcd(y,p)=1,y(p-1)/n=1(mod p)时，y是模p的n次幂。 第八章 同余方程 证明： 必要条件： y是模p的n次幂? y(p-1)/n=1 mod p 设y=xn mod p，有 y(p-1)/n=1 mod p= x(p-1)=1 mod p 充分条件： y(p-1)/n=1 mod p ? y是模p的n次幂 设g是模p的本原根，有y=grmod p y(p-1)/n=1 mod p ? gr(p-1)/n=1 mod p ? ?(p)|r(p-1)/n ? (p-1)|r(p-1)/n ?n|r ?r=kn 所以 y=gr=(gk)n mod p 第八章 同余方程 (3) 推论： 设p为奇素数，y和p互素，则有： y(p-1)/2=1 mod p时，y是模p的平方。 y(p-1)/2=-1 mod p时，y是模p的非平方。 举例：14是模101的平方吗？ 14 50 1 95 25 1 95 24 95 36 12 95 84 6 95 87 3 95 87 2 84 95 1 84 0 95×84%101=1 课内作业：68是模109的立方吗？ 第八章 同余方程 8.7 模为合数n的根 1.孙子定理(中国剩余定理) 设m1,m2,…,mk是两两互素的正整数，则同余 方程组 x=b1 mod m1 x=b2 mod m2