Appearance
第 6 章：近世代数基础
先给你一个定心丸：这章名字吓人，但期末考的基本就是"在多项式里做加减乘除"——跟你小学学的算术几乎一样，只是规则稍微变了一下。
和信息安全有什么关系？AES 加密、椭圆曲线、很多密码算法的底层运算，就是在这些东西上跑的。你不会手算 AES，但你得知道它在什么"数学世界"里运行。
一、群、环、域：三个"数学世界"的入门规则
这三个词本质上是在规定一个集合里的"游戏规则"——你能做什么运算、做完了还在不在这个集合里、能不能反着来。
群：只有一种运算，但很规矩
一个集合 G 配上一种运算（比如 + 或 ×），满足 4 条规矩，就叫群：
| 规矩 | 说人话 |
|---|---|
| 封闭 | 集合里随便拿两个出来算，结果还在集合里 |
| 结合 | (a 算 b) 算 c = a 算 (b 算 c)，次序不碍事 |
| 有单位元 | 存在一个"啥也不改变"的元素 |
| 有逆元 | 每个元素都有一个能把它"消回"单位元的搭档 |
最好的例子：整数 Z 配上加法。
- 封闭：整数 + 整数 = 整数 ✓
- 结合：(1+2)+3 = 1+(2+3) ✓
- 单位元：0，因为 a+0 = a ✓
- 逆元：整数 a 的逆元是 -a，因为 a+(-a) = 0 ✓
所以 整数关于加法构成群。
为什么整数关于乘法不是群？
前三条都 OK——整数乘整数还是整数，有结合律，单位元是 1。但逆元挂掉了。
比如 2，它的乘法逆元应该是 1/2，但 1/2 不是整数，不在集合里。
群要求每个元素都有逆元，且逆元必须在集合里。 整数乘法这条不满足。
环：能加能减能乘，不一定能除
环比群多一种运算：有加法也有乘法。整数 Z 就是环的经典例子——你可以加、减、乘，但除就不一定了（1÷2 拿不出整数结果）。
一句话：环 = 加法群 + 乘法，乘法可以没有逆元。
域：什么都能干，非零元素都能除
域是最高待遇：能加、能减、能乘、非零元素还能除（每个非零元素都有乘法逆元）。
| 结构 | 能干嘛 | 例子 |
|---|---|---|
| 群 | 一种运算（能 "反着来"） | Z 关于加法 |
| 环 | 加减乘 | Z 关于加法和乘法 |
| 域 | 加减乘除（非零可除） | 有理数 Q，模素数 p 的整数 Fₚ |
记忆法
群像单车道（一种运算），环像双车道但没掉头（加减乘），域像高速公路全互通（加减乘除齐全）。
群 → 环 → 域，一个比一个功能全。
二、模 p 的整数是一个域：Fₚ
当 p 是素数时，{0, 1, 2, ..., p-1} 在模 p 加法和乘法下构成一个域，记作 Fₚ。
以 F₅ = {0, 1, 2, 3, 4} 为例：
| 元素 | 加法逆元 | 乘法逆元 |
|---|---|---|
| 0 | 0 | 没有（0 在任何域里都没有乘法逆元） |
| 1 | 4 | 1（1×1=1） |
| 2 | 3 | 3（2×3=6≡1） |
| 3 | 2 | 2（3×2=6≡1） |
| 4 | 1 | 4（4×4=16≡1） |
每个非零元素都有乘法逆元，所以 F₅ 是域。
这也是为什么 RSA 里 p 和 q 要取素数——因为只有当模数是素数时，每个非零元素才有逆元，方程组才能正常解。
三、F₂[x]：系数只能是 0 或 1 的多项式世界
F₂ 只有两个数：0 和 1。
在 F₂ 里，加法和乘法都模 2。最重要的规则：
1 + 1 = 0（因为 2 ≡ 0 mod 2）
这是本章最重要的规则
整个 F₂[x] 和 GF(2ⁿ) 的运算基础就是这条。忘了它，后面的加减乘除全乱。
F₂[x] 就是"系数只能取 0 或 1 的多项式集合"。比如：
x⁴ + x + 1 ← 系 数：1, 0, 0, 1, 1，全 0 或 1 x³ + x² + 1 ← 一样
四、F₂[x] 里的加法：相同项出现两次就消失
规则：同类项合并，系数模 2。因为 1+1=0，所以相同项成对消失。
例题：(x³ + x + 1) + (x³ + x² + 1)
按次数对齐：
| 项 | 第一个多项式 | 第二个多项式 | 相加 |
|---|---|---|---|
| x³ | 1 | 1 | 1+1=0（消失） |
| x² | 0 | 1 | 1（保留） |
| x¹ | 1 | 0 | 1（保留） |
| 常数 | 1 | 1 | 1+1=0（消失） |
剩下 x² + x，所以答案：
(x³ + x + 1) + (x³ + x² + 1) = x² + x
直观记忆：两个一样的项放一起就互相抵消，跟正反物质湮灭似的。
五、不可约多项式：多项式里的"素数"
整数里有素数——不能拆成更小的整数相乘。多项式里也有对应的概念，叫不可约多项式——不能拆成两个次数更低的多项式相乘。
怎么判断低次不可约？
在 F₂[x] 里，一次多项式只有两个：x 和 x+1。
所以判断一个多项式有没有一次因子，只需要：
代入 x = 0：如果 f(0) = 0，说明 x 是因子 代入 x = 1：如果 f(1) = 0，说明 x+1 是因子
两个都不是 0 → 没有一次因子。
为什么？
在 F₂ 中，如果 f(x) 有因子 x，就意味着 x 能整除 f(x)，等价于 f(0) = 0。类似地，因子 x+1 能整除 f(x) 等价于 f(1) = 0。
例题：判断 f(x) = x⁵ + x² + 1 是否不可约
检查一次因子：
f(0) = 0⁵ + 0² + 1 = 1 ≠ 0 → 没有因子 x ✓
f(1) = 1⁵ + 1² + 1 = 1 + 1 + 1 = 3 ≡ 1 (mod 2) ≠ 0 → 没有因子 x+1 ✓
检查高次因子：5 次多项式如果可约，除了有一次因子，还可能拆成 2 次 × 3 次。所以还需要检查能否被二次不可约多项式整除。
在 F₂[x] 中，唯一的二次不可约多项式是 x² + x + 1（因为 x²、x²+1 = (x+1)²、x²+x = x(x+1) 都是可约的）。
用 x² + x + 1 去除 f(x)：余数不为 0 → 不能被它整除。
结论：x⁵ + x² + 1 是不可约多项式。
几个常见不可约多项式的结论（可以直接记）
| 多项式 | 判定 |
|---|---|
| x⁶ + x + 1 | 不可约 |
| x⁵ + x² + 1 | 不可约 |
| x⁸ + x⁴ + x³ + x + 1 | 不可约 |
| x⁴ + x + 1 | 不可约（GF(2⁴) 用的模多项式） |
六、GF(2ⁿ)：次数受限的多项式世界
GF(2ⁿ) = F₂[x] / (f(x))，其中 f(x) 是一个 n 次不可约多项式。
翻译成大白话：
你在 F₂[x] 里算多项式，但所有结果都要除以 f(x) 取余数。最后留下的，都是次数小于 n 的多项式。
GF(2⁴) 的例子
取 f(x) = x⁴ + x + 1（4 次，不可约）。
那么 GF(2⁴) 里的所有元素形如：
a₃x³ + a₂x² + a₁x + a₀，每个系数 aᵢ ∈
每个位置 2 种选择，4 个位置 = 2⁴ = 16 个元素。
比如：0、1、x、x+1、x²、x²+1、x²+x、x²+x+1、x³、x³+1、...
七、GF(2⁴) 的核心替换规则：x⁴ = x + 1
因为模多项式是 x⁴ + x + 1，而我们把它当作 0：
x⁴ + x + 1 = 0
在 F₂ 中，加法和减法是一回事（因为 1+1=0，所以加就是减），所以移项：
x⁴ = x + 1 ← 本章第二重要的规则！
任何出现 x⁴ 或更高次的项，都要用这条规则降下来。比如：
x⁵ = x × x⁴ = x × (x+1) = x² + x
x⁶ = x² × x⁴ = x² × (x+1) = x³ + x²
等等。每次乘完如果次数 ≥ 4，就用 x⁴ = x+1 降压。
八、GF(2⁴) 中的加法：还是一样的抵消规则
加法不需要 x⁴ = x+1 那条规则（因为加法不会升高次数）。跟 F₂[x] 的加法完全一样：同类项合并，相同项抵消。
例题：(x³ + x + 1) + (x² + x + 1)
| 项 | 第一个 | 第二个 | 结果 |
|---|---|---|---|
| x³ | 1 | 0 | 1 |
| x² | 0 | 1 | 1 |
| x | 1 | 1 | 0（抵消） |
| 常数 | 1 | 1 | 0（抵消） |
答案：x³ + x²。
九、GF(2⁴) 中的乘法：先乘再降
乘法分两步：
- 像普通多项式一样乘开
- 凡是次数 ≥ 4 的项，用 x⁴ = x+1 降压
例题：(x²+1)(x³+1)
第一步：普通展开。
(x²+1)(x³+1) = x²·x³ + x²·1 + 1·x³ + 1·1 = x⁵ + x² + x³ + 1
按次数排列：x⁵ + x³ + x² + 1。
第二步：x⁵ 次数太高，降！
x⁵ = x × x⁴ = x × (x+1) = x² + x。
代入原式替换 x⁵：
(x² + x) + x³ + x² + 1
第三步：合并同类项。
x² + x² = 0（抵消）
剩下：x³ + x + 1
答案：(x²+1)(x³+1) = x³ + x + 1。
十、GF(2⁴) 中求逆：找多项式使其乘积为 1
求 a(x)⁻¹ mod f(x)，就是要找 g(x) 使得：
a(x) × g(x) ≡ 1 (mod f(x))
本质上和整数求逆元一模一样——只是把整数换成了多项式。手段也是扩展欧几里得算法（多项式的版本）。
例题：求 (x²)⁻¹ mod (x⁴+x+1)
这道题告诉你答案，然后手把手验证——考试更多是验证而不是从零求逆。
据说逆元候选：g(x) = x³ + x² + 1。
验证：
第一步：相乘。
x² × (x³ + x² + 1) = x⁵ + x⁴ + x²
第二步：降压。
x⁴ = x + 1 x⁵ = x² + x（前面算过）
代入：
(x² + x) + (x + 1) + x²
第三步：合并。
x² + x² = 0 x + x = 0 剩：1
x² × (x³+x²+1) ≡ 1 ✓
所以 (x²)⁻¹ = x³ + x² + 1。
再验证一个：(x³)⁻¹
据说答案是 x³ + x² + x + 1。
验证：
x³ × (x³ + x² + x + 1) = x⁶ + x⁵ + x⁴ + x³
降压：
x⁴ = x + 1 x⁵ = x² + x x⁶ = x³ + x²（x⁶ = x² × x⁴ = x²(x+1) = x³ + x²）
代入：
(x³ + x²) + (x² + x) + (x + 1) + x³
合并：
x³ + x³ = 0 x² + x² = 0 x + x = 0 剩：1
所以 (x³)⁻¹ = x³ + x² + x + 1 ✓。
十一、加法恒等元和乘法恒等元（送分题）
考到就是送分：
加法恒等元：加上它不变的 → 永远是 0乘法恒等元：乘上它不变的 → 永远是 1
在任何 GF(2ⁿ) 里都是这两个答案。背下来，看到就写。
本章做题速查表
| 看到什么 | 立刻想 |
|---|---|
| 判断是不是群 | 四条规则逐条查（封闭、结合、单位元、逆元） |
| 域和环的区别 | 域 = 环 + 非零元素能除 |
| F₂[x] 加法 | 同类项合并，1+1=0，相同项消失 |
| F₂[x] 判断不可约 | 先代 x=0, x=1 查一次因子，再看低次不可约因子 |
| GF(2⁴) 乘法 | 先普通乘开，再用 x⁴=x+1 降压 |
| 求逆 | 扩展欧几里得（多项式版），或直接验证乘积=1 |
| 恒等元 | 加法恒等元 = 0，乘法恒等元 = 1 |
最容易翻车的地方
- 忘了 1+1=0。这是 F₂ 的基本规则，每次做加法都要先想这条。两个一样的项直接划掉。
- x⁴ = x+1 这条规则记错了。注意是 x⁴ = x+1，不是 x⁴ = x⁴+1 之类的。这是从 x⁴+x+1=0 移项来的。
- 降压时忘了继续降。比如 x⁶ 降了一次变成 x³+x²，如果里面还有 ≥ 4 次的项还要继续降，不过一般降一次就够了。
- 群和环和域的定义搞混。建议画个 Venn 图记忆：域 ⊂ 环 ⊂ 群。
- 不可约多项式的判断忘了查高次因子。没有一次因子不等于不可约，还可能是 2×3、2×2 等分解。
自测题
- 用自己的话解释群的定义。（不需要背课本，说清楚四个条件就行）
- 整数 Z 在乘法下是群吗？为什么？
- 在 F₂[x] 中计算：(x³ + x + 1) + (x³ + x² + 1)
- 判断 x⁵ + x² + 1 是否是 F₂[x] 中的不可约多项式。
- 在 GF(2⁴) 中计算：(x² + 1)(x³ + 1)
- 在 GF(2⁴) 中，验证 (x²)⁻¹ = x³ + x² + 1。
自测答案
- 一个集合配一种运算，满足：① 封闭——集合内任取两元素运算结果还在集合里；② 结合律——(ab)c = a(bc)；③ 有单位元——存在 e 使得 ae = ea = a；④ 每个元素都有逆元——对每个 a 存在 a⁻¹ 使得 a·a⁻¹ = e。
- 不是。因为整数 2 的乘法逆元是 1/2，不在整数集合里（逆元不封闭）。
- x² + x。
- 是不可约多项式。
- x³ + x + 1。
- x² × (x³+x²+1) = x⁵+x⁴+x²，用 x⁴=x+1、x⁵=x²+x 降压后合并得 1。验证通过。