密码学——第4章 数论与有限域基础.pptxVIP

第一部分第四章 数论与有限域基础;本章提纲;数论基础;数论基础;数论基础;数论基础;数论基础;数论基础;数论基础;数论基础;数论基础;数论基础;数论基础;数论基础;数论基础;数论基础;数论基础;数论基础;数论基础;数论基础;数论基础;数论基础;欧几里得 (Euclid) 算法 求最大公因子例子，gcd(1970, 1066) 1970 = 1 x 1066 + 904 gcd(1066, 904)1066 = 1 x 904 + 162 gcd(904, 162)904 = 5 x 162 + 94 gcd(162, 94)162 = 1 x 94 + 68 gcd(94, 68)94 = 1 x 68 + 26 gcd(68, 26)68 = 2 x 26 + 16 gcd(26, 16)26 = 1 x 16 + 10 gcd(16, 10)16 = 1 x 10 + 6 gcd(10, 6)10 = 1 x 6 + 4 gcd(6, 4)6 = 1 x 4 + 2 gcd(4, 2)4 = 2 x 2 + 0 gcd(2, 0);欧几里得 (Euclid) 算法 求乘法逆元 如果gcd(a, b) = 1 ，则 b 在 mod a 下有乘法逆元（不妨设 ba），即存在x (xa)，使得 bx≡1 mod a。 扩展 Euclid 算法可求出 gcd(a, b)，当 gcd(a, b) = 1，还得到 b 的逆元。;;群、环、域;群、环、域;群、环、域;群、环、域;有限域基础;有限域基础;有限域基础;?;有限域基础;有限域基础;有限域基础;有限域基础;有限域基础;?;?;本章小结;本章作业