筑基

2026-01-08

信安数基，信安筑基。

离散数学

集合

映射

映射 $f$ 是从 $e_1 \in S_1$ 到 $e_2 \in S_2$ 的一种运算，记作 $f: S_1 \rightarrow S_2, f(e_1) = e_2$。

映射的左值（变量）和右值（值）可以有多个，形如 $f(x_1,x_2) = y, f(x) = \pm y$ 等。

单射、满射、双射

对于映射 $f: A \rightarrow B, f(x) = y$，
单射指 $\forall x \in A, \text{有且只有一个} y \in B \text{满足} f(x) = y$；
满射指 $\forall y \in B, \text{有且只有一个} x \in A \text{满足} f(x) = y$；
双射指既是单射又是满射的 $f$。

双射 $f$ 具有完全且唯一的可逆性，即 $\exists f^{-1}: B \rightarrow A$，其性质与 $f$ 相同。

以初等数学的方程、函数为例，“映射” $f: Q_x \rightarrow Q_y$：

$f_1: y = x^2$ 是单射（每个 $x$ 只能对应唯一的 $y = x^2$）但不是满射（$y$ 对应的 $x$ 数目为 $\begin{cases} 2, y > 0 \\ 1, y = 0 \\ 0, y < 0 \end{cases}$。初等数学中，函数依定义均满足单射。
$f_2: y^2 = x$ 是满射（和 $f_1$ 相反），依变量约定，$f_2$ 不是 $x$ 到 $y$ 的函数。
$f_3: y = 2 \cdot x$ 既是满射也是双射，其逆映射为 $f_3^{-1}: x = \frac{1}{2} y$。

结合法

群

~~坐稳扶好.sage~~

群是近世代数(Modern Algebra)的起点。
近世代数的哲学在于抽象——其将运算等性质符号化，从更上层的角度研究不同集合的运算特征，宛若OOP语言中的较上层类的函数接口。

集合与结合法的概念较为宽泛，其共性太过有限而难以利用——迈入近世代数的山门，则是从约束更多、但也有更多共性与研究价值的“群”开始。

“移进”——从集合到群

速通流可以直接快进到“群”，但请确保充分理解封闭性、结合性、单位元（幺元）、逆元的概念。

结合法与集合、半群、广群、独异点和群是包含递进的关系，即后者一定是前者的子集，以附加条件逐级约束之。

半群

对于定义了结合法 $\cdot$ 的集合 $S$ ：
若该运算满足封闭性，即 $\forall a,b \in S, a \cdot b \in S$，则该集合成为一个半群。

实例：整数集合 $\mathbb{Z}$ 上的加法运算 $+$ （简记为 $(\mathbb{Z}, +)$ ）构成一个半群，但 $(\mathbb{Z},\div)$ 不构成一个半群（因为其不满足封闭性，真分数不在整数集合内）。

广群

若对于半群 $G$，其运算还满足结合性，即 $\forall a,b \in G, (a \cdot b) \cdot c = a \cdot (b \cdot c)$，则称之为一个广群。

实例：~~老生常谈的~~ $(\mathbb{Z},+)$ 也是一个广群。$(\mathbb{Q},\div)$ 是半群而不是广群（显然 $(a \div b) \div c \neq a \div (b \div c)$）。

独异点（又名幺半群）

若对于广群 $G$，$\exists e \in G, \forall a \in G, a \cdot e = e \cdot a = a$，则称之为一个独异点（又名幺半群）。
其中 $e$ 称为单位元（或幺元）。

严格地，有左/右单位元之差分：若 $e$ 满足了 $a \cdot e = a$，则其为右单位元；反之则为左单位元，既是右单位元也是左单位元的元素称为单位元。

实例：$(\mathbb{Z},+)$ 是一个独异点（$e = 0$）；$(\mathbb{Z_{+}},+)$ 是一个广群（其满足封闭性、结合性），但不是独异点（因为其中不存在单位元）。

群

若对于独异点 $G$，$\forall a \in G, \exists a^{-1} \in G$ 满足 $a \cdot a^{-1} = e$，则称之为一个群。
其中 $a^{-1}$ 称为逆元。

同样 $a^{-1}$ 理论上亦有左/右逆元之差分，其理同上。

实例：$(\mathbb{Z},+)$ 是群（任意元素的逆元是其相反数）；$(\mathbb{Q/0},\times)$（零以外的有理数的乘法运算）是群，而 $(\mathbb{Q},\times)$ 不是（显然 $\mathbb{0}$ 没有逆元）。

小结

集合与群是两个最为重要的数学结构之一。
群是定义了结合法，且满足封闭性、结合性、单位元、可逆性四条件的集合。

同态与同构

同态与同构研究的是两个群之间的关系，其允许我们在几种不同的数学结构之间进行转换。

同态

对 $f: G_{1} \rightarrow G_{2}$，若 $\forall a,b \in A$，$f(a \cdot b) = f(a) \cdot f(b)$，则称 $f$ 是 $G_{1}$ 到 $G_{2}$ 的一个同态映射。

若两侧的运算是“相同”的，可称之为op同态。
如令 $G = Z_{p} \space p \notin \{0,2\}, f: G \rightarrow G, f(x) = x \cdot 2 \bmod p$。此时 $\forall a,b \in Z_{p}, f(a) + f(b) = (2 \cdot a + 2 \cdot b) \equiv f(a + b) = 2 \cdot (a+b) \bmod p$。可以发现 $f$ 满足加法同态（即“映射”操作 $f$ 和该群内的加法操作 $+$ 的顺序可以任意交换，不影响结果）。

上述实例中的 $f$ 满足 $G_1 = G_2$，由一个群到自身的映射也被称为自映射。有限群内，自映射的重要特点是单射、满射、双射任意一者是另外二者的充要条件。

同构

同构就是满足双射的同态 $f$。

子群“系”

子群

对于群 $G$，若群 $H$ 满足 $\forall a \in H \Rightarrow a \in G$，且 $H$ 拥有和 $G$ 相同的结合法，则称 $H$ 为 $G$ 的子群，记作 $H \subseteq G$。
显然 $\{e\}$ 和 $G$ 一定是 $G$ 的子群，它们称作 $G$ 的平凡子群。若 $H \neq G$，则称之为 $G$ 的非平凡子群。

如在普通加法下，对于 $G = Z_{6} = \{0,1,2,3,4,5\}$ 而言，$H = \{0,2,4\}$ 即为其子群（$\{0,3\}$ 等显然也是）。

相同的结合法在部分场景下极为关键：如对于普通加法， $2Z \subseteq Z$，但 $Z_{+} \nsubseteq Z$，因为 $Z_{+}$ 不是群（其没有单位元）。

子群的重要定理之一是拉格朗日定理~~群论版~~：$H \subseteq G, |G| \neq \inf \Rightarrow |H| | |G|$。

若 $H \subseteq G$，记 $[H:G] = \frac{|H|}{|G|}$，称 $[H:G] \in Z_{+}$ 为H对G的指标。

其证明需要用到陪集的知识，后置咕一下。

陪集

设 $H \subseteq G, a \in G$，定义 $aH = \{ah : h \in H\}$ 为 $H$ 的左陪集，类似地可以定义右陪集。显然对于交换群来说左/右陪集是相同的。
依然以 $G = Z_{6}$，$H = \{0,2,4\}$ 为例，可以计算 $0H = \{0,2,4\}, 1H = \{1,3,5\}, 2H = \{0,2,4\}$ 等。

陪集的特殊性在于：

设 $f: H \rightarrow aH, f(h) = ah$，根据子群定义（相同结合法）可知 $f$ 是一个同构映射。对于有限群 $G$，$f$ 也一定是双射（群中 $a^{-1}$ 存在，推定存在唯一的单射逆映射 $f^{-1}: aH \rightarrow H, f^{-1}(h) = a^{-1}h$。
$|aH| = |H|$ 成立，即所有陪集的大小都和子群 $H$ 相同。
$\forall g \in G, g \in a_{?}H$，即 $G$ 中所有元素都会出现在某个陪集中。
$\forall a_1,a_2 \in G, a_{1}H \Join a_{2}H = \emptyset$ 或 $a_{1}H = a_{2}H $ 成立。

其中第2、3项由 $f$ 双射的性质可导出。第4项

依然以上述的 $H$, $G$ 为例：
$H = \{0,2,4\}, 1H = \{1,3,5\}$，显然有 $|1H| = |0H| = |H|$。
同时 $\forall g \in G$，$g \in a_{?}H$，具体地，$g \in \begin{cases} 0H, g \equiv 0 \bmod 2 \\ 1H, g \equiv 1 \bmod 2 \end{cases}$。
另 $\begin{cases} a_1H = a_2H, a_1 \equiv a_2 \bmod 2 \\ a_1H \Join a_2H = \emptyset, a_1 \nequiv a_2 \bmod 2$。

正规子群

~~传说中的@正规子群.AI~~

正规子群(Normal Subgroup)是指陪集满足交换性的子群 $H$， $\forall a \in G, H \subseteq G, \{a \cdot H\} = \{H \cdot a\}$，则称 $H$ 为 $G$ 的正规子群。

不难证明阿贝尔群的子群都具有正规性。

上述条件可进一步写作：$\forall a \in G, h \in H, a \cdot h \cdot a^{-1} \in H$。

由上式的对偶性，同右乘 $a$ 后推广 $h$ 至 $H$ 可推定。

商群

只有正规子群可以生成一个商群。

设 $H \text{为} G$ 的正规子群，则 $\{aH :a \in G\}$ 上可定义运算 $\cdot$：$(aH) \cdot (bH) = (ab)H$，其亦成为一个群，称之为商群 $G/H$。

“商群”的概念较为抽象，依然从较为熟悉~~百听不厌~~的整群三剑客 $Z,mZ,Z_m$ 举实例切入：

对于群 $G = (Z_{35},+)$，$H = \{7k : k \in Z_5\}$ 显然为其子群（省略 $+$ 运算，下同）。不难验证 $H$ 也是 $G$ 的正规子群。
写出 $H$ 的陪集有 $0+H,1+H$ 等，即 $\{0,7,14,21,28\},\{1,8,15,22,29\} \cdots$；
故商群 $G/H = \{0+H,1+H,\cdots,k+H : k \in Z_5\}$，其中商群中的每个元素（也就是 $H$ 对 $G$ 的（左）陪集）宏观体现即为 $Z_35$ 内模 $7$ 余数相同整数的集合。

其中商群的运算实例亦是水到渠成：$(0+H) + (1+H) = (0+1) + H = (1+H)$；$(3+H) + (4+H) = (2+H)$ 等，相当于 $(a_1+H)+(a_2+H) = (a_3+H)$ 中 $a_i$ 的运算只在 $Z_5$ 下进行，其运算法与 $H$ 定义中的 $k$ 一致。

商群的重要判定性质之一是其良定性(well-defined)，即其运算律 $(aH)(bH) = (ab)H$ 成立；其交换性蕴含了商群运算不依赖于代表元 $a,b$ 的选取。

商群可以理解为一个正规子群对既有群的一个“划分/分区(partition)”。

循环群

若 $\forall a \in G, \exists i \in \mathbb{Z_{+}}, a^{i} = e$，则称群 $G$ 为循环群。
此时 $\forall a \in G : ord(a) = n$ 的 $a$ 都是生成元。

实际上

设 $|G| = n$，由拉格朗日定理可知 $i | n$ 一定成立，进一步地，$\forall a \in G, a^{n} = e$ 亦一定成立。

实例：$(\mathbb{Z_{p}},+)$ 是循环群，$\forall a \neq \mathbb{0}$ 都是生成元（参考剩余系相关）。

推论：

素数阶群一定是循环群。考虑 $\forall a \in G \space |G| = n$，$a$ 生成的子群为 $H$，根据拉格朗日定理，$|H| | n$，又 $n$ 为质数 $\Rightarrow$ $|H| = 1$ 或 $|H| = n$，其中 $a \neq e$ 时 $|H| = n \Rightarrow a^{n} = e$。

交换群

若群 $(G,\cdot)$，上的运算 $\cdot$ 还满足交换性，即 $\forall a,b \in G, a \cdot b = b \cdot a$，则称之为交换群，又名阿贝尔(Abel)群。

实例：$\mathbb{Z}$ 上的 $+$ 显然也是一个交换群；但 $M_{2 \times 2}$，即 $2 \times 2$ 矩阵的乘法运算就不是交换群。

环与域

环

许多时候，对于一个群，我们希望研究其对多种结合法（运算）的特性。
以 $\mathbb{Z},(+,\cdot)$ 这个~~妇孺皆知的~~运算进行迁移，设对于一个群 $G$ 定义了两种运算（一般就表示为加法 $+$ 和乘法 $\cdot$），若：

$(G,+)$ 是一个交换群；
$(G,\cdot)$ 是一个广群，即只需满足封闭性和结合性；
$+$ 对 $\cdot$ 满足分配律，即 $a \cdot (b + c) = a \cdot b + a \cdot c$，

则称 $(G,(+,\cdot))$ 为一个环(Ring)。

进一步地，依据运算 $\cdot$ 是否满足交换性、环中是否存在乘法单位元 $\mathbb{1} \neq \mathbb{0}$，
可以细言一个环为 交换/非交换 含/不含幺 环。

环中加法单位元一定存在（$(G,+)$ 是群的必要条件），记作为 $\mathbb{0}$；乘法单位元若存在则记作 $\mathbb{1}$。

实例：

$(\mathbb{Z},(+,\times))$ 是一个交换含幺环（环判定：$(\mathbb{Z},+)$ 是交换群，$(\mathbb{Z},\times)$ 是广群，$(a+b)\times c = a \times c + b \times c$；特征判定：存在 $\mathbb{1} = 1 \neq \mathbb{0} = 0$；$(\mathbb{Z},\times)$ 具备交换性）。
$(\mathbb{M_{2 \times 2} : |M| \neq 0,(+,\cdot)})$ 是一个非交换含幺环（环判定同上；特征判定：存在 $\mathbb{1} = \mathbb{I}_{2} \neq \mathbb{0} = 0$，但 $\cdot$ 不具备交换性。

整环

先介绍零因子(zero divisors)的概念：
设 $a,b \neq \mathbb{0} \in R$，若 $a \cdot b = \mathbb{0}$，则称 $a,b$ 为 $R$ 的零因子。
如在 $(\mathbb{Z_{6},(+,\cdot)})$ 中， $2 = 0 $，其中 $2,3$ 就是零因子。

整环(Integral Ring)，~~顾名思义~~，是 $(\mathbb{Z},(+,\times))$ 概念的拓展。
若一个交换含幺环没有零因子，即 $\forall a,b \neq \mathbb{0} \in R, a \cdot b \neq \mathbb{0}$，则称之为整环。

实例：$(\mathbb{Z},(+,\cdot))$ 是整环~~废话文学.sage~~；设 $p,m$ 分别为质数与合数，则 $(\mathbb{Z_{p}},(+,\cdot))$ 也是整环，但 $(\mathbb{Z_{m},(+,\cdot)})$ 不是。

整环除无零因子外的一个重要特性是消去律：$\forall a,b,c \neq \mathbb{0} \in R, a \cdot b = a \cdot c \rightarrow b = c$。

~~某种意义上的初等数学老生常谈~~

域、理想

域和理想都是环的同级延申。

域

域是更进一步的环。
若整环 $(R,(+,\cdot))$ 下，$(R,\cdot)$ 也满足交换性且具有单位元 $\mathbb{1}$ ，则称之为一个域。

域可以认为是可以进行各种数学运算（加减乘除，其中除要求非 $\mathbb{0}$）的代数结构。

实例：$\mathbb{Q}$ 显然是域~~省略 $(+,\cdot)$，下同~~；设 $p,m$ 分别为素数和合数，则 $\mathbb{Z_{p}}$ 也是域，而 $\mathbb{Z}$ 和 $\mathbb{Z_{m}}$ 不是（ $\forall a \neq \mathbb{1} \in \mathbb{Z}, \nexists a^{-1} \in \mathbb{Z}$；$\mathbb{Z_{m}}$ 不是整环（对 $m$ 的因数分解就是其零因子），同时也不满足可逆性（显然可逆要求 $(a,m) = 1$））。

由上可以整理出递进关系：
集合 -> 广群 -> 半群 -> 独异点 -> 群 -> 交换群；环 -> 整环 -> 域。

理想

理想(Ideal)是一种特殊的子环。
若 $(I,+) \subseteq (R,+)$ 满足吸收性，即 $\forall r \in R, a \in I, (a \cdot r, r \cdot a) \in R$（对于交换环可简化为 $a \cdot r \in R$），则称 $I$ 为 $R$ 的一个理想。

“吸收性”作人话之解，即为能通过乘法（$\cdot$）吸收任意元素的子集，可视为“原环的倍数”。
实例：$\mathbb{Z/2Z}$ 是 $\mathbb{Z}$ 的一个理想，因为任意整数乘以一个偶数的结果必为偶数。

特别地，显然 $R$ 亦为自身的理想，此时称其为 $R$ 的平凡理想，对应满足条件的 $\forall I \neq R$ 为 $R$ 的非平凡理想。

主理想和素理想要求原环 $R$ 必须为交换环。

主理想

主理想是由单个元素 $a \in R$ 生成的理想 $\langle a \rangle = R \cdot a = \{r \cdot a | s\forall r \in R\}$。

实例：$\mathbb{Z/2Z}$ 就是由 $2$ 生成的主理想；任意环 $R$ 的平凡理想的生成元是乘法单位元 $\mathbb{1}$。

(反例咕咕中)

素理想

对于环 $R$ 的非平凡理想 $I$，若 $\forall a,b \in R, a \cdot b \in I \Rightarrow a \in I \text{或} b \in I$，则称之为 $R$ 的素理想。

如 $\mathbb{Z}$ 中的素理想就是 $\langle p \rangle$，~~即素数生成的理想~~

最大理想

对于环 $R$ 的非平凡理想 $I$，若 $\forall U \subseteq R, I \subseteq U \subseteq R \Rightarrow U = I \text{或} U = R$，则称之为 $R$ 的最（极）大理想。

主理想整环

~~拼凑而成的概念，字面意义，全是主理想的整环~~

对于整环 $R$，若其中的理想 $I \subseteq R$ 都是主理想，则称之为主理想整环。

主理想整环中，每个素理想都是极大理想。由于主理想整环中，每个理想都可以表示成 $(d) | d \in R$ 的形式，结合素理想的性质可证明 $(p) \subseteq (d)$ 时 $d \in \{1,p\}$（相当于 $(d) \in \{(p),R\}$ ）。

常见的主理想整环包括整数环 $\mathbb{Z}$ 和多项式环 $\mathbb{F_{p}/f}$（其中 $f$ 为 $F_{p}$ 下的不可约多项式）。

抽象多项式

常见的 $n \text{次多项式} f(x)$ 形如 \[c_nx^n + c_{n-1}x^{n-1} + \cdots + c_1x^1 + c_0 = \sum_{i=0}^{n} c_{i}x^{i}\]，其中常有 $x \in F_{p}$ 。

$F_{p}$ 是模 $p$ 整数环形成的域。

回顾常见多项式的运算规则：

加法是对应项系数在 $Z_{p}$ 下相加，即相加后对 $p$ 取模；
乘法是普通的多项式乘法，其中系数运算同样在 $Z_{p}$ 下进行。

如 $F_{3}$ 下令 $a = x + 2, b = x + 1$，则 $a + b = 2x$，$a \cdot b = x^2 + 2x$。

注意此时的多项式运算依然不是一个环，因目前其尚未定义除法（乘法逆运算）和模运算。

定义一个多项式的度(degree)为其最高变量的幂数，简记作 $d(f) = n \forall f = \sum_{i=0}^{n} c_{i}x^{i}$。

为使这个多项式群能拓展为一个环，需要将多项式群对一个度为 $n$ 的不可约多项式 $f$ 取模，使之形成一个商环(Quotient Ring)，记作 $Z_{p} / f$。

不可约多项式具体参阅下一小节，先简记为 $F_p$ 下不能再“约分”的多项式即可；$f$ 为任意非零多项式时 $Z_{p} / f$ 都能称为一个商环，但 $f$ 为不可约多项式时其方为一个整环，~~参考抽象代数中的二级结论：对于交换含幺环 $R$，$P$ 为素理想的充要条件为 $R/P$ 为整环。~~

类比 $Z/mZ$ 给出的相似代数结构有助于理解。
如 $Z_{m} \subseteq Z \text{，定义} f: Z \rightarrow Z_{m}, f(x) = x \bmod m, ker(f) = mZ$，则这个商群和 $im(f)$，即 $Z_{m}$ 同构。
同样地，$F_{f}$ （即模 $f$ 的多项式）亦可进行类似的定义。

对于加法和乘法，每次运算完成后要求对 $f$ 取模，模运算依长除法进行；
除法相当于乘以乘法逆元，乘法逆元可由扩展欧几里得除法(gcdext)获得。

由于 $Z_{p}/f$ 为整环，因而其没有零因子，$(f^{'},f) = 1$必定成立；类比 $Z_{p}$ 可知环上的多项式都存在乘法逆元。
对多项式的gcdext和对整数的gcdext本质无异（从抽象运算而言），注意此处多项式除法的结果、余数均为多项式，且通过长除法给出（此时并未进入到 $F_{f}$ 中）。

举例：设 $f_i \in F_2 / (x^2 + x + 1), f_0 = x, f_1 = x^2 + 1,f_2 = x^2 + x$。
运算示例：\[f_0 \cdot f_1 = (x^3 + x) \bmod (x^2 + x + 1) = x + 1\]

不可约多项式

效仿 $Z$ 中素数的概念，引入“不可约多项式”：
若 $f,f_a,f_b \in Z_p d(f_a),d(f_b) \leq d(f),\forall f_a \cdot f_b = f \Rightarrow f_a = f \text{或} f_b = f$（且显然另一者为 $1$），则称 $f$ 为不可约多项式。
与素数~~a.k.a.不可约数~~的差分在于，$f$ 是否为不可约亦取决于 $x$ 的所在环（域），如 $x^2 + 1 \in F_{3}$ 是不可约多项式，但 $x^2 + 1 \in F_{2} = (x+1)^{2}$。

不可约多项式的测试法与素数判断类似：满足以下条件的 $d(f) = n$ 的多项式 $f$ 为 $F_{p} \text{下的 } n$ 次不可约多项式：

其不能被所有 $d(f^{'}) \leq \lfloor \frac{n}{2} \rfloor \text{的不可约多项式} f^{'}$ 整除，
其在 $F_{p}$ 内没有根（此项不适用于 $n = 1$，故 $\forall k \in F_p, x + k$ 均为 $F_p$ 下的不可约多项式）。

//???

举例：判断 $f = x^3 + x + 1 \in F_{3}$ 是否为不可约多项式？注意到 $f$ 有一个根 $x = 1$ （满足 $f(x) = 0$），故其不是不可约多项式。
若将之转移至 $F_{2}$：首先确定其没有根，随后检验 \[\begin{cases} f \bmod x = 1 \neq 0 \\ f \bmod (x+1) = 1 \neq 0 \end{cases}\] ，检验通过，确定其为不可约多项式。

环阶与本原多项式

若 $d(f) = n$，则商环 $F_{p}/f$ 的最大阶为 $p^n - 1$。

“最大阶”的理解：$x$ 的阶显然为 $p$；$n$ 次项之间相互独立，因而 $n$ 次多项式的取值个数不会超过 $p^{n}$，即其阶数上界为 $p^{n} - 1$（因为阶数定义为满足 $f^{n} = \mathbb{0}\text{（单位元）} = 1$ 的最小整数 $n$）。

而商环的实际阶数 $n$ 定义为满足 $f^n = x^{}$

定义拓展

进一步地，由于域中元素可以进行各类数学运算，故 $x$ 亦可被定义在任何域 $F$ 中。

现记定义在域 $F$ 中的“自变量” $x$ 构成的多项式 $f \in F[X]$。$F[X]$ 构成一个多项式环(Polynomial Ring)，$F[X]$ 中的元素个数显然是无限的。
同样引入抽象的模不可约多项式 $f_q$，构建商环 $F[X]/f_q$，若 域 $F$ 的阶为 $p$，，则 $F/f_q$ 的最大阶数为 $p^{n} - 1$。

格

格(Lattice)是指一个拥有最大上界和最小下界的偏序关系集。

数论

笔者学习信安数基、密码学等相关知识时，多数教材均选择将数论先全盘托出，随后再讲解离散数学（抽象代数）相关内容。
但数论中部分关键概念（如中国剩余定理、模n整数的原根等）本质上是抽象代数在模n整数下的实例；通过调整部分内容，可以将之置于代数之后，作为其实例之一进行理解，对抽象代数的消化吸收和数论相关分析、推导的接受度均大有裨益。

模n高次同余式

指数与原根

设 $p$ 为质数，$(a,p) = 1$，$a$ 在 $Z_p$ 下的指数定义为满足 $a^{k} \equiv 1 (\bmod p)$ 的最小正整数 $k$，记作 $ord_p(a)$（亦可简记作 $ord(a)$）。
若 $ord_p(a) = \varphi(p) = p-1$，则称之为 $Z_m$ 下的原根。

本质上其就是群 $(Z_m,\times)$，原根即 $Z_m$ 下乘法群的生成元。

根据费马小定理，$\forall (a,p) = 1, a^{p-1} \equiv 1 (\bmod p)$ 必定成立，因此“原根”只是 $ord(a)$ 达到了其上界。同时数论分析和拉格朗日定理都可以给出，$\forall (a,p) = 1, ord(a) | p-1$ 同样成立。

同时对任意一个原根 $g$，$\forall i \in \{c_i\}, g^{i}$ 亦为其原根，其中 $\{c_{i}\}$ 为 $p-1$ 的简化剩余系。
由同余相关分析可以导出检验 $a$ 是否为 $Z_p$ 原根的快捷方法：设 \[p-1 = 2 \times \prod_{i=1}^{n}p_{i}^{e_{i}}\]
其中 $p_i$ 为奇质数，若 \[\forall k = \prod_{i=1}^{n} p_{i}^{s_{i}}, 0 \leq s_{i} \leq e_{i}, k < \frac{p-1}{2}, a^{k} \neq \pm 1 (\bmod p)\]
则 $a$ 为其原根。
同时此步可用于计算 $a$ 的指数：将测试的 $k$ 升序排序，得到最小的满足条件 $k$，则 \[ord_m(a) = \begin{cases} k, a^k \equiv 1 \bmod p \\ 2k, a^k \equiv -1 \bmod p \end{cases}\]

$a^{p-1} \equiv 1 \bmod p \Rightarrow a^{\frac{p-1}{2}} \equiv \pm 1 \bmod p$，此为余-1的“截断”依据。

若 $ord(a) = m$，则 $ord(a^i) = \frac{m}{gcd(i,m)}$，具体原因仍然可以参考剩余系相关——构造一个同态映射 $f: Z_{p-1} \rightarrow Z_{p}, f(x) = g^{x}$，观察其“逆映射”的指数即可。

可推导出 $Z_{p}$ 下的原根个数为 $\varphi{\varphi{N}}$，同时从任一原根可推出其全部原根——对于任意群亦是如此，已知单个生成元和群阶，即可推出其全部的生成元~~前提是群的阶不被打造成RSA一般的极难分解的大整数~~

运算示例

以 $Z_{43}$ 下的运算为例。

求 $ord(2)$：
存在 $\varphi{43} = 43 - 1 = 42 = 2 \times 3 \times 7$；计算 $Z_{43}$ 下 $2^3 = 8, 2^7 = 42 = -1$，因而 $ord_43(2) = 7 \times 2 = 14$。
再试求 $Z_{43}$ 下的所有原根：
已知 $2$ 不是其原根，再尝试 $3$：
$3^3 = 27, 3^7 = 37$，说明 $3$ 是 $Z_{43}$ 的原根（检验：$3^{21} \equiv -1 \bmod 43 \rightarrow 3^{42} \equiv 1 \bmod 43$）。

再列出 $42$ 的简化剩余系：
$\{c_i\} = \{1,5,11,13,17,19,23,25,29,31,37,41\}$，计算得 $Z_{43}$ 原根有 $3,28,30,12,26,19,34,5,18,33,20,29$。

密码学实例

RSA

RSA的基础知识不再赘述，详见RSA。
其部分~~“联动”~~的性质如下：

RSA的加密 $e$ 和解密 $d$ 都是 $Z_N \rightarrow Z_N$ 的映射，且均满足乘法同态；RSA运算在一个交换含幺环上进行，其零因子为 $N$ 的因数分解 $p,q$，故其不是整环。
RSA中，$Z_{N}$ 下原根构成的乘法群的阶是 $\varphi{N}$，而根据拉格朗日定理，任意元素构成的乘法群阶一定能整除 $\varphi{N}$。此点是RSA正确解密的基础，因为 $ed \equiv 1 \bmod \varphi{N}$，其保证了 $\forall c \in Z_{N}, m^{k \cdot \varphi{N} + 1} = c^d \equiv m \bmod N$。

DLP

尽管DLP(Discrete Logorithm Problem,离散对数问题)极少被直接用于加密等，但其思想及在各种域($Z_p,E,F_p[X]/f$ 等)中的应用，依然是大量现代密码学算法的安全性的基石之一。

其核心思想为：

给定一个群 $(G,\cdot)$ 和 $P \in G$
给定 $n \in Z$，正向数乘计算，即计算 $Q = nP$ 非常高效（可以通过快速幂/乘拓展来实现，即将 $nP$ 中的 $n$ 转化为二进制）
但给定 $(Q,P)$，找到 $n$ 满足 $nP = Q$ 是非常困难的

典型的群实例包括 $(Z_{p},\times)$ 和 $(E,+)$，后者亦被称为ECDLP。
计算难度的单向性使其可被用于设计陷门函数(trapdoor function)，即加密等操作时可以将关键信息隐藏于 $n$ 中，攻击者即使知道 $(P,Q)$ 也无法倒推出 $n$，同时 $Q$ 数学上携带了 $n$ 的信息且可传递。

DH

DLP最著名的应用实例之一当属Diffle-Hellman密钥交换：
对于一个安全的群 $(G,\cdot), |G| = n$，通信双方选择 $a,b \in Z_{n}$ 作为私钥，选择 $G$ 的一个生成元 $P$，计算 $A = aP, B = bP$ 并发送给对方。
对方接收到 $A$ 或 $B$ 后将之与自己的私钥再相乘：
$aB = a(bP) = (ab)P, bA = b(aP) = (ba)P$，又 $Z$ 下的乘法满足交换性，显然由此双方获得了相同的点 $S = abP$。
而全程双方传递的信息只有 $(A,B,P)$，攻击者即使截获之，因计算 $n$ 的困难性，亦无法计算出 $S$。

安全群与攻击

对于DLP的攻击，在Brute-force（逐个尝试 $n$ 直至命中）以外亦有些许技巧；相应地，为了保证DLP问题的应用安全性，其对群的设计也提出了一些要求。

Pohlig-Hellman

Pohlig-Hellman攻击又名“子群攻击”，其核心就是拉格朗日定理的“拓展版”。

由拉格朗日定理，设 $|G| = n$，则 $\exists H \subseteq G, H = n^{'} \forall n^{'} | n$。进一步地，设 $G$ 的生成元为 $g$，则 $|\langle k \cdot \rangle| = \frac{n}{gcd(n,k)}$，其表明了可以通过控制 $k$ 来生成不同大小的子群—— $gcd(n,k) = 1$ 时其转化为 $\frac{n}{k}$。

而 $f: G \rightarrow H, f(x) = k \cdot x$ 是一个同态映射，因此若 $Q = xP$，则 $f(Q) = x^{'}'f(P)$ 且 $x^{'} \equiv x \bmod \frac{n}{k}$。

解出大量如此的 $x^{'} \equiv x \bmod \frac{n}{k}$ 后，根据中国剩余定理即可解出 $x$。
结合CRT对于模数互质的要求，设 $n = \prod_{i=1}^{n} p_{i}^{e_{i}}$，推定其宏观上的时间复杂度会由 $O(n)$ 降低至 $O(\sum_{i=1}^{n} p_{i})$。

~~不要问指数 $e_{i}$ 去哪了，问就是在模 $p$ 下拿同余式解后直接lift~~

故对于任意群 $G$ 上的离散对数问题，其难解性是与其最大素因子 $p_{i}$ 紧密相关的——若 $\max{p_{i}}$ 过小，则攻击者通过在小阶子群上解DLP即可“拼凑”出原问题的解，此所谓Pohlig-Hellman攻击（亦称小子群攻击）。
另外若一个群阶的小因子过多，只要其积大于（或略小于）$x$ 的上界，由CRT可知其较小模的“既有通解”就是特解。

由于DLP问题在密码学应用的广泛性，在不同群上的DLP为抵抗该攻击均需精心设计参数：

$Z_{p}$ 要求 $p$ 为强质数，即 $p-1$ ~~其实还有 $p+1$ 必须至少有一个大因子~~（其一定有一个因子 $2$，不过此点无伤大雅，较简易的生成强质数的方式之一就是随机选取素数 $p$ 并检验 $2p+1$ 是否为质数）。~~补档：好像这个是防RSA的光滑数攻击的~~
$E$ 要求计算得曲线的阶 $|E|$ 为质数，防止构造子群攻击。

对于EC-DLP亦需在应用时增加点的校验来防止无效曲线攻击，即检验待加密的点是否在给定的曲线上。
简化的椭圆曲线点运算系统（尤其在计算资源有限的小型设备上），为追求效率最大化会常会直接利用传入的点参数进行计算。参考椭圆曲线的点加规则，可以发现其群性质只依赖于参数 $(x,y,a,p)$，而附加常数 $b$ 本质上被“隐藏”于 $(x,y)$ 中。
改变 $b$ 不会影响点加计算的逻辑，，相当于原设备会在另一条（$a,p$ 相同，$b$ 不同）的曲线上进行点的计算。
但通过更改 $b$，攻击者可以将这个点转移至更弱的椭圆曲线上，并进行涉及私钥（离散对数解）的点乘计算，在子群下得到足够多的 $x^{'} \bmod p_{i}$，最终通过CRT即可解出原解 $x$。
本质上，上述过程即为诱导拓展的Pohlig-Hellman攻击。

BSGS

若 $|G| = n$，则直接爆破 $G$ 上的DLP问题的时间复杂度为 $O(n)$，而其空间复杂度为 $O(1)$。
BSGS(Baby Step Giant Step，小步大步法)则是一种“分摊”时间和空间复杂度的方法：
将待求式转化至 $Q = x \cdot P \space{3} 0 \leq x < n$。则

$x = x_1 \cdot \lfloor \sqrt{n} \rfloor + x_0 \space{3} x_1,x_2 \leq \lceil \sqrt{n} \rceil$
计算 $\{P^{'}_{i}\} = \{x_0 \cdot P \forall x_{0} \leq \lceil \sqrt{n} \rceil\}$
再 $\forall x_1 \leq \lceil \sqrt{n} \rceil$，计算 $Q^{'} = x_{1} \cdot Q^{-1}$，若 $Q^{'} \in \{P^{'}_{i}\}$，则命中解 $x = x_1 \cdot \lfloor \sqrt{n} \rfloor + x_0$。

其中第三步“命中”校验可以采用访问时间复杂度为 $O(1)$ 的数据结构进行（散列表等）。
可以看出其通过将空间复杂度提高为 $O(\sqrt{n})$ 来将时间复杂度降低为 $O(\sqrt{n})$。

椭圆曲线

满足方程 \[y^2 = x^3 + ax + b \space{5} (x,y \in F, 4a^3 + 27b^2 \neq 0)\] 的点集合为椭圆曲线，通常选取 $x,y \in F_p$。

理论上 $x,y$ 亦可被定义在任意域中（密码学应用要求其为有限域）。

定义点集合 $E$ 上的结合法 $+$，$(E,+)$ 是一个交换群（Abel群）。

$\forall a,b \in E$，$(a + b) + c = a + (b + c)$（结合律），$a + b = b + a$（交换性）
单位元 $e = \mathbb{O}$，其是无穷远的一个点，$\forall P \in E, P + \mathbb{O} = P$
逆元 $a^{-1} = \begin{cases} \mathbb{O}, a = \mathbb{O} \\ (x,-y), a = (x,y) \neq \mathbb{O} \end{cases}$
加法规则：设 $A = (x_1,y_1), B = (x_2,y,2) \in E$，满足 \[A + B = \begin{cases} \mathbb{O}, y_1 + y_2 = 0 \\ (k^2 - (x_1 + x_2), k \cdot (x_1 - x_3) - y_1), y_1 + y_2 \neq 0 \end{cases} \text{其中}k = \begin{cases}\frac{y_2-y_1}{x_2-x_1}, A \neq B \\ \frac{3x_1^2 + a}{2y_1}, A=B \end{cases} \]
点只能进行数乘，$kP$ 即为 $k$ 个点之和，$P$ 在 $E$ 上的阶定义为使得 $nP = \mathbb{O}$ 最小正整数 $n$，同样有 $n | ord(E)$
$E$ 还是一个循环群，$\forall P \in E, nP = \mathbb{O}$~~不仔细看还以为这是环的表达式~~

AES

AES 的“字节”运算全部在有限域$F_{2^8}= \mathbb{F}_2[x]/(m(x))$ 下进行，其中 $m(x)=x^8+x^4+x^3+x+1$ 是 8 次不可约（也是本原）多项式。

注意形若 $F_{p^{n}}$ 的计算都不是对 $p^{n}$ 取模，事实上 $Z_{p^{n}}$ 亦无法构成一个域。
本质上，其是在模degree为8的多项式 $f$ 构成的商环 $F_{2}[X]/f$ 环下进行运算。
宏观上的“字节”由其对应多项式的系数“拼凑”而成（$p$ 进制转化），即：\[a_{i} = \sum_{i=0}^{7} s_{i}2^{i} \in F_{2^{8}} \Leftrightarrow \sum_{i=0}^{7} s_{i}x^{i} \in F_{2}[X] / (m(x))\]
如，$\text{0xab} = 171 = 2^7 + 2^5 + 2^3 + 2 + 1$，对应多项式 $a(x)=x^7+x^5+x^3+x+1$。

AES的商环诱导的代数运算结构：
对于加法，两个字节直接异或即可：对应多项式系数在 $\mathbb{F}_2$ 上相加—— $F_{2}$ 的优雅之处即在此，无进/借位。
对于乘法，转化为多项式乘法后对 $m(x)$ 取模。转化为宏观“字节”的计算，可以采用快速乘的思想，溢出时的“魔数”模数为 $\text{0x1b} = 27$。
实现形如：

class Byte
{
    using value_t = unsigned char;
public:
    static constexpr void _gf256_mul(value_t& x, unsigned long long y)
    {
        value_t res = 1, mul = x;
        while(y)
        {
            if(y&1)
            {
                res *= mul;
                res ^= (res >> 2 ? 0x1b : 0x00);
                res &= 0xff;
            }
            mul *= mul;
            mul ^= (mul >> 2 ? 0x1b : 0x00);
            mul &= 0xff;
        }
        x = res;
    }

    friend constexpr Byte operator+(Byte x,Byte y)
    {
        return Byte(x.value^y.value);
    }

    //...

private:
    value_t value;

};

$\forall a \neq e, \exists a^{-1} \in GF(2^{8}), a \cdot a^{-1} = 1$，即对于0x00外的元素，乘法逆元存在且唯一（为保证兼容，AES定义了0x00的逆元为其自身，进而其在S-Box内的映射为0x63，推导见下）。
同时由于定义域和值域很小，因此实际的AES实现中常会预计算乘法表以加快运行速率。

AES的几个组件都依赖于元素在 $GF(2^{8})$ 上的矩阵/向量运算，其中元素对应的向量是 $GF(2)$ 上定义的 $8 \times 8$ 矩阵，一般按低位优先(LSB)顺序排列。
三种表示方式（字节值、多项式、向量）的转化示例：\[ 232 = 2^{3} + 2^{5} + 2^{6} + 2^{7} \in GF(2^{8}) \leftrightarrow x^{3} + x^{5} + x^{6} + x^{7} \in F_{2}[x] / (x^8 + x^4 + x^3 + x + 1) \leftrightarrow \begin{bmatrix} 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \end{bmatrix}^{T}\]
如记S-Box的双射为 $f: GF(2^{8}) \rightarrow GF(2^{8})$，则 $f(x) = x^{-4} + x^{-3} + x^{-2} + x^{-1} + 63$~~不先替换一下逆元就直接表达be like~~
其对应的矩阵乘法形式为：\[\begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{bmatrix} \cdot \begin{bmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \\ b_4 \\ b_5 \\ b_6 \\ b_7 \end{bmatrix} + \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{bmatrix}\]

LFSR

LFSR，Linear Feedback Shift Register，线性反馈移位寄存器，其广泛应用于流密码序列的生成。
整个LFSR可以视为在 $F_{2}[X]/f_q$ 下运行的多项式商环（其和另一种解析LFSR的方式，即 $F_{2}$ 下的矩阵运算是同构的）。

具体地，假设反馈值 \[s_{n} = \sum_{i=0}^{n-1} f_{i}s_{i} \bmod 2\]
矩阵形式下，其亦可表示作 \[s_{n} = \begin{bmatrix} f_{n-1} & f_{n-2} & \cdots & f_{0} \end{bmatrix} \cdot \begin{bmatrix} s_{n-1} & s_{n-2} & \cdots & s_{0} \end{bmatrix}^{T} \]

若从 $F_{2}[X]/f_q$ 的角度出发，每个状态下的多项式可以表示为 \[f_{k} = \sum_{i=0}^{n-1} s_{i}x^{i}\]
令 \[f_q = \sum_{i=0}^{n-1} f_{i}x^{i}\]
推导多项式为 \[f_{k+1} = x \cdot f_{k} \bmod f_q\]

其和多项式环相关知识的关联：

欲令该生成器的数列（即结果多项式）的周期最大，$f_q$ 应为本原多项式，理论最大周期与该多项式环的阶一致，为 $2^{n} - 1$（从矩阵亦可推导之，相互校验）
若 $f_q$ 是可约的，则其周期与其因式的阶有关，可以根据中国剩余定理推导之
即使多项式是本原的，若起始的多项式 $f_{0}$ 选择不当（即其不是 $F_{2}/f_q$ 的生成元），其生成序列的周期依然小于 $|F_{2}/f_q|$