信息安全数学基础——第九章 群的结构

大三上 期末复习

---

循环群

加群Z的每个子群H都是循环群，且$H=<0>$或$H=<m>=mZ$，其中m是H中的最小整数，如果$H\not =<0>$，则H是无限的。

每个无限循环群同构于加群Z。每个阶为m的有限循环群同构于加群Z/mZ

群G的子群$<a>$的阶称为元素a的阶，记为$ord(a)$

G是一个群，$a\in G$

• a为无限阶
  
  • 当且仅当$k=0$，$a^k=e$
  • 元素$a^k(k\in Z)$两两不同
• a是有限阶m>0
  
  • m是使得$a^m=e$的最小正整数
  • 当且仅当$m|k$，$a^k=e$
  • 当且仅当$r\equiv k\pmod m$，$a^r=a^k$
  • 元素$a^k(k\in Z/mZ)$两两不同
  • $<a>=\{a,a^2,\ldots ,a^{m-1},a^m=e\}$
  • 对任意整数$1\le d\le m$，有$ord(a^d)=\frac m{(d,m)}$

循环群的子群是循环群。

设G为循环群

• 如果G是无限的，则G的生成元为$a$和$a^{-1}$
• 如果G是有限阶m，则当且仅当(k,m)=1，$a^k$是G的生成元

有限群的生成元的构造

引理：

• 设G是有限交换群，对任意元素$a,b\in G$，若$(ord(a),ord(b))=1$，则
  
  • $ord(a\cdot b)=ord(a)\cdot ord(b)$
  • 存在$c\in G$，使得$ord(c)=[ord(a),ord(b)]$

设G是有限交换群，则G中存在元素$a_1,a_2,\ldots ,a_s$满足

$$ord(a_{i+1})|ord(a_i),1\le i\le s-1$$ 并且使得 $$G=<a_1,a_2,\ldots ,a_s>$$

---

有限交换生成群

基底

• 如果G是乘法交换群
  
  • $G=<X>$
  • X中任意不同的元素$x_1,x_2,\ldots ,x_k$乘性无关
• 如果G是加法交换群
  
  • $G=<X>$
  • X中任意不同的元素$x_1,x_2,\ldots ,x_k$线性无关

直积：$(H_1\cdots H_{i-1}H_{i+1}\cdots H_k)\cap H_i=\{e\},1\le i\le k$，记作$H_1\otimes \cdots \otimes H_k$
直和：$(H_1+\cdots +H_{i-1}+H_{i+1}+\cdots +H_k)\cap H_i=\{0\},1\le i\le k$，记作$H_1\oplus \cdots \oplus H_k$

设交换加群（或乘群）G有一组非空基底，则G是一组循环群的直和（或直积），G称为自由交换群

自由交换群的任意两个基底所含的元素个数相同，其基底元素的个数叫做G的秩

每个交换群都是一个秩为$|X|$的自由交换群的同态像子群，其中X为G的生成元集。

---

置换群

$\sigma$是S到自身的一一对应的映射，我们可以将其显示地表示为：

$$\sigma =\begin{pmatrix}a&b&c \\ \sigma(a)&\sigma(b)&\sigma(c) \\ \end{pmatrix}$$
所以
$$\sigma ^{-1} =\begin{pmatrix}\sigma(a)&\sigma(b)&\sigma(c) \\ a&b&c \\ \end{pmatrix}$$

n元置换全体组成的集合$S_n$对置换的乘法构成一个群，其阶是$n!$

k-轮换，建成轮换：使集合中的k个元素按照$i_1\rightarrow i_2\rightarrow\cdots \rightarrow i_k\rightarrow i_1$的方式进行转换，剩下的元素保持不变，k成为轮换的长度
恒等置换：k=1
对换：k=2

两个轮换$\sigma=(i_1,i_2,\ldots ,i_{k-1},i_k),\tau =(j_1,j_2,\ldots ,j_{l-1},j_l)$，如果$k+l$个元素都是不同的，则称这两个轮换不相交。

任意一个置换都可以表示为一些不相交轮换的乘积，在不考虑乘积次序的情况下，该表达式是唯一的。

n元排列$i_1,\ldots ,i_k,\ldots ,i_l,\ldots , i_n$的一对有序元素$(i_k,i_l)$，如果$k<l$时，$i_k>i_l$，则称$(i_k,i_l)$逆序，排列中逆序的个数叫做逆序数，记为$[i_1,\ldots , i_n]$

任意一个置换$\sigma$都可以表示为一些对换的乘积，且对换个数的奇偶性与排序的逆序数$[\sigma(1),\ldots,\sigma(n)]$的奇偶性相同

偶置换：一个置换$\sigma$可表示为偶数个对换的乘积
奇置换：一个置换$\sigma$可表示为奇数个对换的乘积