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