域(Fields) 15 域F,可以记为F,+,,是有加法和乘法的两个 二元运算的元素的集合，对于F中的任意元素 a,b,C,满足以下公理： (A1-M6),F是一个整环 (M7),乘法逆元，对于F中的任意元素a(除0以外)，F 中都存在一个元素a1,使得aa1=(a)a=1. 域就是一个集合，在其上进行加减乘除而不脱离该 集合，除法按以下规则定义：ab=a(b1). 有理数集合，实数集合和复数集合都是域；整数集合 不是域，因为除了1和-1有乘法逆元，其他元素都无 乘法逆元 2022/10/9 现代密码学理论与实践04 7/51
2022/10/9 现代密码学理论与实践04 7/51 域 (Fields) ⚫ 域F, 可以记为{F, +, x}, 是有加法和乘法的两个 二元运算的元素的集合，对于F中的任意元素 a, b, c, 满足以下公理： ⚫ (A1-M6), F是一个整环 ⚫ (M7), 乘法逆元, 对于F中的任意元素a(除0以外), F 中都存在一个元素a -1 , 使得aa-1=(a-1 )a=1. ⚫ 域就是一个集合，在其上进行加减乘除而不脱离该 集合, 除法按以下规则定义: a/b=a(b-1 ). ⚫ 有理数集合, 实数集合和复数集合都是域；整数集合 不是域，因为除了1和-1有乘法逆元，其他元素都无 乘法逆元
少海连拉家专 群、环和域的关系 15 (A1)Closure under addition: If a and b belong to S,then a+b is also in (A2)Associativity of addition: a+(b+c)=(a+b)+c for all a,b,cinS dno.ueilaqV dnoa9 (A3)Additive identity: There is an element 0 in R such that a+0=0+a=a for all ain S (A4)Additive inverse: For each a in S there is an element-a in S such that a+(-a)=(-a)+a=0 (A5)Commutativity of addition: a+b=b+a for all a,binS (M1)Closure under multiplication: If a and b belong to S,then ab is also in S (M2)Associativity of multiplication: a(bc)=(ab)c for all a,b,c in S (M3)Distributive laws: a(b+c)=ab ac for all a,b,c in S (a+b)c=ac bc for all a,b,c in (M4)Commutativity of multiplication: ab ba for all a,b in S (M5)Multiplicative identity: There is an element 1 in S such that al =la=a for all a in S (M6)No zero divisors: If a,b in S and ab=0,then either a=00rb=0 (M7)Multiplicative inverse: If a belongs to S and a 0,there is an element a-l in S such that aa-1=a-a 1 Figure 4.1 Group,Ring,and Field 现代密码学理论与买践04 8/51
2022/10/9 现代密码学理论与实践04 8/51 群、环和域的关系
海至家大 4.2 MODULAR ARITHMETIC 15 给定任意正整数n和a,如果用a除以n,得到的商g 和余数满足如下关系： a=qn+r0sr<n;q=☐a/n」□x」表示小于等于x的最大 整数 Eg: 11=1X7+4,=4; -11=(-2)x7+3,=3 2n 3n q11 q+1)m Figure 4.2 The Relationship a=gn+r;0sr<n 2022/10/9 现代密码学理论与实践04 9/51
2022/10/9 现代密码学理论与实践04 9/51 4.2 Modular Arithmetic ⚫ 给定任意正整数n和a，如果用a除以n，得到的商q 和余数r满足如下关系: a=qn + r 0≤r <n; q=⌊a/n」⌊x」表示小于等于x的最大 整数 Eg: 11=1x7 + 4, r=4; -11=(-2)x7 + 3, r=3
因子Divisors 15 如果a=mb,其中a,b,m为整数，则当b≠0时，即b能 整除a,或a除以b余数为0，bla.b是a的一个因子。24 的正因子有1,2,3,4,6,8,12和24。 以下关系成立 如果a1,则a=士1 如果ab,且bla,则a=±b 任何b≠0能整除0 如果blg,且blh,则对任何整数m和n有bl(mg+nh) Eg:b=7,g=14,h=63,m=3,n=2,714and763 求证：7(3x14+2x63) 证明：(3x14+2x63)=7(3x2+2x9) 显然，7(7(3x2+2x9) 如果a三0modn,则nla 2022/10/9 现代密码学理论与实践04 10/51
2022/10/9 现代密码学理论与实践04 10/51 因子 Divisors ⚫ 如果a=mb, 其中a, b, m为整数，则当b≠0时，即b能 整除a, 或a除以b余数为0, b|a. b是a的一个因子。24 的正因子有1, 2, 3, 4, 6, 8, 12和24。 ⚫ 以下关系成立 ⚫ 如果a|1, 则a=±1 ⚫ 如果a|b，且b|a, 则a=±b ⚫ 任何b≠0能整除0 ⚫ 如果b|g，且b|h, 则对任何整数m和n有b|(mg+nh) ⚫ Eg: b=7, g=14, h=63, m=3, n=2, 7|14 and 7|63 求证：7|(3x14 + 2x63) 证明：(3x14 + 2x63)=7(3x2 + 2x9) 显然, 7|(7(3x2 + 2x9)) ⚫ 如果a ≡ 0 mod n，则n|a
长 同余(congruence) 105 ● 给定整数a,b及n0,当且仅当a-b=kn时，a与b在模n 时同余，记为a=b mod n或a三nb EX:1757.17-7=2*5; 53=711.53-11=6*7 a三nb当且仅当a mod n=b mod n 如果a是整数，n是正整数，定义a除以n所得之余数为 a模n。对于任意整数a,我们总可写出：a=a/n」xn (a mod n) ●11m0d7=4; -11m0d7=3 ● 如果(a mod n)=(b mod n),则称整数a和b是模n同余， 表示为a=b mod n或a=nb 。73≡4mod23; 21≡-9m0d10 2022/10/9 现代密码学理论与实践04 11/51
2022/10/9 现代密码学理论与实践04 11/51 同余 (congruence) ⚫ 给定整数a, b及n≠0, 当且仅当a-b=kn时，a与b 在模n 时同余，记为 a≡b mod n 或 a≡nb Ex: 17≡57 ∵17-7=2*5; 53≡711 ∵53-11=6*7 a≡nb 当且仅当 a mod n = b mod n ⚫ 如果a是整数，n是正整数，定义a除以n所得之余数为 a模n。对于任意整数a，我们总可写出： a =⌊a/n」x n + (a mod n) ⚫ 11 mod 7 = 4; -11 mod 7 = 3 ⚫ 如果(a mod n)=(b mod n), 则称整数a和b是模n同余， 表示为a≡b mod n 或 a≡nb ⚫ 73 ≡ 4 mod 23； 21 ≡ -9 mod 10