信息安全数学 群

电子科技大学计算机科学与工程学院UESTCPress第二章群信息安全数学基础许春香编著电子科技大学计算机科学与工程学院UESTCPress第二章群第二章群电子科技大学计算机科学与工程学院UESTCPress第二章群第二章群•2.1群的定义（重要）•2.2子群（掌握）•2.３同构和同态（重要）•2.４变换群与置换群（掌握）电子科技大学计算机科学与工程学院UESTCPress第二章群2.1群的定义定义2.1.1设G是一非空集合．如果在G上定义了一个代数运算，称为乘法，记为ab，而且这个运算满足下列条件，那么G称为一个群：1）G对于乘法是封闭，即对于G中任意元素a，b，有abG；2）对于G中任意元素a，b，c，有a(bc)=(ab)c；3）在G中有一个元素e，对于G中任意元素a，有ea=a；4）对于G中任一元素a都存在G中的一个元素b，使ba=e．电子科技大学计算机科学与工程学院UESTCPress第二章群群的定义群的定义可以简单的归结为带有运算的集合，在集合上的运算满足1）封闭性；2）结合性；3）单位元；4）逆元；电子科技大学计算机科学与工程学院UESTCPress第二章群群的定义例2.1.1整数对于加法构成了整数加法群，由我们初等代数的知识知，任意两个整数相加仍然是整数（封闭性），且满足加法结合性，其单位元为0，即任意整数加0均为自身，任意整数a的逆元为-a全体整数Z，全体实数R，全体复数C对于加法是群全体非零实数R*=R\{0}对于乘法是群同样有非零有理数，非零复数对乘法也构成了群分别记作（Z，+），（Q，+）（R，+），（C，+）（Q*，·）（R*，·）（C*，·）其中Q*表示非零有理数集，R*表示非零实数，C*非零复数这类群称为数群电子科技大学计算机科学与工程学院UESTCPress第二章群群的定义关于群的几点说明：1.群的定义有多种描述可以参考近世代数书籍，本定义2.1.1只给出了一种2.定义中的“乘法”并不代表具体的乘法，而是抽象的乘法——代表一种代数运算群的定义补充电子科技大学计算机科学与工程学院UESTCPress第二章群群的定义例2.1.2自然数集合N＝{1，2，3，．．．}对于通常的加法封闭且满足结合律，但不存在左单位元和左逆元，因此对于加法不是群．而只是半群整数Z对乘法也只是半群，即只满足封闭性和结合性电子科技大学计算机科学与工程学院UESTCPress第二章群群的定义例2.1.3集合{0，1}对于模2加法“”（或称异或）是一个群．显然封闭性和结合律满足；这里的单位元e=0，因为00＝0，01＝1；每一个元素的左逆元就是它自己：00＝0，11＝0．{0，1}对于运算是加法群．电子科技大学计算机科学与工程学院UESTCPress第二章群群的定义例2.1.4集合的元素不一定是数，我们举一个集合元素为二阶方阵的例子：该集合对于矩阵的普通乘法是一个群，单位元是100110101010,,,01010101电子科技大学计算机科学与工程学院UESTCPress第二章群群的定义例2.1.5考虑二阶矩阵集合，其中a，b，c，d为整数，，则该集合对于普通矩阵乘法构成群：1）封闭性：两个矩阵A和B相乘仍然是整数二阶矩阵，而且|AB|＝|A||B|=1；2）结合律显然满足；3）单位矩阵是单位元；4）任意元素的左逆元为．实际上任意阶整数方阵当其行列式等于±1时对于矩阵的普通乘法都构成群。集合元素可以是任意事物，其中的运算也可以是任意定义的．1001abcddbcaabcd1abcd电子科技大学计算机科学与工程学院UESTCPress第二章群群的定义定义2.1.2如果群中的运算满足交换律，则这个群称为交换群或阿贝尔（Abel）群比如：（Z，+），（Q，+）（R，+），（C，+），（Q*，·）（R*，·）（C*，·）都是（Abel）群电子科技大学计算机科学与工程学院UESTCPress第二章群群的基本性质1）左逆元同时也是右逆元，即对于a，bG，如果ba=e，则ab=e．2）左单位元同时也是右单位元，即如果对于所有aG有ea=a，则对于所有aG也有ae=a．3）单位元是唯一的．4）逆元是唯一的．电子科技大学计算机科学与工程学院UESTCPress第二章群群的基本性质（证明）证明设G是一个群，e是G中的左单位元．1）aG，设其左逆元为b，即ba=e；又设b的左逆元为b’，即b’b=e．于是(b’b)(ab)=e(ab)=(ea)b=ab；但我们又有(b’b)(ab)＝b’[(ba)b]=b’(eb)=b’b=e，所以我们得到ab=e，即b也是a的右逆元．左逆元同时也是右逆元电子科技大学计算机科学与工程学院UESTCPress第二章群群的基本性质（证明）证明设G是一个群，e是G中的左单位元．2）aG，设其左（右）逆元为b．则(ab)a=ea=a；又(ab)a=a(ba)=ae；所以ae=a，故左单位元也是右单位元．左单位元同时也是右单位元电子科技大学计算机科学与工程学院UESTCPress第二章群群的基本性质（证明）证明设G是一个群，e是G中的左单位元．3）如果G中存在另一单位元e’，我们有e=ee’=e’，则单位元是唯一的单位元是唯一的电子科技大学计算机科学与工程学院UESTCPress第二章群群的基本性质（证明）证明设G是一个群，e是G中的左单位元．4）aG，设b，c都是a的逆元，则b=be=b(ac)=(ba)c=ec=c，则每个元素的逆元是唯一的．逆元是唯一的电子科技大学计算机科学与工程学院UESTCPress第二章群群的阶、元素的阶定义2.1.3如果一个群G中元素的个数是无限多个，则称G是无限群；如果G中的元素个数是有限多个，则称G是有限群，G中元素的个数称为群的阶，记为|G|．如前面例2.1.1提到的数群是无限群，例2.1.3的模2加法群，阶为2，例2.1.4的群阶为4电子科技大学计算机科学与工程学院UESTCPress第二章群群的阶、元素的幂由于群里结合律是满足的，所以元素连乘a1a2…an有意义，它也是G中的一个元．我们把a的n次连乘记为an，称为a的n次幂（或称乘方），即．我们还将a的逆元a1的n次幂记为an，即群的逆元（a1）1=annaaaa111nnaaaa电子科技大学计算机科学与工程学院UESTCPress第二章群群的阶、元素的幂若ab=ba，则（ab）n=anbn另外：anan=e，aman=am+n，(an)m=anm电子科技大学计算机科学与工程学院UESTCPress第二章群群的等价性质定理2.1.1一个群的乘法满足消去律：如果ax=ax’，则x=x’；（左消去）如果ya=y’a，则y=y’．（右消去）证明假定ax=ax’，那么a1(ax)=a1(ax’)，(a1a)x=(a1a)x’，ex=ex’，x=x’．同理可证由ya=y’a，得y=y’．电子科技大学计算机科学与工程学院UESTCPress第二章群群的等价性质定理2.1.2如果G是一个群，a，bG，方程ax=b，ya=b有解；反之，如果上述方程在非空集合G中有解，而且其中的运算封闭且满足结合律（即半群），则G是一个群．电子科技大学计算机科学与工程学院UESTCPress第二章群群的等价性质证明先证方程有解如果G是一个群，对于任一元素a有逆元a-1，由ax=b可得a1(ax)＝a1b，x=a1b∈G于是x=a1b是方程ax=b的解．同理y=ba1是方程ya=b的解．电子科技大学计算机科学与工程学院UESTCPress第二章群群的等价性质证明（续）：对于方程有解时，半群（G，·）是群。先证有左单位元：如果a，b，方程ax=b，ya=b在G中有解，则假设a=b时，方程亦有解，即ya=a有解，设其解为e。任取g∈G，方程ax=g有解，设其解为b，即ab=g，于是有eg=eab=ab=g，因而e是左单位元。再证任a∈G有左逆元：因为方程ya=e有解，其解就是a的左逆元。综上，由定义2.1.1知，G对于运算“·”在满足封闭性结合性前提下，只要方程ax=b，ya=b有解，G关于运算“·”是群电子科技大学计算机科学与工程学院UESTCPress第二章群群的等价性质推论2.1.2.1如果一个非空集合G中的运算封闭且满足结合律，则它是一个群的充分必要条件是a，bG，方程ax=b，ya=b有解．电子科技大学计算机科学与工程学院UESTCPress第二章群群的等价性质定理2.1.3如果一个非空有限集合G中的运算封闭且满足结合律，则它是一个群的充分必要条件是满足消去律．证明必要条件由定理1立即得到．只证明充分条件．如果消去律满足，则a，bG，方程ax=b，ya=b有解．先证明方程ax=b在G中有解．假设G有n个元素，G={a1，a2，a3，，an}．用a左乘G中的每个元素得到G’={aa1，aa2，aa3，，aan}，电子科技大学计算机科学与工程学院UESTCPress第二章群群的等价性质证明（续）由于乘法的封闭性，G’是G的子集，而且G’中的n个元素两两不同，不然假设aai＝aaj，其中ij，由消去律得ai＝aj，其中ij，这是不可能的．于是G’也有n个两两不同的元素，则G’=G．设b=aak，则ak就是以上方程的解．同样可证ya=b有解．由定理2.1.2，G是一个群．定理证毕．电子科技大学计算机科学与工程学院UESTCPress第二章群2.2子群定义2.2.1一个群G的一个子集H如果对于G的乘法构成一个群，则称为G的子群也记作H≤G．一个群G至少有两个子群：G本身；只包含单位元的子集{e}，它们称为G的平凡子群，其他子群成为真子群(H＜G)．电子科技大学计算机科学与工程学院UESTCPress第二章群2.2子群例2.2.1设m是一个正整数．整数加群Z中每个元素的m倍数{0，m，2m，3m，…}对加法也构成群，它是Z的子群，记为mZ．电子科技大学计算机科学与工程学院UESTCPress第二章群2.2子群引理一个群G和它的一个子群H有：1）G的单位元和H的单位元是同一的；2）如果aH，a1是a在G中的逆元，则a1H．证明对于任意aH，有aG．1）反证法．设G的单位元为e，H的单位元为e’，而且ee’．由于e’HG，则G中的单位元不唯一，与群的定义矛盾，故e=e’．2）反证法．对于任意aH，假设a1H，则a在H中存在另一逆元a’，由于a’G，则a在G中存在两个逆元，得到矛盾，故a1H．电子科技大学计算机科学与工程学院UESTCPress第二章群2.2子群定理2.2.1一个群G的一个非空子集H构成一个子群的充分必要条件是：1）a，bH，有abH；2）aH，有a1H．证明首先证明充分条件．由于1），H是封闭的．结合律在G中，在H中自然成立．现证明H中有单位元．对于任意aH，由于aG，所以存在a1使a1a=e．由2）有a1H，由1）就有a1aH，于是a1a=eH，则G中的单位元在H中．H不可能再有单位元，否则G的单位元不唯一．由2），H中的每个元素都有逆元．故H是一个群．再证明必要条件．1）是封闭性，是必要的．2）由引理也是必要的．证毕．电子科技大学计算机科学与工程学院UESTCPress第二章群2.2子群定理2.2.2一个群G的一个非空子集H构成一个子群的充分必要条件是：对于任意a，bH，有ab1H．证明我们证明这个条件和定理2.2.1的两个条件是一致的，即和定理2.2.1等价．先证明由定理1的两个条件可推出这个条件．a，bH，有b1H，则ab1H．反过来，这个条件可推出定理1的两个条件．由aH，有aa1=eH，于是ea1=a1H．又由a，bH，（参照上一行，）有b1H，于是a(b1)1=abH．证毕．在判定子群时，此定理