当前位置：首页 > news >正文

crypto抽象代数篇(群论)

news 2026/6/16 23:54:29

定义：群

群是一个代数结构（集合与一个或多个运算的组合），满足：

结合律：\((a * b) * c = a * (b * c)\)
封闭性：\(\forall a,b \in G,\ a * b \in G\)
单位元：\(\exists e \in G,\ \forall a \in G,\ e * a = a * e = a\)
逆元：\(\forall a \in G,\ \exists a^{-1} \in G,\ a * a^{-1} = a^{-1} * a = e\)

其中有限集合组成的为有限群，无限集合的为无限群。集合中的元素个数称之为群的阶，记作 \(|G|\)。

性质1：每个群都有唯一的单位元。
性质2：每个元素的逆元唯一。
性质3：消去律：\(a * b = a * c \implies b = c\)；方程 \(a * x = b\) 有唯一解 \(x \in G\)。
性质4：\((a * b)^{-1} = b^{-1} * a^{-1}\)
性质5：\((a^{-1})^{-1} = a\)

平凡群：只有单位元形成的群 \(\{e\}\)。

阿贝尔群

阿贝尔群：满足交换律 \(a * b = b * a\) 的群。

性质1：阿贝尔群的子群都是正规子群。
性质2：\((a^t)^m = a^{tm}\)
性质3：\((a * b)^t = a^t * b^t\)

子群

子群：设 \(H\) 为 \(G\) 的非空子集，且 \(H\) 本身成群，则称 \(H\) 是群 \(G\) 的子群，记作 \(H \le G\)。
如果子群只有单位元或它本身，则称为平凡子群。

性质1：平凡子群只有 \(\{e\}\) 或 \(G\)。
性质2：子群的逆元和单位元也是群 \(G\) 的单位元和逆元。

判断子群（子群判定定理）

设 \(H\) 是群 \(G\) 的非空子集。若有

\[\forall a,b \in H,\quad a b^{-1} \in H, \]

则 \(H\) 是 \(G\) 的子群。这里 \(a,b \in H \subseteq G\)，故 \(b^{-1}\) 是 \(b\) 在 \(G\) 中的逆元，乘法运算在 \(G\) 中进行。

构造子群的常见方式

若 \(G\) 为乘法群，则 \(G^m = \{a^m \mid a \in G\}\) 是群 \(G\) 的子群。
若 \(G\) 为加法群，则 \(mG = \{m \cdot a \mid a \in G\}\) 也是群 \(G\) 的子群。
将方式一中构造出的子群元素中等于单位元 \(e\) 的元素挑出形成的群也是群 \(G\) 的子群，即

\[G[m] = \{a^m \mid a^m = e\} \]

此处 \(G\) 为阿贝尔群，且 \(m \in \mathbb{Z}\)。

若有 \(d = \gcd(m,n)\)，有 \(\mathbb{Z}_n\{m\} = \mathbb{Z}_n\{d\}\)，这三个子群其实为同一个子群。

整数群的子群

定理1：\(H\) 是 \(\mathbb{Z}\) 的子群，则存在唯一的非负整数 \(m\)，使得 \(H = m\mathbb{Z}\)。

定理2：\(m_1, m_2\) 是非负整数，当且仅当 \(m_2 \mid m_1\) 时，有 \(m_1\mathbb{Z} \subseteq m_2\mathbb{Z}\)。

定理3：\(H\) 是 \(\mathbb{Z}_n\) 的子群，存在 \(n\) 的唯一正因子 \(m\) 使得 \(H = m\mathbb{Z}_n\)。
\(m_1, m_2\) 是 \(n\) 的正因子，则当且仅当 \(m_2 \mid m_1\) 时，有 \(m_1\mathbb{Z}_n \subseteq m_2\mathbb{Z}_n\)。

由子群构造新子群

\(H_1,\dots,H_n\) 是阿贝尔群 \(G\) 的子群，则 \(H_1 \cdots H_n\) 也是 \(G\) 的子群：

\[H_1 \cdots H_n := \{a_1 * \cdots * a_n \mid a_1 \in H_1,\ \dots,\ a_n \in H_n\} \]

\(H_1,\dots,H_n\) 是群 \(G\) 的子群，则 \(H_1 \cap \cdots \cap H_n\) 也是 \(G\) 的子群。

陪集

定义：\(H\) 为群 \(G\) 的子群，\(a \in G\)，则

\[aH = \{a * h \mid h \in H\} \]

称之为 \(a\) 在 \(G\) 中的左陪集；

\[Ha = \{h * a \mid h \in H\} \]

称之为 \(a\) 在 \(G\) 中的右陪集。

如果 \(aH = Ha\)，则称为 \(H\) 关于 \(a\) 在 \(G\) 中的陪集，\(a\) 称为代表元。

性质1：\(a \in H \iff [a]_H = H\)
性质2：\([a]_H = [b]_H \iff a^{-1} b \in H \iff b^{-1} a \in H\)

同一个子群构造的所有陪集，它们的大小都相等，并且等于子群的大小。

拉格朗日定理

\(G\) 是有限群，\(H\) 是 \(G\) 的任意子群，则

\[|H| \ \big|\ |G| \]

即任意子群的阶必定是群阶的因子。

正规子群

定义：设 \(N\) 是群 \(G\) 的子群，如果对于任意 \(a \in G\) 都有 \(aN = Na\)，则称 \(N\) 为 \(G\) 的正规子群，记作 \(N \trianglelefteq G\)。（阿贝尔群的子群一定是正规子群，注意这只是充分条件。）

商群

定义：在正规子群的陪集下构造的群称为群 \(G\) 在模 \(N\) 下的商群，记作 \((G/N, *)\)。

集合：

\[G/N = \{[a]_N \mid a \in G\} \]

这个集合里面的元素也是陪集形式的集合。定义二元运算：

\[[a]_N * [b]_N = [a * b]_N \]

定理1：\(G\) 是有限群，\(N\) 是 \(G\) 的正规子群，则

\[[G:N] = \frac{|G|}{|N|} \]

即商群的阶等于群的阶除以正规子群的阶，也就是陪集的个数。

定理2：\(G\) 是有限群，\(N\) 是 \(G\) 的正规子群，\(K\) 是 \(N\) 的正规子群，则

\[[G:K] = [G:N][N:K] \]

性质1：阿贝尔群的子群都是正规子群。
性质2：阿贝尔群的任意子群都能构造商群。
性质3：阿贝尔群的子群构造的商群也是阿贝尔群。

群同态

定义：设群 \((G, *)\) 和群 \((G', *')\)，如果函数 \(f: G \to G'\) 对于任意 \(a,b \in G\) 都有

\[f(a * b) = f(a) *' f(b) \]

则称 \(f\) 为 \((G, *)\) 到 \((G', *')\) 的群同态。

同态像：

\[\operatorname{Im} f = f(G) = \{f(a) \mid a \in G\} \]

指群 \(G\) 经过映射后在群 \(G'\) 中的集合。

同态核：

\[\operatorname{Ker} f = \{a \in G \mid f(a) = e'\} \]

其中 \(e'\) 表示 \(G'\) 的单位元，指群 \(G\) 中映射到群 \(G'\) 中为单位元 \(e'\) 的元素集合。

定理1：\(f: G \to G'\) 是群同态，则 \(\operatorname{Ker} f\) 是 \(G\) 的正规子群。

定理2：\(f: G \to G'\) 是群同态，任意 \(a,b \in G\)，有

\[f(a) = f(b) \iff a \equiv b \pmod{\operatorname{Ker} f} \]

定理3：\(f: G \to G'\) 是群同态，有

\[f \text{ 是单射} \iff \operatorname{Ker} f = \{e\} \]

性质1：\(f(e) = e'\)（\(e\) 和 \(e'\) 分别是群 \(G\) 和群 \(G'\) 的单位元）。
性质2：\(f(a^{-1}) = f(a)^{-1}\)，对任意 \(a \in G\)。
性质3：\(H\) 是 \(G\) 的子群 \(\implies f(H)\) 是 \(G'\) 的子群，同态像是群 \(G'\) 的子群。
性质4：\(H'\) 是 \(G'\) 的子群 \(\implies f^{-1}(H')\) 是 \(G\) 的子群（\(f^{-1}\) 表示 \(H'\) 的原像集合），同态核是群 \(G\) 的子群。
性质5：\(f(a^m) = f(a)^m\)，对任意 \(a \in G,\ m \in \mathbb{Z}\)。

群同态的复合

定义：\(f\) 是 \((G, *)\) 到 \((G', *')\) 的群同态，\(f'\) 是 \((G', *')\) 到 \((G'', *'')\) 的群同态，则 \(f'\) 和 \(f\) 的复合 \(f' \circ f: G \to G''\) 也是群同态。

判断单同态：\(\operatorname{Ker} f = \{e\}\)
判断满同态：\(\operatorname{Im} f = G'\)

群同构

同构的群本质上是同一个群。

定义：一个群同态满足双射（单射和满射）。

第一同构定理

设群 \((G, *)\) 和群 \((G', *')\)，\(f: G \to G'\) 是群同态（同态核为 \(\operatorname{Ker} f\)，同态像为 \(\operatorname{Im} f\)），则

\[G / \operatorname{Ker} f \cong \operatorname{Im} f \]

即群和同态核构造的商群与同态像形成同构。

循环群

此处引入构造子群的一种方法：设 \(G\) 是群，\(a \in G\)，则

\[\langle a \rangle = \{a^z \mid z \in \mathbb{Z}\} \]

是由 \(a\) 生成的 \(G\) 的子群。

定义：设 \(G\) 是群，\(g \in G\)，如果 \(G = \langle g \rangle\)，则称 \(G\) 是循环群，\(g\) 是循环群 \(G\) 的生成元。

定理1：任意循环群都是阿贝尔群。
定理2：循环群的子群是循环群。
定理3：设 \(G\) 是循环群，\(H\) 是其子群，则商群 \(G/H\) 是循环群。

元素的阶

设 \(G\) 是群，\(a \in G\)，如果 \(n\) 是满足 \(a^n = e\) 的最小正整数，则称 \(n\) 是元素 \(a\) 的阶，记作 \(\operatorname{ord}(a)\)。

性质1：\(G\) 是群，元素 \(a\) 的阶是 \(n\)（即 \(a^n = e\)），则存在 \(m \in \mathbb{Z}\)，有

\[n \mid m \iff a^m = e \]

性质2：有限循环群的阶是 \(n\)，则生成元的阶也是 \(n\)。

性质3：正整数 \(d \mid n\)，\(n\) 阶有限循环群恰有唯一的 \(d\) 阶子群。

性质4：\(n\) 阶有限循环群 \(\langle g \rangle\)，存在 \(k \in \mathbb{Z}\)，有

\[\operatorname{ord}(g^k) = \frac{n}{\gcd(n, k)} \]

性质5：\(n\) 阶有限循环群有 \(\varphi(n)\) 个生成元。

性质6：\(G\) 是有限群，元素 \(a\) 的阶是 \(|G|\) 的因子（拉格朗日定理推论）。

性质7：素数阶的群必然是有限循环群。

性质8：\(G\) 是 \(n\) 阶有限循环群，\(d\) 是 \(n\) 的正因子，则 \(G\) 里 \(d\) 阶元素一共有 \(\varphi(d)\) 个。

循环群的同构

无限循环群同构于 \(\mathbb{Z}\)。
有限循环群同构于 \(\mathbb{Z}_n\)。

也就是说，在研究循环群时可以转向研究同构的群的性质，它们具有相同的性质。

原根

乘法阶

定义：\(a \in \mathbb{Z}\)，\(\gcd(a, n) = 1\)，设 \(k\) 是满足

\[a^k \equiv 1 \pmod{n} \]

的最小正整数，称 \(k\) 是 \(a\) 在模 \(n\) 下的乘法阶，记为 \(\operatorname{ord}_n(a)\)。

原根

定义：\(g \in \mathbb{Z}\)，\(\gcd(g, n) = 1\)，如果 \(\operatorname{ord}_n(g) = \varphi(n)\)，称 \(g\) 是模 \(n\) 下的原根。

\[g^{\operatorname{ord}_n(g)} \equiv g^{\varphi(n)} \equiv 1 \pmod{n} \]

原根存在条件

设 \(p\) 是奇素数，\(e\) 是正整数，当

\[n = 1,\ 2,\ 4,\ p^e,\ 2p^e \]

时，模 \(n\) 下存在原根。

设模 \(n\) 下存在原根（\(n = 1, 2, 4, p^e, 2p^e\)），原根的阶是 \(\varphi(n)\)，\(\mathbb{Z}_n^*\) 的阶也是 \(\varphi(n)\)，因此原根是 \(\mathbb{Z}_n^*\) 的生成元，\(\mathbb{Z}_n^*\) 是循环群。