本章要点 域是一些元素的集合,其上定义了两个算术运算(加 法和乘法),具有常规算术性质,如封闭性、结合律、 交换律、分配律、加法逆和乘法逆等。 模算术是一种整数算术,它将所有整数约减为一个固 定的集合[0,1,…,n-1],门为某个整数。任何这个集 合外的整数通过除以m取余的方式约减到这个范围内。 两个整数的最大公因子是可以整除这两个整数的最大 正整数。 个有限域就是有有限个元素的域。可以证明有限域 的阶(元素个数)一定可以写作素数的幂形式p,n为 个整数,p为素数 阶为p的有限域可以由模p的算术来定义。 阶为p,m>1的有限域可由多项式算术来定义。 Cloot a answer sclence /eclvacoce 都 mfy@ustc.edu.cn 现代密码学理论与实践 2/55
mfy@ustc.edu.cn 现代密码学理论与实践 2/55 域是一些元素的集合，其上定义了两个算术运算(加 法和乘法)，具有常规算术性质，如封闭性、结合律、 交换律、分配律、加法逆和乘法逆等。 模算术是一种整数算术，它将所有整数约减为一个固 定的集合[0,1,…,n-1]，n为某个整数。任何这个集 合外的整数通过除以n取余的方式约减到这个范围内。 两个整数的最大公因子是可以整除这两个整数的最大 正整数。 一个有限域就是有有限个元素的域。可以证明有限域 的阶(元素个数)一定可以写作素数的幂形式pn ，n为 一个整数，p为素数。 阶为p的有限域可以由模p的算术来定义。 阶为pn ，n>1的有限域可由多项式算术来定义
本章目录 4.1群,环和域 42模算术 43欧几里得算法 44有限域GF(P 45多项式运算 4.6有限域GF(2N 都 mfy@ustc.edu.cn 现代密码学理论与实践 3/55
mfy@ustc.edu.cn 现代密码学理论与实践 3/55 4.1群, 环和域 4.2 模算术 4.3 欧几里得算法 4.4 有限域GF(p) 4.5 多项式运算 4.6 有限域GF(2n)
41群,环和域 GROUPS,RINGS,, AND FIEI的③ 群G,记作{G,%,定义一个二元运算的集合,G中 每一个序偶(a,b)通过运算生成G中元素(ab),满 足下列公理: (A1)封闭性 Closure:如果a和b都属于G,则ab也属于G 0(A2)结合律 Associative:对于G中任意元素a,b,C,都 有abC)=(ab)c成立 (A3)单位元 Identity element:G中存在一个元素e,对 于G中任意元素a,都有a·e=ea=a成立 (A4)逆元 nverse element:对于G中任意元素a,G中都 存在一个元素a’,使得aa’=a'a=e成立 neuter sciences echvalac 都 mfy@ustc.edu.cn 现代密码学理论与实践 4/55
mfy@ustc.edu.cn 现代密码学理论与实践 4/55 群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成立
群、有限群和无限群 用Nn表示n个不同符号的集合,{1,2,,n}.n个不同符号的 个置换是一个Nn到N的一一映射。定义Sn为n个不同符号的所 有置换组成的集合。Sn中的每一个元素都代表集合{1,2,…,n 的一个置换,容易验证Sn是一个群: A1:如果π,p∈Sn,则合成映射π"p根据置换m来改变p中元素的次 序而形成,如,{3,2,1y{1,3,2}={2,3,1},显然Tp∈Sn A2:映射的合成显而易见满足结合律 °A3:恒等映射就是不改变n个元素位置的置换,对于Sn,单位元是 {1,2,,n} °A4:对于任意π∈Sn,抵消由π定义置换的映射就是π的逆元,这 个逆元总是存在,例如:{2,3,1}3,1,2}={1,2,3}, 有限群 Finite group和无限群 INfinite Group:如果一个群的 元素是有限的,则该群称为有限群,且群的阶等于群中元素的 个数;否则称为无限群 皿 都 mfy@ustc.edu.cn 现代密码学理论与实践 5/55
mfy@ustc.edu.cn 现代密码学理论与实践 5/55 用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：如果一个群的 元素是有限的，则该群称为有限群，且群的阶等于群中元素的 个数；否则称为无限群
交换群和循环群 丶交换群 Abelian group:还满足以下条件的群称为 交换群(又称阿贝尔群) (A5)交换律 commutative:对于G中任意的元素a,b, 都有a·b=ba成立 当群中的运算符是加法时,其单位元是0;a的逆元 是-a,并且减法用以下的规则定义: b=a+(-b) 循环群Cyc| ic Group 如果群中的每一个元素都是一个固定的元素a(a∈G的 幂a(k为整数),则称群G为循环群。元素a生成了群G, 或者说a是群G的生成元。 apure s cetacea /ecvacoge 都 mfy@ustc.edu.cn 现代密码学理论与实践 6/55
mfy@ustc.edu.cn 现代密码学理论与实践 6/55 交换群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) 环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 o(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=0or b=0. 满足M4的是交换环;满足M5和M6的交换环是整环 claat ay Camerer sclence /echvocage mfy@ustc.edu.cn 现代密码学理论与实践 7/55
mfy@ustc.edu.cn 现代密码学理论与实践 7/55 环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) 域F,可以记为{,+,X},是有加法和乘法的两个二 元运算的元素的集合,对于F中的任意元素a,b,C, 满足以下公理: (A1-M6),F是一个整环 (M7),乘法逆元,对于F中的任意元素a(除0以外),F中都存 在一个元素a,使得a1=( a-1)a=1. 。域就是一个集合,在其上进行加减乘除而不脱离该集合, 除法按以下规则定义:a/b=a(b-1 有理数集合,实数集合和复数集合都是域;整数集合 不是域,因为除了1和-1有乘法逆元,其他元素都无 乘法逆元 都 mfy@ustc.edu.cn 现代密码学理论与实践 8/55
mfy@ustc.edu.cn 现代密码学理论与实践 8/55 域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有乘法逆元，其他元素都无 乘法逆元
群、环和域的关系 (Al)Closure under addition If a and b belong to s, then a+ b is also in (A2) Associativity of ad a+(6+c)=(a+b)+cfor all a, b, c in S (A3)Additive identity There is an element o in r such that a+0=0+a=a for all a in s (A4)Additive inverse For each a in s there is an element-a in s such that a+(a)=(a)+a=0 AcE a+b=b+a for all a b in s (MI)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, cin s (a +b)c= ac bc for all a, b, c in s (M4) Commutativity of multiplication: ab= ba for all a, b in S (MS) Multiplicative identity There is an element 1 in S such that a1=la= a for all a in s (M6) No zero divisors If a. b in s and ab=0 then either a=or b=0 (MT) Multiplicative inverse If a belongs to s and a 0, there is an element al in S such that acl=ala=1 Figure 4.1 Group, Ring, and Field mfy@ustc.edu.cn 现代密码学理论与实践 9/55
mfy@ustc.edu.cn 现代密码学理论与实践 9/55
4.2 MODULAR ARITHMETIC 给定任意正整数n和a,如果用a除以n,得到的商q 和余数r满足如下关系 a=qn+r0≤r<n;q=□a/n」□」表示小于等于x 的最大整数。给定a和η时,q和r即唯一确定。(证明) g l=1X7+4,r=4 11=(-2)x7+3 r=3 3 a(q+I)n 012 Figure 4.2 The Relationship a= qn+r; Osr<n mfy@ustc.edu.cn 现代密码学理论与实践 10/55
mfy@ustc.edu.cn 现代密码学理论与实践 10/55 给定任意正整数n和a，如果用a除以n，得到的商q 和余数r满足如下关系: a=qn + r 0≤r <n; q=⌊a/n」⌊x」表示小于等于x 的最大整数。 给定a和n时，q和r即唯一确定。 （证明） Eg: 11=1x7 + 4, r=4; -11=(-2)x7 + 3, r=3
因子( 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=± 如果a|b,且b|a,则a=±b 任何b≠0能整除0 0如果b|g,且bh,则对任何整数m和n有bmg+nh) 例:b=7,g=14,h=63,m=3,n=2,714and 7|63 求证:7(3×14+2×63) 证明:(3×14+2X63)=7(3X2+2X9) 显然 如果a 0n7(7(3X2+2x9) modn,则na皿 都 mfy@ustc.edu.cn 现代密码学理论与实践 11/55
mfy@ustc.edu.cn 现代密码学理论与实践 11/55 如果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) 例: 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