本章要点 域是一些元素的集合,其上定义了两个算术运算(加 法和乘法),具有常规算术性质,如封闭性、结合律、 交换律、分配律、加法逆和乘法逆等。 模算术是一种整数算术,它将所有整数约减为一个固 定的集合[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的生成元