第6章-近世代数基础

• 第 6 章：近世代数基础

  不要被“近世代数”这个名字吓到。这章在期末考试里，本质上就是让你**“在只有 0 和 1 的世界里，重新做一遍小学的加减乘除”**。

  这章没有复杂的逻辑，只有死规定。你只要把这套“外星人的算术规则”记住，这章就是纯纯的送分题。

  ---

  一、群、环、域：考场上的“查户口”指南

  考题经常问：“证明某某集合是一个群/环/域”。别慌，这是八股文，照着模板写就行。

  1. 群（Group）：只会一种法术（比如加法）

  要证明是群，必须满足 4 个条件（口诀：封、结、幺、逆）：

  1. 封闭性：集合里挑两个数相加，结果还在集合里。
  2. 结合律：(a+b)+c = a+(b+c)（这句废话写上就得分）。
  3. 单位元（幺元）：存在一个数（比如 0），加上它等于没加。
  4. 逆元：每个数都有个“死对头”，俩人一加就变成单位元（比如 a 的死对头是 -a）。

  2. 环（Ring）：会加减，还会乘，但不一定能除

  环 = 加法是个群 + 能做乘法。 比如：整数集合 Z 就是环。你能算 2×3，但你算 1÷2 就得不到整数了。

  3. 域（Field）：全能真神，加减乘除随便玩

  域 = 环 + 所有非 0 元素都能除（都有乘法逆元）。 密码学最喜欢“域”，因为有了逆元，方程 $ax=b$ 才能解。

  考试送分题结论： 模 p 的整数集合（p必须是素数）是一个域，记作 Fₚ。 如果 p 不是素数，它就只是个环，不是域！

  ---

  二、F₂[x] 的终极法则：1 + 1 = 0

  F₂[x] 意思是：系数只能是 0 或 1 的多项式。 在这个世界里，你必须洗脑自己接受一件事：

  ☠️ 终极法则：相同项直接湮灭！

  在 F₂ 里，1 + 1 = 0！ 这意味着，加法和减法是一模一样的！这里没有负号！ 两个相同的多项式相加，结果直接是 0（互相抵消了）。

  例题：(x³ + x + 1) + (x³ + x² + 1) 不要去列竖式了，考场上直接用笔把相同的项划掉！ x³ 和 x³ 划掉！1 和 1 划掉！ 剩下啥就是啥，答案：x² + x。就这么简单！

  ---

  三、不可约多项式判定：考场 3 步秒杀流水线

  不可约多项式，就是多项式里的“素数”，不能再往下拆了。 怎么判断一个长长的多项式是不是不可约？绝大多数题目，用下面 3 步流水线直接秒杀！

  第一步：看常数项是不是 1？

  如果没有 +1 结尾（比如 $x^5+x^2+x$），说明大家都能提取一个 $x$ 出来，绝对可约！

  鉴定：没有常数项 1 的，直接死刑。

  第二步：数一数项数是不是偶数个？

  （比如 $x^3+x^2+x+1$，一共 4 项） 在 F₂ 里，只要项数是偶数个，把 $x=1$ 代进去，结果一定是 $1+1+...+1=0$。说明含有因子 $(x+1)$。

  鉴定：总项数是偶数个的，直接死刑。

  第三步：长除法查低次不可约因子（仅限 4 次及以上）

  如果经过前两步，它（1）有常数项，（2）有奇数项（比如 3 项或 5 项），说明它没有一次因子。

  • 如果是 2 次或 3 次多项式：通过了前两步，它百分之百不可约！（比如 $x^2+x+1$ 和 $x^3+x+1$）
  • 如果是 4 次或 5 次多项式：它还有可能拆成 $2\mathrm{次}\times 2\mathrm{次}$ 或 $2\mathrm{次}\times 3\mathrm{次}$。 你只需要用唯一的 2 次不可约多项式 $x^2+x+1$ 去做一次长除法，除不尽（有余数），就宣布它不可约！

  综合例题：判断 $x^5+x^2+1$ 是否不可约。

  1. 有没有常数项？有 +1。（过关）
  2. 数项数：共 3 项，奇数个。（过关，说明没一次因子）
  3. 长除法：用 $x^5+x^2+1$ 除以 $x^2+x+1$。除完发现有余数。（过关） 结论：不可约！

  ---

  四、GF(2ⁿ) 运算：自带降压药的乘法

  GF(2ⁿ) 意味着我们要找一个 n 次不可约多项式 $f(x)$ 当作“模”。 所有运算结果，只要次数达到 n，就要被强行降级。

  考场开挂准备工作：手写“降维表”

  假设考题说：在 GF(2⁴) 中，使用模多项式 $f(x)=x^4+x+1$。 做任何计算前，先在草稿纸上写下：$x^4+x+1=0⟹x^4=x+1$ 然后顺手推算出 $x^5$ 和 $x^6$：

  $x^4=x+1$

  $x^5=x\cdot x^4=x(x+1)={\mathbf{x}}^{\mathbf{2}}\mathbf{+}\mathbf{x}$

  $x^6=x\cdot x^5=x(x^2+x)={\mathbf{x}}^{\mathbf{3}}\mathbf{+}{\mathbf{x}}^{\mathbf{2}}$(有了这三行，后面的乘法直接查表替换，大脑完全不需要思考！)

  例题：计算 (x² + 1) × (x³ + 1)

  第一步：闭着眼睛乘开。$=x^5+x^2+x^3+1$ 整理一下顺序：$={\mathbf{x}}^{\mathbf{5}}\mathbf{+}{\mathbf{x}}^{\mathbf{3}}\mathbf{+}{\mathbf{x}}^{\mathbf{2}}\mathbf{+}\mathbf{1}$

  第二步：查表降维。 一查表，里面混进了个 $x^5$，查表得知 $x^5=x^2+x$。把它替换掉！ $=({\mathbf{x}}^{\mathbf{2}}\mathbf{+}\mathbf{x})+x^3+x^2+1$

  第三步：相同项湮灭！ 式子里有两个 $x^2$，划掉！ 答案直接出来：$x^3+x+1$。

  ---

  五、💥 GF(2ⁿ) 求逆元：多项式表格法绝杀

  求 $(x^2{)}^{-1}(\mathrm{mod}{x}^4+x+1)$。 书上是用长篇大论的扩展欧几里得倒推，考场上写多项式倒推必错无疑！ 这里教你把整数的神奇表格法，完美平移到多项式上！

  规则和第一章一模一样：当前行 = 上上行 + 商 × 上一行(注意：在 F₂ 里，减法就是加法，所以直接用加号，连负号都不用管，简直爽翻！)

  例题：求 $(x^2{)}^{-1}(\mathrm{mod}{x}^4+x+1)$

  行号	商 q	余数 r	逆元列 y	考场草稿计算过程（不用写）
  -1	无	x⁴+x+1	0	(写死，模多项式)
  0	无	x²	1	(写死，要求逆的多项式)
  1	x²	x+1	x²	q: $x^4+x+1$ 除以 $x^2$，商 $x^2$ 余 $x+1$ y: $0+x^2\cdot 1=x^2$
  2	x+1	1	x³+x²+1	q: $x^2$ 除以 $x+1$，商 $x+1$ 余 1 y: $1+(x+1)\cdot x^2=x^3+x^2+1$

  算到余数 r = 1 停止，看最后一行的 y，答案直接出来了：

  $(x^2{)}^{-1}=x^3+x^2+1$

  全程没有一个减号，没有一行回代，清清爽爽拿到满分！

  (附注怎么做多项式短除法求商和余数：比如行1里，$(x^4+x+1)/x^2$，最高次 $x^4/x^2=x^2$。然后 $x^4+x+1+x^2(x^2)=x+1$，余数就是 $x+1$。就这么简单。)

  ---

  六、送分概念题速记

  遇到填空题或判断题，直接写：

  1. 加法恒等元（单位元）：永远是 0。
  2. 乘法恒等元（单位元）：永远是 1。
  3. 如果密码学算法（如 AES）选了 GF(2⁸)，那它的每个元素都可以用一个 8 位的二进制字节（Byte） 来表示。比如 $x^2+1$ 就是 00000101。

  ---

  🚀 本章做题速查表（考前 5 分钟必看）

  你要做什么	考场无脑流水线
  F₂[x] 加法计算	找相同的，直接划掉！划掉！
  判定不可约	1. 没 $+1$ 的直接死；2. 项数是偶数的直接死；3. 四次以上除以 $x^2+x+1$。
  GF(2ⁿ) 乘法计算	先写出 $x^n,x^{n+1}...$ 的降维替换表。乘开 $\to$ 查表替换 $\to$ 划掉相同的。
  求多项式逆元	画表格，用 当前 = 上上 + 商 × 上一（全程用加号）。

  ---

  ☠️ 历年期末最惨烈翻车现场

  1. 脑子里还有负号：做减法时还写出 $-x^2$，F₂ 里面只有 0 和 1！$-x^2$ 就是 $+x^2$，相减就是相加，相同的直接划掉。
  2. 乘法没降维彻底：查表把 $x^5$ 换成了 $x^2+x$，但没注意到式子里还有个 $x^4$，忘了 $x^4$ 也要换成 $x+1$。结果里绝对不能出现最高次及以上的项。
  3. 不可约判定漏判高次：看 $x^4+x^2+1$ 有常数项，而且是 3 项（奇数），就直接喊不可约。其实它等于 $(x^2+x+1)(x^2+x+1)$！4次以上的必须用除法验一下。

  ---

  自测题（没做对别进考场）

  1. 在 F₂[x] 中计算：$(x^3+x^2+x)+(x^2+x+1)$。
  2. 快速判断 $f(x)=x^4+x^3+x+1$ 是否可约？（提示：数一数项数）。
  3. 假设 GF(2⁴) 模多项式是 $x^4+x+1$，计算 $x\cdot x^3$ 的结果。
  4. （压轴必考） 用表格法，在 $f(x)=x^4+x+1$ 下求 $x^3$ 的逆元。

  ---

  自测答案

  1. 直接划掉相同的 $x^2$ 和 $x$。答案：$x^3+1$。
  2. 一共 4 项（偶数个）。代入 $x=1$ 得 $1+1+1+1=0$。有因子 $x+1$，可约！
  3. $x\cdot x^3=x^4$。在模 $x^4+x+1$ 下，直接查表降维，答案是 $x+1$。
  4. 画表： 第一行：x⁴+x+1, y=0 第二行：x³, y=1 第三行(做除法)：商 x，余数 x+1。$y=0+x(1)=$ x 第四行(做除法)：$x^3/(x+1)$ 商 $x^2+x+1$，余 1。$y=1+(x^2+x+1)(x)=$ x³+x²+x+1 余数到 1 停止，逆元是 $x³+x²+x+1$。（表格法绝不翻车！）