)
定义：群
群是一个代数结构（集合与一个或多个运算的组合），满足：
- 结合律：\((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\) 的非空子集。若有
则 \(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 \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,\dots,H_n\) 是群 \(G\) 的子群，则 \(H_1 \cap \cdots \cap H_n\) 也是 \(G\) 的子群。
陪集
定义：\(H\) 为群 \(G\) 的子群，\(a \in G\)，则
称之为 \(a\) 在 \(G\) 中的左陪集；
称之为 \(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\) 的任意子群，则
即任意子群的阶必定是群阶的因子。
正规子群
定义：设 \(N\) 是群 \(G\) 的子群，如果对于任意 \(a \in G\) 都有 \(aN = Na\)，则称 \(N\) 为 \(G\) 的正规子群，记作 \(N \trianglelefteq G\)。（阿贝尔群的子群一定是正规子群，注意这只是充分条件。）
商群
定义：在正规子群的陪集下构造的群称为群 \(G\) 在模 \(N\) 下的商群，记作 \((G/N, *)\)。
集合：
这个集合里面的元素也是陪集形式的集合。定义二元运算：
定理1：\(G\) 是有限群，\(N\) 是 \(G\) 的正规子群，则
即商群的阶等于群的阶除以正规子群的阶，也就是陪集的个数。
定理2：\(G\) 是有限群，\(N\) 是 \(G\) 的正规子群，\(K\) 是 \(N\) 的正规子群，则
性质1：阿贝尔群的子群都是正规子群。
性质2：阿贝尔群的任意子群都能构造商群。
性质3：阿贝尔群的子群构造的商群也是阿贝尔群。
群同态
定义：设群 \((G, *)\) 和群 \((G', *')\)，如果函数 \(f: G \to G'\) 对于任意 \(a,b \in G\) 都有
则称 \(f\) 为 \((G, *)\) 到 \((G', *')\) 的群同态。
同态像：
指群 \(G\) 经过映射后在群 \(G'\) 中的集合。
同态核：
其中 \(e'\) 表示 \(G'\) 的单位元，指群 \(G\) 中映射到群 \(G'\) 中为单位元 \(e'\) 的元素集合。
定理1：\(f: G \to G'\) 是群同态，则 \(\operatorname{Ker} f\) 是 \(G\) 的正规子群。
定理2：\(f: G \to G'\) 是群同态，任意 \(a,b \in G\)，有
定理3：\(f: G \to G'\) 是群同态，有
性质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\) 是群，\(a \in G\)，则
是由 \(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}\)，有
性质2：有限循环群的阶是 \(n\)，则生成元的阶也是 \(n\)。
性质3：正整数 \(d \mid n\)，\(n\) 阶有限循环群恰有唯一的 \(d\) 阶子群。
性质4：\(n\) 阶有限循环群 \(\langle g \rangle\)，存在 \(k \in \mathbb{Z}\)，有
性质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\) 是满足
的最小正整数，称 \(k\) 是 \(a\) 在模 \(n\) 下的乘法阶，记为 \(\operatorname{ord}_n(a)\)。
原根
定义：\(g \in \mathbb{Z}\)，\(\gcd(g, n) = 1\)，如果 \(\operatorname{ord}_n(g) = \varphi(n)\)，称 \(g\) 是模 \(n\) 下的原根。
原根存在条件
设 \(p\) 是奇素数，\(e\) 是正整数，当
时，模 \(n\) 下存在原根。
设模 \(n\) 下存在原根（\(n = 1, 2, 4, p^e, 2p^e\)），原根的阶是 \(\varphi(n)\)，\(\mathbb{Z}_n^*\) 的阶也是 \(\varphi(n)\)，因此原根是 \(\mathbb{Z}_n^*\) 的生成元，\(\mathbb{Z}_n^*\) 是循环群。
寻找原根
\(a\) 是原根当且仅当：
其中 \(p_i\) 是 \(\varphi(n)\) 的所有不同素因子。
离散对数
定义（指标 / 离散对数）
设 \(\gcd(a, n) = 1\)，且模 \(n\) 下存在原根 \(g\)。则必存在唯一的整数 \(x\)（\(0 \le x < \varphi(n)\)），使得
称 \(x\) 是以 \(g\) 为底的 \(a\) 模 \(n\) 的离散对数，记作：
定理1：
设 \(\gcd(b, n) = 1\)，\(y = \log_g(b)\)，\(m\) 是整数，\(h\) 也是原根，有以下性质：
离散对数问题（DLP）
设 \(G\) 是循环群，\(g \in G\) 是生成元，对于 \(y \in G\) 和正整数 \(x\)，有
则离散对数问题定义为：给定 \(y\) 和 \(g\)，求 \(x = \log_g(y)\)。
RSA 的模数
设
则 \(\mathbb{Z}_n^*\) 中任意元素的阶都是 \(\lambda(n)\) 的因子，且 \(\mathbb{Z}_n^*\) 的阶是 \(\varphi(n)\)，元素最大阶是 \(\lambda(n)\)。