信息安全数学基础——第八章 群

大三上 期末复习

---

前置概念

设S是一个具有结合法的非空集合：

• 如果S满足结合律，则这样的集合可称为半群。
• S中的单位元e是唯一的

设S是一个有单位元的半群，则对S中的任意可逆元a，其逆元a'是唯一的。

群

• 运算封闭——即是一个具有结合法的非空集合
• 结合律
• 单位元
• 可逆元

当G的结合法写作乘法时，G叫做乘群；若是加法，则为加群。

阶：群G的元素个数，记为|G|。
有限群：群G的|G|为有限数。
无限群：群G的|G|为无限大
交换群：群G还满足交换律。

---

子群

H是群G的子群$\Leftrightarrow a,b\in H$，有$ab^{-1}\in H$

子群的生成

$\{H_i\}_{i\in I}$是G的包含X的所有子群，则$\bigcap_{i\in I}H_i$叫做有X生成的子群，记作$\langle X\rangle$，X称为其生成元。

有限生成：如果$G=\langle a_1,\ldots , a_n\rangle$，则称G为有限生成的
由a生成的循环群：如果$G=\langle a\rangle$，则称G为a生成的循环群。

由有限个元素生成的群：
设G是交换群，$X=\langle a_1,\ldots , a_t\rangle$是G的子集

• G为乘法群： $$\langle X \rangle = \{a_1^{n_1}\cdots a_t^{n_t}|a_i\in X,n_i\in Z,1\le i\le t\}$$
• G为加法群： $$\langle X \rangle = \{n_1a_1+\cdots + n_ta_t|a_i\in X,n_i\in Z,1\le i\le t\}$$

若$X=\langle a\rangle$

• G为乘法群：$\langle X\rangle =\{a^n|n\in Z\}$
• G为加法群：$\langle X\rangle =\{na|n\in Z\}$

证明2个集合相等的方法：若要证集合A=集合B，可先证$A\subseteq B$，再证$B\subseteq A$

正规子群和商集

左陪集：$aH=\{ah|h\in H\}$，右陪集：$Ha=\{ha|h\in H\}$
代表元：aH或者Ha中的元素
陪集：aH=Ha

$G=\bigcup_{i\in I}a_iH$——不相交左陪集（或右陪集）的并集构成群G
$|G|=\sum_{i\in I}|a_iH|$

商集：$G/H = \{aH|a\in G\}=\{a_iH|i\in I\}$
H在G中的指标：$[G:H]$——即商集的元素个数

一些定理：
H是G的子群，K是G的子群，也是H的子群

• $|G|=[G:H]|H|$
• $[G:K]=[G:H][H:K]$

拉格朗日定理：|H|是|G|的因数

考虑2个子群的情况：
H，K是G的子群，则

• $|HK|=|H||K|/|H\cap K|$
• $[H:H\cap K]\le [G:K]$，如果$[G:K]$是有限的，则当且仅当$G=KH$时，等号成立
• 若H，K都是有限指标子群，则$[G:H\cap K]$有限，且$[G:H\cap K]\le [G:H][G:K]$，当且仅当$G=HK$时，等号成立

正规子群
N为G的正规子群，则对任意$a\in G$满足以下等价条件

• $aN=Na$
• $aNa^{-1}=N$
• $aNa^{-1}\subset N$，$aNa^{-1}=\{ana^{-1}|n\in N\}$

商群

H是正规子群，则满足结合法$(aN)(bN)=(ab)N$的G/H称作群G对于正规子群H的商群。

---

同态和同构

同态：f是G到G'的一个映射，对任意的$a,b\in G$，都有$f(ab)=f(a)f(b)$，那么f叫做G到G'的一个同态。其中，等式左边的ab使用的是G的运算法，而f(a)f(b)的相乘是G'的运算法。

同态的性质

• f(e)=e'，即单位元映射到单位元
• $a\in G,f(a^{-1})=f(a)^{-1}$，即a的逆元映射到f(a)的逆元
• $ker f =\{a|a\in G,f(a)=e'\}$是G的子群，且f是单同态$\Leftrightarrow ker f = \{e\}$
• $f(G)=\{f(a)|a\in G\}$是G'的子群，且f是满同态$\Leftrightarrow f(G)=G'$
• H'是G的子群，则$f^{-1}(H')=\{a\in G|f(a)\in H'\}$是G的子群

核子群：$ker f =\{a|a\in G,f(a)=e'\}$
像子群：$f(G)=\{f(a)|a\in G\}$

同态分解定理

前置定理：

f是G到G'的同态，则f的核ker(f)是G的正规子群。
反过来，如果N是G的正规子群，则映射

$$s:G\mapsto G/N$$ $$a\mapsto aN$$ 是核为N的同态。

自然同态：$s:G\mapsto G/N$称为G到G/N的自然同态

同态分解：
f是G到G'的同态，则存在唯一的G/ker(f)到像子群f(G)的同构$\bar f:a\, ker(f)\mapsto f(a)$，是的f可分解为$i\circ \bar f\circ s$
其中，$i:c\mapsto c$，是f(G)到G'的恒等同态
$s:a\mapsto aN$是G到G/ker(f)的自然同态
即

$$\ \ \ \ G\ \ \ \ \overset f\rightarrow \ \ \ \ G'$$ $$\ \ \ \ s\downarrow \ \ \ \ \ \; \; \; \ \ \ \ \uparrow i$$ $$G/ker(f)\overset {\bar f}\rightarrow f(G)$$

设K是G的正规子群，H是G的包含K的子群，则

• $\bar H=H/K$是商群$\bar G=G/K$的子群
• $H\mapsto \bar H$是G的包含K的子群集，到$\bar G$的子群集的一一对应
• 当且仅当$\bar H$是$\bar G$的正规子群时，H是G的正规子群
• $\frac GH\cong \frac {\bar G}{\bar H}=\frac {G/K}{H/K}$

设H是群G的子群，且K是G的正规子群

• $HK=\{hk|h\in H,k\in K\}$是G的包含K的子群
• $H\cap K$是H的正规子群
• 映射$h(H\cap K)\mapsto hK,h\in H$是$H/H\cap K$到$HK/K$的同构