第2章 信息安全数学基础（数论）计算机系统与网络安全技术 知识课件.ppt

电子科技大学 计算机科学与工程学院 ;第2章 信息安全数学基础（数论）;第2章 信息安全数学基础（数论）;子夏曰：“贤贤易色；事父母，能竭其力；事君，能致其身；与朋友交，言而有信。虽日未学，吾必谓之学矣。” 人际关系：父子；君臣；朋友；夫妻;2.整除的基本性质( N —整数集) (1) a(a≠0), ? a|0,a|a (同理?b ? N,1|b) (2) b|a, ?cb|ca (3) a|b, b|c ? a|c.（传递性） (4) a|b, a|c ? a|(xb+yc) (x,y?N) (5) b|a 且a≠0 ?|b|≤|a| (6) cb|ca, ?b|a;1.定义： 一个大于1的整数p，只能被1或者是它本身整除,而不能被其他整数整除，则称整数为素数(prime number)，否则就叫做合数(composite)。 eg 素数（2，3，5，7，11，13等） 合数（4，6，8，9，12等） ;2.补充定理(1)：设a是任一大于1的整数，则a的除1外的最小正因子q是素数，并且当a是合数时： ;2.补充定理(2)：若p是一个素数，a是任一整数，则有p|a或(p,a)=1;素数补充定理（续）;3.素数个数定理（1）： 素数的个数是无限的;素数定义及素数个数定理;1.整数的唯一分解定理定理（算术基本定理）: 设n∈Z, 有分解式, n = ±p1e1p2e2...pmem,其中p1, p2,…, pm∈Z+是互不相同的素数, e1,e2,…,em∈Z+, 并且数对(p1, e1), (p2, e2),…,(pm, em)由n唯一确定（即如果不考虑顺序，n的分解是唯一的）.;1.定义 两个整数a,b的最大公约数，就是能同时整除a和b的最大正整数,记为gcd(a,b)， 或(a,b). eg: gcd(5,7) = 1， gcd(24,60) = 12，;(2)欧几里得(Euclid)算法 设a, b?N, ab0, 用以下方法可求出 gcd(a,b). ;Euclid算法实例：求 gcd(132, 108). ;欧几里得算法（例1） ;欧几里得算法（例2）：求gcd(12345,1111) ;欧几里得算法抽象 ;欧几里得算法实现 ;特别a, b为素数时gcd(a,b)=1，存在 ma+nb=1. 上述求 rn = ma+nb的方法叫做扩展的Euclid算法 利用该方法我们可以求ax+by=d的解,这里d= (a,b);计算出了gcd(a,b); 但是并没有计算出两个数m，n来，使得： ma+nb=gcd(a,b);利用该方法我们可以求密码学方程ax+by=d的解,这里d= (a,b);第2章 信息安全数学基础（数论）;证明： 必要性:设a≡b (mod m), a=mp+r, b=mq+r, 0≤rm ? a-b=m(p-q), m|(a-b). 充分性:设m|(a-b), a=mp+r, b=mq+s, 0≤r, sm ? a-b=m(p-q)+(r-s) ? m|(r-s) 0≤|r-s|m, ∴ r=s, ? a≡b (mod m). 证毕;4.模运算的性质 设m∈Z+, a≡b (mod m), x≡y (mod m), 则有 (1) a+x≡b+y (mod m) （加法） (2) a-x ≡b-y (mod m) （减法） (3) ax ≡ by (mod m) （乘法） ;例： 求解2x＋7＝3（mod 17） 解：2x＝3－7 → 2x＝－4 x＝－2 x＝15（mod 17）;4.模运算的性质 （4）除法： 例： 求解5x＋6＝13（mod 11） 解：5x＝13－6 → 5x＝7（mod 11） x=7/5??? 注意到7＝18＝29＝40（mod 11） 所以： 5x＝7（mod 11）→ 5x＝40（mod 11） x＝8（mod 11）;5.模m的乘法逆元 定义：设m∈Z+, x, y∈Z, 如果xy≡1 (mod m), 则称y是x的模m乘法逆元, 记为: y=x-1;欧几里德算法与乘法逆元 如果算法gcd（a，b）输出rm＝1，则b有乘法逆元 如果求出了ma+nb=1中的整数m，n，则可以求出b（mod a）的乘法逆元。 欧几里得算法没有给出