本章要点 ● 域是一些元素的集合，其上定义了两个算术运算（加 法和乘法)，具有常规算术性质，如封闭性、结合律、 交换律、分配律、加法逆和乘法逆等。 ● 模算术是一种整数算术，它将所有整数约减为一个固 定的集合[0,1，.，n-1],n为某个整数。任何这个集合 外的整数通过除以取余的方式约减到这个范围内。 ● 两个整数的最大公因子是可以整除这两个整数的最大 正整数。 一 个有限域就是有有限个元素的域。可以证明有限域 的阶（元素个数）一定可以写作素数的幂形式p”,n为一 个整数，p为素数。 阶为p的有限域可以由模p的算术来定义。 ·阶为p”,n>1的有限域可由多项式算术来定义 2022/10/9 现代密码学理论与实践04 2/51
2022/10/9 现代密码学理论与实践04 2/51 本章要点 ⚫ 域是一些元素的集合，其上定义了两个算术运算(加 法和乘法)，具有常规算术性质，如封闭性、结合律、 交换律、分配律、加法逆和乘法逆等。 ⚫ 模算术是一种整数算术，它将所有整数约减为一个固 定的集合[0,1,…,n-1]，n为某个整数。任何这个集合 外的整数通过除以n取余的方式约减到这个范围内。 ⚫ 两个整数的最大公因子是可以整除这两个整数的最大 正整数。 ⚫ 一个有限域就是有有限个元素的域。可以证明有限域 的阶(元素个数)一定可以写作素数的幂形式p n ，n为一 个整数，p为素数。 ⚫ 阶为p的有限域可以由模p的算术来定义。 ⚫ 阶为p n ，n>1的有限域可由多项式算术来定义
4.I群，环和域GROUPS,RINGS,AND FIELDS ● 群G,记作{G,},定义一个二元运算的集合，G中 每一个序偶(a,b)通过运算生成G中元素(ab),满 足下列公理： ● (A1)封闭性Closure:如果a和b都属于G,则ab也属于G. (A2)结合律Associative:对于G中任意元素a,b,c,都有 a(bc)=(ab)c成立 (A3)单位元Identity element:G中存在一个元素e,对于 G中任意元素a,都有ae=ea=a成立 (A4)逆元Inverse element:对于G中任意元素a,G中都存 在一个元素a',使得aa'=a'a=e成立 2022/10/9 现代密码学理论与实践04 3/51
2022/10/9 现代密码学理论与实践04 3/51 4.1群, 环和域Groups, Rings, and Fields ⚫ 群G, 记作{G, •}, 定义一个二元运算•的集合，G中 每一个序偶(a, b)通过运算生成G中元素(a•b)，满 足下列公理： ⚫ (A1) 封闭性Closure: 如果a和b都属于G, 则a•b也属于G. ⚫ (A2) 结合律Associative: 对于G中任意元素a, b, c，都有 a•(b•c)=(a•b)•c成立 ⚫ (A3) 单位元Identity element: G中存在一个元素e，对于 G中任意元素a，都有a•e=e•a=a成立 ⚫ (A4) 逆元Inverse element: 对于G中任意元素a, G中都存 在一个元素a’，使得a•a’=a’•a=e成立
群、有限群和无限群 15 用Nn表示n个不同符号的集合，{1,2，.，n}.n个不同符号的一个 置换是一个N到Nn的一一映射。定义Sn为n个不同符号的所有 置换组成的集合。S中的每一个元素都代表集合{1,2，…，n}的一 个置换，容易验证S是一个群： A1:如果n,p∈Sn,则合成映射mp根据置换m来改变p中元素的 次序而形成，如，{3,2,1}{1,3,2}={2,3,1}，显然p∈Sn A2:映射的合成显而易见满足结合律 A3:恒等映射就是不改变个元素位置的置换，对于Sn,单位元 是{1,2，.，n} A4:对于任意T∈Sn,抵消由m定义置换的映射就是m的逆元， 这个逆元总是存在，例如：{2,3,1}3,1,2={1,2,3}， 有限群Finite Group:和无限群Infinite Group:如果一个群的元 素是有限的，则该群称为有限群，且群的阶等于群中元素的个 数否则称为无限群 2022/10/9 现代密码学理论与实践04 4/51
2022/10/9 现代密码学理论与实践04 4/51 群、有限群和无限群 ⚫ 用Nn表示n个不同符号的集合，{1,2,…,n}. n个不同符号的一个 置换是一个Nn到Nn的一一映射。定义Sn为n个不同符号的所有 置换组成的集合。Sn中的每一个元素都代表集合{1,2,…,n}的一 个置换，容易验证Sn是一个群： ⚫ A1：如果π,ρ∈Sn，则合成映射π•ρ根据置换π来改变ρ中元素的 次序而形成，如，{3,2,1}•{1,3,2}={2,3,1},显然π•ρ ∈Sn ⚫ A2：映射的合成显而易见满足结合律 ⚫ A3：恒等映射就是不改变n个元素位置的置换，对于Sn，单位元 是{1,2,…,n} ⚫ A4：对于任意π∈Sn，抵消由π定义置换的映射就是π的逆元， 这个逆元总是存在，例如： {2,3,1}•{3,1,2}={1,2,3}, ⚫ 有限群Finite Group和无限群Infinite Group：如果一个群的元 素是有限的，则该群称为有限群，且群的阶等于群中元素的个 数；否则称为无限群
交换群和循环群 15 交换群Abelian Group:还满足以下条件的群称为交 换群（又称阿贝尔群） (A5)交换律Commutative:对于G中任意的元素a,b, 都有ab=ba成立 当群中的运算符是加法时，其单位元是0；a的逆元 是-a,并且减法用以下的规则定义： a-b=a+(-b) 01 循环群Cyclic Group 如果群中的每一个元素都是一个固定的元素a(a∈G)的 幂ak(k为整数)，则称群G为循环群。元素a生成了群G, 或者说a是群G的生成元。 2022/10/9 现代密码学理论与实践04 5/51
2022/10/9 现代密码学理论与实践04 5/51 交换群和循环群 ⚫ 交换群Abelian Group：还满足以下条件的群称为交 换群(又称阿贝尔群) ⚫ (A5) 交换律Commutative ：对于G中任意的元素a, b， 都有a•b=b•a成立 ⚫ 当群中的运算符是加法时，其单位元是0；a的逆元 是-a, 并且减法用以下的规则定义： a – b = a + (-b) ⚫ 循环群Cyclic Group ⚫ 如果群中的每一个元素都是一个固定的元素a (a ∈G)的 幂a k (k为整数)，则称群G为循环群。元素a生成了群G， 或者说a是群G的生成元
环(Rings) 15 环R,由R,+,表示，是具有加法和乘法两个二元 运算的元素的集合，对于环中的所有a,b,c,都服 从以下公理： (A1-A5),单位元是0，a的逆是-a. (M1),乘法封闭性，如果a和b属于R,则ab也属于R (M2),乘法结合律，对于R中任意a,b,c有a(bc)=(ab)c. (M3),乘法分配律，a(b+c)=ab+acor(a+b)c-ac+bc (M4),乘法交换律，ab=ba,交换环 (M5),乘法单位元，R中存在元素1使得所有a有a1=1a. (M6),无零因子，如果R中有a,b且ab=0,则a=0orb=0 满足M4的是交换环；满足M5和M6的交换环是整环 2022/10/9 现代密码学理论与实践04 6/51
2022/10/9 现代密码学理论与实践04 6/51 环 (Rings) ⚫ 环R, 由{R, +, x}表示, 是具有加法和乘法两个二元 运算的元素的集合，对于环中的所有a, b, c, 都服 从以下公理： ⚫ (A1-A5), 单位元是0，a的逆是 -a. ⚫ (M1), 乘法封闭性, 如果a和b属于R, 则ab也属于R ⚫ (M2), 乘法结合律,对于R中任意a, b, c有a(bc)=(ab)c. ⚫ (M3), 乘法分配律, a(b+c)=ab+ac or (a+b)c=ac+bc ⚫ (M4), 乘法交换律, ab=ba，交换环 ⚫ (M5), 乘法单位元, R中存在元素1使得所有a有 a1=1a. ⚫ (M6), 无零因子, 如果R中有a, b且ab=0, 则 a=0 or b=0. 满足M4的是交换环；满足M5和M6的交换环是整环
域(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