《信息安全数学基础_群的基本概念》由会员分享，可在线阅读，更多相关《信息安全数学基础_群的基本概念（50页珍藏版）》请在金锄头文库上搜索。
1、信息安全数学基础 -群计算机科学与技术系 王常远139806881271847809482021/6/161群n一般来说，一个代数结构是指一个非空集合S以及定义在S上的二元运算的总体，要求二元运算满足一定的条件。2021/6/162定义 群的定义 .2021/6/163注意：2021/6/164n有限群和无限群：n如果集合 G 中的元素个数有限，就称群G为 有限群；否则称为无限群。2021/6/165n阿贝尔群n阿贝尔群又称交换群（commutative group)，本章中出现的所有群都是指交换群。2021/6/1662021/6/167举例n下面，我们给出群的一些具体例子。2021/6/1
2、68群的例子（1）n整数集 Z 在加法下构成群，记为(Z, +). (Z, +)是一个无限群、阿贝尔群。 有理数集Q、实数集R和复数集C关于加法都形成无限群。单位元，逆元素的定义与整数加法群相同。2021/6/169群的例子（2）nQ、R 和 C中的非零元素在乘法下构成群。将这些群分别记为Q*、R*和C*。 这三个群的完整表示是(Q*, , (R*, , (C*, 。 将这些群称为乘法群。2021/6/1610群的例子（3）n对任意自然数 n , 整数模 n 集合构成一个包含 n 个元素的有限加法群，这里的加法运算是模 n 加，将这个群记为Zn 。 这个群的完整表示为（Zn，+(mod n)）
3、. 注意: Zn 是 Z/nZ的简化表示。2021/6/1611群的例子（4）n时钟上表示小时的数字在模12加法下构成群Z12 , 将（ Z12 , +(mod 12)称为时钟群。2021/6/1612群的例子（5）nZn=0, 1, 2, , (n-1) Zn中所有与 n 互素的的元素是Zn的一个子 集, 这个子集按照模 n 乘法运算构成一个群，用Zn*表示。 例如， (Z15*, (mod15) ) = (1, 2, 4, 7, 8, 11, 13, 14, (mod15) ) 2021/6/1613群的例子（6）n集合B=0,1，在异或运算下形成群。2021/6/1614群的例子（7）n
4、x3 -1=0的根在乘法运算下构成一个有限群。 x =1是方程的一个解，该方程有三个根。 用u和v表示其它两个根。由于 x3 -1=(x-1)(x2 + x + 1) 则u和v是 x2 + x + 1=0的两个根。 由二次方程根与系数的关系， u和v互逆。 封闭性: (x2)3 1 =0 。2021/6/1615群的例子(8)n置换群 S=1,2,n Sn是S上所有置换构成的集合 | Sn |=n! , 是Sn中置换, 表示和的复合, 即(x)=(x) Sn构成群, 称为n阶对称群对称群.2021/6/1616n置换的表示 = = = 2021/6/1617 (1234)(56) = = (1
5、32) (1432) = (1423) 2021/6/1618重复群运算的简化表示2021/6/16192021/6/1620群的性质2021/6/1621子群2021/6/1622子群n对于群 G 的一个非空子集H，要判别H是否是G的子群，需要验证4条：n封闭性n结合律（不必验证）n单位元n逆元素2021/6/1623子群的例子（1）n在加法运算下，Z Q R C.n注意，在这个例子中：n子群中的单位元和群中的单位元相同，都是0n子群中元素的逆元素和群中该元素的逆元素一致2021/6/1624子群的例子（2）n全体偶数的集合（包括0），在加法运算下，是整数加法群的一个子群。因此也是 （1）中
6、所有群的子群。2021/6/1625子群的例子（3）n在乘法运算下， Q* R* C*。 2021/6/1626子群的例子（4）2021/6/1627子群的例子（5）nB=0,1在异或运算下是一个群。n0是B的一个真子群n1不是B的子群2021/6/1628子群的例子（6）n设G是一个群，e是它的单位元ne和G是群G的两个平凡子群。2021/6/1629群的阶n有限群G中元素的个数称为G的阶，记为#G.n#Zn = nnB=0,1按照异或运算，#B = 2n#Roots (x3-1) = 32021/6/1630子群中的单位元n在我们给出的例子中，子群的单位元就是包含它的群的单位元！n事实上，
7、对任意子群都有这样的结论成立： 证明: 设H是G的一个子群，H中的单位元为eH，G 中的单位元为eG。那么，在H中，有eH 。eH = eH； 在G中，有eH 。eG = eH。从而可得到eH = eG。2021/6/1631子群中的逆元素n由于eH = eG，因此子群H中元素的逆元正是它在G中的逆元。2021/6/1632子群的判别 (1)n子群的判别方法：2021/6/16332021/6/1634子群的判别(2)n设H是群G的一个非空子集, H是G的子群的充要条件是对任意的元素x, y H, 有xy-1 H.2021/6/1635子群的判别 (3)n当 H 是一个有限集合时，判别会变得容
8、易些，只需满足封闭性即可：2021/6/1636拉格朗日定理n陪集陪集（Coset）的定义2021/6/1637n拉格朗日定理：2021/6/1638商群的概念n注: n此处，首先应说明商群上的运算是一个二元运算。n实际上，商群上的运算可以看作集合之间的乘法运算，因为：2021/6/1639商群的例子(1)n 设 n0 是一个整数，在加法运算下，集合 nZ=0, n, -n, 2n, -2n,是Z的一个子群， 那么商群 Z/nZ=x+nZ | x为任一整数 有n个元素，即 Z/nZ=0+nZ,1+nZ,n-1+nZ 可以看出Z/nZ=Zn 事实上，Z/nZ是Zn的正式和标准记法，为了表达的方便
9、， 用Zn代替Z/nZ。2021/6/1640商群的阶2021/6/1641商群的例子(2)2021/6/1642群元素的阶n注：注：当一个元素当一个元素g的阶的阶ord(g)有限时，如果有有限时，如果有gn =e成立，则必有成立，则必有ord(g)|n，即，即n一定是一定是ord(g)的倍数的倍数。2021/6/1643例子（1）n在时钟群Z12中：n12是满足112=0 (mod 12)的最小正整数，所有ord(1)=12；n类似地，ord(2)=6，ord(3)=4，ord(4)=3， ord（5）=12。2021/6/1644例子（2）n0, 1关于异或运算形成一个群，ord(0)=1, ord(1)=2.2021/6/1645例子（3）n在群Roots(x3-1)中，ord(u)=ord(v)=3，ord(1)=1.2021/6/1646例子（4）n在Z中，ord(1)= 。2021/6/1647推论 （拉格朗日）2021/6/1648n推论提供了群的阶和群中元素的阶之间的关系。n欧拉定理和费马小定理可以直接由推论得到：v欧拉函数：n欧拉定理：欧拉定理：n费马小定理：费马小定理：2021/6/1649 结束语结束语若有不当之处，请指正，谢谢！若有不当之处，请指正，谢谢！
