多项式枚举、LFSR与AES选型)
第一次在项目里认真查"不可约多项式"这个词，是因为一段 LFSR 代码的输出周期只有理论值的三分之一——反馈抽头明明是从手册上照抄的，序列却在几十个时钟周期之后就重复了。当时把特征多项式拎出来一算才发现：那个多项式在 GF(2) 上确实满足"不可约"，但它的根只能生成 5 个非零元，离满周期 2^4−1=15 差得远。也就是说，不可约多项式并不等于本原多项式，前者只是后者的必要门槛。那次之后我把这两个概念彻底拆开重学了一遍，顺手把所有低次的情形都手算枚举了一遍，这篇就是那段时间的笔记整理。
内容会覆盖：有限域上多项式除法的手算方法、不可约性的三种判定路径、GF(2) 上 2 到 5 次不可约多项式的完整枚举、本原多项式的阶判定与逐项验算、GF(3) 上的对照例子、一份可以直接跑的 Python 实现，最后是 LFSR、CRC、AES 这些真实场景里选型时容易踩的坑。适合正在做通信扰码、纠错编码、序列密码、硬件随机数发生器，或者单纯想把这部分数学基础补扎实的人。所有结论我都尽量配上可以自己动笔复算的计算过程，而不是只丢一张表。
1. 多项式除法的基本功：手算之前先把"除得尽"讲清楚
1.1 GF(p)[x] 里加法和减法是一回事，但系数必须模 p
讨论不可约性，所有运算都发生在有限域 GF(p) 上的多项式环 GF(p)[x]里。这个环的元素是形如 a_n x^n + ... + a_1 x + a_0 的多项式，系数 a_i 取自 {0, 1, ..., p−1}，加减乘全部按模 p 进行。一阶不可约多项式就是 x + c 这种形式，因为它的根是 −c，一定在 GF(p) 里。
最常用的是 p = 2，也就是系数只有 0 和 1 的情形。这里有个必须记住的性质：加法就是异或，减法也是异或。原因很简单，−1 ≡ 1 (mod 2)，所以 x 减 y 和 x 加 y 的结果完全一样。这个性质让 GF(2) 上的所有手算都变得异常顺手——长除法里不用考虑"借位"，直接按位异或就行。很多人在 GF(2) 上手算出错，恰恰是因为脑子里还残留着十进制减法的直觉。
p = 3 的时候就要小心了。系数在 {0,1,2} 里，−1 ≡ 2，−2 ≡ 1，所以 x^2 + 1 在 GF(3) 上的"负"是 2x^2 + 2，而不是 −x^2 − 1 那种写法。手工算 GF(3) 的除法时，每一步都要把系数落回 {0,1,2}，不然很容易在中间步骤丢一个负号。
另外要明确一个术语约定：我们讨论"不可约"时，默认只讨论首一多项式（最高次项系数为 1）。因为任何一个多项式乘以非零常数都不改变它的可除性，把首一作为唯一标准可以让枚举和计数干净很多。GF(p) 上 n 次首一多项式一共有 p^n 个，这个数字后面会反复用到。
1.2 长除法手算模板：两个能背下来的例子
不可约判定的第一步永远是试除，而试除依赖长除法。这里给两个我练手时反复用的例子。
例 1（GF(2)）：计算 (x^4 + x^3 + x^2 + x + 1) ÷ (x^2 + x + 1)。
被除式最高次是 4，除式最高次是 2，商的首项是 x^2。用 x^2 乘除式：
x^2 · (x^2 + x + 1) = x^4 + x^3 + x^2
与被除式相减（GF(2) 上就是异或）：
(x^4 + x^3 + x^2 + x + 1) ⊕ (x^4 + x^3 + x^2) = x + 1
余式 x + 1 的次数 1 小于除式次数 2，除法结束。结果：
x^4 + x^3 + x^2 + x + 1 = (x^2 + x + 1) · x^2 + (x + 1)
因为余式非零，说明 x^2 + x + 1 不是它的因子。这一步在后面判定 x^4+x^3+x^2+x+1 的不可约性时还会再出现。
例 2（GF(3)）：计算 (x^3 + 2x + 1) ÷ (x + 2)。
商首项 x^2，x^2 · (x + 2) = x^3 + 2x^2，相减（普通减法，系数模 3）：
(x^3 + 0x^2 + 2x + 1) − (x^3 + 2x^2) = −2x^2 + 2x + 1 ≡ x^2 + 2x + 1
商次项 x，x · (x + 2) = x^2 + 2x，再减：
(x^2 + 2x + 1) − (x^2 + 2x) = 1
所以 x^3 + 2x + 1 = (x + 2)(x^2 + x) + 1。用综合除法验算更快：多项式在 x = −2 ≡ 1 处的值 f(1) = 1 + 2 + 1 = 4 ≡ 1，与余式吻合。余数定理在有限域上同样成立，这一点非常有用——判断某个一次式 x − a 是不是因子，只需要代入 a 算一下值，不用真的做除法。
1.3 一个让我少算了无数遍的小技巧
在 GF(2) 上，判断 x + 1 是不是 f(x) 的因子，等价于判断 f(1) 是否为 0。把 1 代进去，每一项都变成 1，所以 f(1) 就是所有系数在 GF(2) 中的和，也就是"非零项个数的奇偶性"。
结论直接记住：GF(2) 上只有奇数个非零项的多项式才可能不可约。非零项个数是偶数的，一定被 x + 1 整除，一定是可约的。
回头看前面例 1 里的 x^4+x^3+x^2+x+1，非零项 5 个，奇数，所以它至少躲过了 x+1 这一关。而 x^4+x^3+x+1 有 4 个非零项，偶数，立刻可以断定它可约，事实上它等于 (x+1)^2(x^2+x+1)。这个判据能在枚举时帮你砍掉一半候选，值不值得单独记，你自己算两轮就知道了。
2. 不可约性的三重判定：求根、试除、Rabin 各管一段
2.1 次数不超过 3 时，求根法就是全部
先给结论：在 GF(p) 上，次数为 2 或 3 的多项式不可约，当且仅当它在 GF(p) 中没有根。
理由是分解次数：一个 2 次多项式如果真的能分解，只可能是 1+1；一个 3 次多项式如果真的能分解，只可能是 1+2。两种情况下都必然存在一个一次因子，而一次因子 x − a 存在等价于 f(a) = 0。所以只要把 GF(p) 里所有 p 个元素挨个代进去试一遍，没有根就是不可约。
GF(2) 上更省事，只需要试 0 和 1，也就是看常数项是不是 0、非零项个数是不是奇数。GF(3) 上试 0、1、2 三个值。
但这条规则到 4 次就失效了，这是新手最容易翻车的地方。反例现成的：x^4 + x^2 + 1 在 GF(2) 上没有根（f(0) = 1，f(1) = 1），但它是 (x^2 + x + 1)^2，彻底可约。因为你完全可以把 4 次拆成 2+2，两个因子都没有根，但乘积有。求根法只在次数 ≤ 3 时是充分必要的，4 次及以上它只能用来排除有根的情形，不能用来确认不可约。
2.2 试除法：只需要试到 n/2 次
对 n 次首一多项式 f，如果它是可约的，那它一定有一个次数不超过 n/2 的不可约因子。所以理论上只需要拿所有次数 ≤ ⌊n/2⌋ 的首一不可约多项式去试除即可。
实际操作中我一般偷个懒：直接拿所有次数 ≤ ⌊n/2⌋ 的首一多项式（包括可约的）去试除。因为可约因子里必然含有不可约因子，多试几个不会改变结论，只是多算几步，但省掉了"先把低次不可约多项式筛出来"的准备工作。GF(2) 上 4 次多项式的试除只需要对付 x、x+1、x^2+x+1 三个（次数 ≤ 2 的首一式），工作量完全可以接受。
试除法的优点是直观、可手算、出错能被检查；缺点是次数一高就崩。8 次多项式要试除次数 ≤ 4 的所有首一多项式，GF(2) 上有 1+2+4+8+16 = 31 个，还能忍；到了 16 次、32 次，手工枚举就不现实了，需要换工具。
2.3 Rabin 检验：x^(q^n) − x 这条主线
真正能上规模的方法基于一条恒等式：
在 GF(q) 上，x^(q^n) − x 等于所有次数 d 整除 n 的首一不可约多项式的乘积（d 遍历 n 的所有正因子）。
这条式子把"不可约性"这件事翻译成了多项式整除关系。设 f 是 GF(q) 上次数 n > 0 的首一多项式，则f 不可约当且仅当同时满足：
- x^(q^n) ≡ x (mod f)；
- 对 n 的每一个素因子 r，都有 gcd(x^(q^(n/r)) − x, f) = 1。
条件 1 的作用是保证 f 没有重复因子、并且它的每个不可约因子的次数都整除 n；条件 2 则是踢掉那些次数严格小于 n 的真因子。两者合起来，剩下的只能是"次数正好等于 n 的单个不可约因子"，也就是 f 本身不可约。
拿 GF(2) 上 f = x^4 + x + 1 走一遍。n = 4，素因子只有 2。
条件 1 要验证 x^16 ≡ x (mod f)。前面算过 x^15 ≡ 1（这一节的结论在下一章会完整验算），两边乘 x 就得到 x^16 ≡ x，通过。
条件 2 要验证 gcd(x^4 − x, f) = 1。在模 f 的意义下 x^4 = x + 1，所以 x^4 − x = x^4 + x = (x + 1) + x = 1。gcd(1, f) = 1，通过。两步都过，f 不可约。
再看反例 f = x^4 + x^3 + x^2 + x + 1。条件 1 同样通过（它的根在某个扩域里的阶是 5，5 | 15，所以 x^16 ≡ x）。条件 2：x^4 + x 在模 f 下等于 (x^3 + x^2 + x + 1) + x = x^3 + x^2 + 1。计算 gcd(x^3 + x^2 + 1, x^4 + x^3 + x^2 + x + 1)，辗转相除几步之后得到 1，条件 2 也通过。所以它确实不可约——但注意，它不可约并不代表它是本原多项式，这正是下一章要展开的分水岭。
提示：Rabin 检验做的是多项式取模和多项式幂，全部可以用位运算加速，8 次、16 次的多项式在普通笔记本上都是毫秒级。手算只适合验证 4 次以内的情形，别硬扛。
3. GF(2) 上不可约多项式的全枚举：次数 2 到 5 一个一个筛
3.1 次数 2 和 3：手算穷尽所有候选
2 次首一多项式共 4 个，逐个来：
| 多项式 | 判定依据 | 结论 |
|---|---|---|
| x^2 | 等于 x · x | 可约 |
| x^2 + 1 | 等于 (x+1)^2，且 f(1) = 0 | 可约 |
| x^2 + x | 等于 x(x+1)，且常数项为 0 | 可约 |
| x^2 + x + 1 | f(0) = 1，f(1) = 1，无根 | 不可约 |
所以 2 次不可约多项式只有 1 个：x^2 + x + 1。
3 次首一多项式共 8 个。用"奇数个非零项"先砍：非零项个数必须是奇数，所以常数项必须是 1、并且 x^2 和 x 的系数里要有偶数个 1（1 个或 0 个）。满足条件的是这 4 个：
- x^3 + 1：等于 (x+1)(x^2+x+1)，可约；
- x^3 + x + 1：无根，不可约；
- x^3 + x^2 + 1：无根，不可约；
- x^3 + x^2 + x + 1：等于 (x+1)^3，可约。
2 个不可约多项式。这个数字和公式 (1/3)(2^3 − 2^1) = 2 吻合。
3.2 次数 4：16 个候选里的 3 个幸存者
4 次首一多项式一共 16 个，我把它们全部列出来。这一步不要跳，因为"哪些能被 2 次因子整除"的直觉必须靠这种穷举建立起来。
| 多项式 | 分解形式 | 结论 |
|---|---|---|
| x^4 | x·x·x·x | 可约 |
| x^4 + 1 | (x+1)^4 | 可约 |
| x^4 + x | x(x+1)(x^2+x+1) | 可约 |
| x^4 + x + 1 | 无低次因子 | 不可约 |
| x^4 + x^2 | x^2(x+1)^2 | 可约 |
| x^4 + x^2 + 1 | (x^2+x+1)^2 | 可约 |
| x^4 + x^2 + x | x(x^3+x+1) | 可约 |
| x^4 + x^2 + x + 1 | (x+1)(x^3+x^2+1) | 可约 |
| x^4 + x^3 | x^3(x+1) | 可约 |
| x^4 + x^3 + 1 | 无低次因子 | 不可约 |
| x^4 + x^3 + x | x(x^3+x^2+1) | 可约 |
| x^4 + x^3 + x + 1 | (x+1)^2(x^2+x+1) | 可约 |
| x^4 + x^3 + x^2 | x^2(x^2+x+1) | 可约 |
| x^4 + x^3 + x^2 + 1 | (x+1)(x^3+x+1) | 可约 |
| x^4 + x^3 + x^2 + x | x(x+1)^3 | 可约 |
| x^4 + x^3 + x^2 + x + 1 | 无低次因子 | 不可约 |
三个不可约多项式：x^4 + x + 1、x^4 + x^3 + 1、x^4 + x^3 + x^2 + x + 1。
其中 x^4 + x^3 + x^2 + x + 1 是最容易误判的一个。它没有一次因子（非零项 5 个，奇数），要确认它不可约必须排除 2 次因子。GF(2) 上唯一的 2 次不可约多项式是 x^2 + x + 1，我在 1.2 节已经算过它除这个多项式余 x + 1，非零。所以它确实不可约。反过来，x^4 + x^2 + 1 也是非零项 3 个、没有一次因子，试除 x^2 + x + 1 时余式为 0，直接判为可约——这两个只差一个 x^3 项，结论却完全相反，是最典型的对比案例。
3.3 次数 5：为什么 32 个候选里只剩 6 个
5 次首一多项式 32 个。先用奇数项条件砍：最高项固定为 1，剩下 5 个系数里 1 的个数必须是偶数，也就是 0、2、4 个，共有 C(5,0) + C(5,2) + C(5,4) = 1 + 10 + 5 = 16 个候选。再用试除法排掉所有被 2 次因子整除的，剩下 6 个不可约多项式：
- x^5 + x^2 + 1
- x^5 + x^3 + 1
- x^5 + x^3 + x^2 + x + 1
- x^5 + x^4 + x^2 + x + 1
- x^5 + x^4 + x^3 + x + 1
- x^5 + x^4 + x^3 + x^2 + 1
和公式 (1/5)(2^5 − 2^1) = 30/5 = 6 完全一致。
顺手检验一个反例，x^5 + x^4 + 1。它有 3 个非零项，没有一次因子，但要试除 x^2 + x + 1：
x^5 + x^4 + 1 除以 x^2 + x + 1，第一步商 x^3，x^3(x^2+x+1) = x^5 + x^4 + x^3，相减得 x^3 + 1；再商 x，x(x^2+x+1) = x^3 + x^2 + x，相减得 x^2 + x + 1；再商 1，正好减为 0。所以
x^5 + x^4 + 1 = (x^2 + x + 1)(x^3 + x + 1)
可约。这说明"非零项少"和"不可约"之间没有任何必然联系，三项式照样可能可约。
3.4 用计数公式交叉验算：μ 函数到底在扣什么
GF(q) 上次数为 n 的首一不可约多项式个数有闭式解：
N_q(n) = (1/n) · Σ_{d | n} μ(d) · q^(n/d)
其中 μ 是默比乌斯函数：μ(1) = 1，μ(d) = 0 若 d 含有平方因子，μ(d) = (−1)^k 若 d 是 k 个不同素数的乘积。
GF(2) 上的几个值，你可以在枚举完之后逐一对账：
| n | 计算过程 | 不可约个数 | 本原多项式个数 |
|---|---|---|---|
| 1 | (1/1)(2) | 1 | 1 |
| 2 | (1/2)(4−2) | 1 | 1 |
| 3 | (1/3)(8−2) | 2 | 2 |
| 4 | (1/4)(16−4) | 3 | 2 |
| 5 | (1/5)(32−2) | 6 | 6 |
| 6 | (1/6)(64−8−4+2) | 9 | 6 |
| 7 | (1/7)(128−2) | 18 | 18 |
| 8 | (1/8)(256−16) | 30 | 16 |
这张表里最值得盯住的是第 4、6、8 行：不可约的个数和本原的个数不相等。次数为 2、3、5、7 时两者相等，次数为 1、4、6、8 时两者不等。这个规律背后有一条漂亮的判据：当 2^n − 1 是素数（梅森素数）时，GF(2^n) 的乘法群阶是素数，任何非 1 元素的阶都是 2^n−1，于是所有不可约多项式自动是本原的。2、3、5、7 次正好都满足，而 4 次对应 15、6 次对应 63、8 次对应 255，全是合数，所以就出现了差值。
4. 本原多项式：不可约之上再加"生成元"这一条
4.1 定义和三个判定条件
设 f 是 GF(q) 上次数 n ≥ 1 的首一不可约多项式，α 是它在 GF(q^n) 中的任意一个根。GF(q^n) 的乘法群是 q^n − 1 阶循环群，α 作为其中一个元素，有它自己的阶，即最小的正整数 d 使得 α^d = 1，且 d 必然整除 q^n − 1。
若 α 的阶恰好等于 q^n − 1，则称 f 为 GF(q) 上的n 次本原多项式。
换句话说，本原多项式就是"它的根能生成整个乘法群"。不可约只保证 f 的根落在 GF(q^n) 里而不是更小的子域里，但并不保证这个根的阶是满的。
判定流程可以拆成三步，我平时就是这么走的：
- 先确认 f 首一且不可约（用上一章的方法）；
- 计算 m = q^n − 1，做素因子分解m = r_1^e_1 · r_2^e_2 · ...；
- 对每个素因子 r_i，验证 x^(m / r_i) ≢ 1 (mod f)。全部不成立，则 x 的阶就是 m，f 本原。
第 3 步的原理是：一个元素若阶不是 m，那么它的阶一定是 m 的某个真因子，而 m 的任意真因子必然整除某个 m/r_i（r_i 是素因子）。所以只要排除了所有 m/r_i，就不可能是真因子。
注意：这里必须做素因子分解，不是因子分解。m = 255 的素因子是 3、5、17，检查三个即可；如果你把 15、51、85 这些合因子也拿来检查，只是多算几次，结论不会错但效率低。反过来，漏掉一个素因子就会把非本原多项式误判成本原的。
4.2 把 x^4+x+1 的 15 个幂全部算出来
理论说得再多，不如把一次完整验算摊开。取 f = x^4 + x + 1，在 GF(2) 上。由 f(x) = 0 得到关系式
x^4 = x + 1
（注意 GF(2) 上 −(x+1) 就是 x+1）。之后每一次乘法都往这个关系式上靠，把次数压回 4 次以下。
| k | x^k 的化简结果 | 4 位向量表示 |
|---|---|---|
| 0 | 1 | 0001 |
| 1 | x | 0010 |
| 2 | x^2 | 0100 |
| 3 | x^3 | 1000 |
| 4 | x + 1 | 0011 |
| 5 | x^2 + x | 0110 |
| 6 | x^3 + x^2 | 1100 |
| 7 | x^3 + x + 1 | 1011 |
| 8 | x^2 + 1 | 0101 |
| 9 | x^3 + x | 1010 |
| 10 | x^2 + x + 1 | 0111 |
| 11 | x^3 + x^2 + x | 1110 |
| 12 | x^3 + x^2 + x + 1 | 1111 |
| 13 | x^3 + x^2 + 1 | 1101 |
| 14 | x^3 + 1 | 1001 |
| 15 | 1 | 0001 |
第 15 行回到 1，而且中间 14 个结果互不相同，所以 x 的阶正好是 15 = 2^4 − 1，f = x^4 + x + 1 是本原多项式。
这张表还能顺便验证很多事。比如你可以看到 1 到 15 次幂一共出现了 15 个不同的非零向量，正好把 4 位二进制里除 0000 以外的全部 15 个状态走了一遍。这就是为什么本原多项式在 LFSR 里这么重要——用它做反馈，寄存器状态会跑遍所有非零状态，周期达到最大的 2^n − 1，也就是所谓 m 序列。
再比如顺着表看 x^8 = x^2 + 1，而 x^4 = x+1，(x^4)^2 = x^8 = (x+1)^2 = x^2 + 1，两者一致。这个"平方"关系在特征 2 的域里天然成立，是检查算错没有的一个廉价手段：任何 x^(2k) 都应该等于 (x^k)^2。
4.3 阶的快速判定：只查素因子对应的那几次幂
有了 4.2 节的表，验证本原性只需要看 255 或 15 这种数的素因子。回到 f = x^4 + x + 1，m = 15 = 3 × 5，素因子是 3 和 5，只需确认
- x^(15/3) = x^5 = x^2 + x ≠ 1；
- x^(15/5) = x^3 ≠ 1。
两个都成立，所以阶是 15。而阶一定整除 15，既然不整除 5 也不整除 3，那只能是 15。
同样的流程放到 8 次：m = 255 = 3 × 5 × 17，要检查 x^85、x^51、x^15 三个值是否都不等于 1。这个计算量用程序一秒就出结果，手算就免了。但思路一定要清楚：判定本原性的成本，主要花在 m 的素因子分解上，而不是多项式幂本身。m 小的时候（比如 2^15 − 1 = 32767 = 7 × 31 × 151）手算因子都不难；m 一大（比如 2^127 − 1 这种大素数），分解虽然幸运算得快，但多项式幂的位数也跟着爆炸，这就是工程上必须查表的原因。
4.4 本原多项式的个数与互反关系
GF(2) 上 n 次本原多项式的个数是 φ(2^n − 1) / n，φ 是欧拉函数。验证几个：n = 4 时 φ(15)/4 = 8/4 = 2，正好对应 x^4 + x + 1 和 x^4 + x^3 + 1；n = 5 时 φ(31)/5 = 30/5 = 6，正好对应上一节列的 6 个全部都是本原的；n = 8 时 φ(255)/8 = 128/8 = 16，255 个不可约里只有 16 个能当生成元用。
还有一个实用性质：互反多项式保持本原性。把 f(x) = a_n x^n + ... + a_0 的系数顺序倒过来得到 f*(x) = a_0 x^n + ... + a_n，如果 f 是本原的，f* 也是本原的。x^4 + x + 1 和 x^4 + x^3 + 1 就互为反多项式，它们两个的本原性不是巧合。这条性质在查表时特别重要，因为不同来源给出的表往往一个是原式、一个是反式，看到两个都"本原"不用怀疑自己算错了。
5. 不可约但不本原：最容易混淆的一类反例
5.1 GF(2) 上的 x^4+x^3+x^2+x+1 只能跑出 5 个状态
还是那个 x^4 + x^3 + x^2 + x + 1。它在 3.2 节被确认不可约，现在我们算它的阶。
由 f(x) = 0 得 x^4 = x^3 + x^2 + x + 1。逐次算幂：
- x^1 = x
- x^2 = x^2
- x^3 = x^3
- x^4 = x^3 + x^2 + x + 1
- x^5 = x · x^4 = x^4 + x^3 + x^2 + x = (x^3 + x^2 + x + 1) + x^3 + x^2 + x = 1
x^5 = 1，所以 x 的阶是 5，而不是 15。它不是本原多项式。
用 LFSR 的语言来说，这个反馈多项式对应的寄存器只会在这 5 个状态之间打转：
0001 → 0010 → 0100 → 1000 → 1111 → 0001 → ...
再加上全零状态（永远自锁），一共只用到 6 个状态，剩下的 10 个状态永远进不去。用在伪随机序列发生器上，周期从 15 掉到 5，性能直接崩掉。这就是我开头说的那段代码周期异常的原因。
关键点在于：判定这个多项式不可约没有任何问题，它的根确实落在 GF(2^4) 里且不在任何真子域里，但根的阶只有 5。5 是 15 的真因子，却又不整除 3（GF(2^2) 的大小 4 减 1），所以它既不属于任何子域，也不生成整个群。这种元素在有限域里大量存在，对应到多项式上就是"不可约但不本原"。
5.2 换到 GF(3)：x^2+1 与 x^2+x+2 的分野
换一个素域，逻辑完全一样，但结论会更直观。
x^2 + 1 在 GF(3) 上：f(0) = 1，f(1) = 2，f(2) = 4 + 1 = 5 ≡ 2，三个值都不为 0，2 次多项式无根即不可约。现在算阶。m = 3^2 − 1 = 8，素因子只有 2，只需检查 x^4 是否等于 1。
由 x^2 = −1 ≡ 2，得 x^4 = 2^2 = 4 ≡ 1。
x^4 = 1 而不等于 m = 8，所以x^2 + 1 不可约但不本原。其实更直接地看，x^2 + 1 的根就是 GF(9) 里那个"平方等于 −1"的元素，它的阶是 4，正好是 8 的一半。
x^2 + x + 2 在 GF(3) 上：f(0) = 2，f(1) = 1 + 1 + 2 = 4 ≡ 1，f(2) = 4 + 2 + 2 = 8 ≡ 2，无根，不可约。算阶：由 x^2 = −x − 2 ≡ 2x + 1，得
x^4 = (2x + 1)^2 = 4x^2 + 4x + 1 ≡ x^2 + x + 1
代入 x^2 = 2x + 1：x^2 + x + 1 = (2x + 1) + x + 1 = 3x + 2 ≡ 2
所以 x^4 = 2 ≠ 1，而 x^8 = 2^2 = 1。阶为 8 = 3^2 − 1，x^2 + x + 2 是本原多项式。
两个多项式都不可约，都无根，但一个阶 4 一个阶 8。这类对照在 GF(3)、GF(5) 上比 GF(2) 更常见，因为小素域上"阶是 m 的真因子"的情况更多。GF(3) 上 2 次不可约多项式一共 3 个：
| 多项式 | 是否不可约 | x 的阶 | 是否本原 |
|---|---|---|---|
| x^2 + 1 | 是 | 4 | 否 |
| x^2 + x + 2 | 是 | 8 | 是 |
| x^2 + 2x + 2 | 是 | 8 | 是 |
3 个不可约、2 个本原，和 φ(8)/2 = 4/2 = 2 的公式一致。x^2 + 2x + 2 是 x^2 + x + 2 的反多项式，所以本原。
5.3 AES 的 0x11B：一个每天都在被使用的非本原多项式
现代密码学里最有名的"不可约但不本原"的例子，是 AES 用的那个模约化多项式：
x^8 + x^4 + x^3 + x + 1
对应的十六进制表示是 0x11B（也有人写作 0x1B，省略最高位，这个约定后面会专门说）。它是 GF(2) 上 8 次不可约多项式，这一点没问题，AES 的整个 S 盒求逆运算都建立在它是不可约的基础之上。
但它不是本原多项式。x 在这个域里的阶是 51，而不是 255。255 = 3 × 5 × 17，51 = 3 × 17 是它的真因子。所以如果你在 AES 的域里用 0x02（也就是 x）去当生成元遍历整个乘法群，走到第 51 步就回到 1 了，剩下的 204 个非零元素你一个都碰不到。
AES 的设计者显然知道这件事，所以 MixColumns 里用的固定生成元是0x03（也就是 x + 1），而不是 0x02。0x03 才是这个域里的本原元。这一点在实现 AES 或者写 GF(2^8) 乘法表的时候非常关键——很多人照着文档实现，乘法一直用 0x02 的反复倍乘（xtime），这在计算上是完全正确的，但一旦想用"乘法群生成元"的思路去构造对数表，就会踩坑。
对比一下，GF(2^8) 上 8 次不可约多项式一共 30 个，其中本原的只有 16 个。常见的一个本原选择是 x^8 + x^4 + x^3 + x^2 + 1，在 LFSR 和伪随机序列的场合用得更多。
6. 用 Python 把判定和枚举跑一遍
6.1 位掩码表示法与三个核心函数
GF(2) 上的多项式和一个整数可以一一对应：整数二进制表示里 bit i 为 1，就代表 x^i 这一项存在。比如
- x^4 + x + 1 = 0b10011 = 19
- x^2 + x + 1 = 0b111 = 7
- x^8 + x^4 + x^3 + x + 1 = 0x11B = 283
这样做的好处是加法和减法直接退化成异或，乘法的位移和异或实现也非常自然。我下面写的这几个函数都是 GF(2) 专用，位掩码风格，二十行就能覆盖全部需求。
# 以整数位掩码表示 GF(2) 上的多项式，bit i 对应 x^i # 例：0b1011 表示 x^3 + x + 1 def deg(a): return a.bit_length() - 1 def divmod_poly(a, b): """返回 (q, r)，满足 a = q*b + r 且 deg(r) < deg(b)""" q, db = 0, deg(b) while a and deg(a) >= db: s = deg(a) - db q ^= 1 << s a ^= b << s return q, a def mod_poly(a, b): return divmod_poly(a, b)[1] def mul_poly(a, b): r = 0 while b: if b & 1: r ^= a b >>= 1 a <<= 1 return r def mulmod(a, b, m): return mod_poly(mul_poly(a, b), m) def powmod(base, e, m): """base^e mod m，快速幂""" r = 1 base = mod_poly(base, m) while e: if e & 1: r = mulmod(r, base, m) base = mulmod(base, base, m) e >>= 1 return r def gcd_poly(a, b): while b: a, b = b, mod_poly(a, b) return a这几个函数是全部判定的地基。divmod_poly就是 1.2 节手算长除法的机读版本，每次找到一个商的单项，异或回去继续，直到余式次数低于除式。powmod是标准的二进制快速幂，把"算 x^85 次方"这种需求从 85 次乘法降到 7 次乘法和 7 次平方。
6.2 不可约判定、本原判定与枚举脚本
Rabin 检验和本原判定的代码几乎是照着定义直译，不需要任何技巧：
def factorize(n): fs, d = {}, 2 while d * d <= n: while n % d == 0: fs[d] = fs.get(d, 0) + 1 n //= d d += 1 if n > 1: fs[n] = fs.get(n, 0) + 1 return fs def divisors(n): ds, i = [], 1 while i * i <= n: if n % i == 0: ds.append(i) if i != n // i: ds.append(n // i) i += 1 return sorted(ds) X = 0b10 # 多项式 x def is_irreducible(f): n = deg(f) if n < 1: return False if n == 1: return True # 条件 1：x^(2^n) ≡ x (mod f) if powmod(X, 1 << n, f) != mod_poly(X, f): return False # 条件 2：对 n 的每个素因子 r，gcd(x^(2^(n/r)) - x, f) = 1 for r in factorize(n): h = powmod(X, 1 << (n // r), f) ^ X if gcd_poly(h, f) != 1: return False return True def ord_of_x(f): """x 在模 f 意义下的阶""" n = deg(f) m = (1 << n) - 1 for d in divisors(m): if powmod(X, d, f) == 1: return d return None def is_primitive(f): if not is_irreducible(f): return False n = deg(f) m = (1 << n) - 1 for r in factorize(m): if powmod(X, m // r, f) == 1: return False return True枚举 4 次的情形，一行就够：
n = 4 irr = [f for f in range(1 << n, 1 << (n + 1)) if is_irreducible(f)] prim = [f for f in irr if is_primitive(f)] print("不可约:", [bin(f) for f in irr]) print("本原 :", [bin(f) for f in prim])跑出来是：
不可约: ['0b10011', '0b11001', '0b11111'] 本原 : ['0b10011', '0b11001']0b10011 = x^4 + x + 1，0b11001 = x^4 + x^3 + 1，0b11111 = x^4 + x^3 + x^2 + x + 1，和 3.2 节的手算结果完全对上，本原的两个也和 4.4 节的 φ(15)/4 = 2 对上。把 n 改成 8，程序会在几百毫秒内给出 30 个不可约和 16 个本原的答案，顺便可以验证 ord_of_x(0x11B) 是不是 51。
6.3 用现成库交叉验证结果
自己写的代码最容易在边界条件上出错，我一般会用第二个工具对一遍。Python 生态里做有限域最顺手的是galois库，接口大致是这样的（具体命名以你安装的版本为准）：
import galois # 列出 GF(2) 上 4 次的全部不可约多项式 / 本原多项式 print(galois.irreducible_polys(2, 4)) print(galois.primitive_polys(2, 4)) # 判定单个多项式 print(galois.is_irreducible_poly(2, 0b11111)) # x^4+x^3+x^2+x+1 print(galois.is_primitive_poly(2, 0b10011)) # x^4+x+1 # 建成域对象后可以直接做运算 GF256 = galois.GF(2**8, irreducible_poly=0b100011011) # 0x11B = AES 的多项式 print(GF256.primitive_element)如果机器上有 SageMath，语法更接近数学写法，验证起来最直观：
R.<x> = PolynomialRing(GF(2)) f = x^4 + x^3 + x^2 + x + 1 print(f.is_irreducible()) # True print(f.is_primitive()) # False g = x^8 + x^4 + x^3 + x + 1 print(g.is_irreducible(), g.is_primitive()) # True Falsegalois里的primitive_element那一行值得注意：对于一个给定的 GF(2^8) 表示，本原元不一定是 0x02。如果用 AES 的 0x11B 建域，本原元是 0x03；换成 x^8+x^4+x^3+x^2+1 建域，本原元就可以是 0x02。这就是为什么写涉及对数表的代码时，"先确认生成元"这一步不能省。
提示：自己实现的版本和库版本结果不一致时，先怀疑三件事——多项式的位序是否一致、本原判定有没有漏掉 m 的某个素因子、以及 m 的分解有没有把 1 当成素因子算进去。
7. 工程选型的几个坑：LFSR、CRC 与查表约定
7.1 LFSR 周期只认阶，不认"不可约"
这是我最想强调的一条。LFSR 的输出周期由反馈多项式的根的阶决定，不是由"可不可约"决定。
| 反馈多项式 | 是否不可约 | x 的阶 | 状态周期 |
|---|---|---|---|
| x^4 + x + 1 | 是 | 15 | 15（满周期） |
| x^4 + x^3 + 1 | 是 | 15 | 15（满周期） |
| x^4 + x^3 + x^2 + x + 1 | 是 | 5 | 5 |
| x^4 + x^2 + 1 = (x^2+x+1)^2 | 否 | 3 | 3 |
两个都"不可约"的多项式，一个跑 15 拍、一个跑 5 拍，差距就是这么直接。所以选 LFSR 抽头时，判断标准必须是"本原多项式"，而不是"不可约多项式"。
另外一个实际经验：抽头少的多项式（三项式）硬件上最省异或门，但不是每个次数都存在本原三项式。8 次里比较常见的选择是五项式 x^8 + x^4 + x^3 + x^2 + 1。选型时如果查到某个次数只有五项式或七项式可用，不要硬凑三项式，先确认它确实本原再说。查表时也不能只抄系数，最好自己用第 6 章的代码跑一遍验证阶是不是满的。
7.2 CRC 生成多项式本来就不需要本原
这一点经常被误解。CRC 的核心指标是最小距离和可检测错误长度，不是"能不能生成整个乘法群"。
具体来说，很多标准 CRC 的生成多项式故意包含 (x + 1) 因子，目的是让所有奇数个位翻转的错误都能被检测到。而一个多项式含有 (x+1) 因子，就意味着它必然可约——这跟本原性的要求是背道而驰的。
举一个能自己验证的例子：CRC-16/IBM 的多项式是 x^16 + x^15 + x^2 + 1，非零项 4 个，是偶数，所以在 GF(2) 上它一定被 x + 1 整除，一定可约。这不影响它成为一个广泛使用的 CRC 标准。
所以正确的认知是：CRC 用可约多项式，LFSR 和扩频序列用本原多项式，AES 用不可约但不本原的多项式。三种场景三种需求，不要拿一把尺子量所有东西。
7.3 互反多项式与 MSB/LSB 约定带来的查表错位
最后一个坑，也是我见过最多人栽跟头的：同一条多项式在不同工具里的表示不一致。
第一层是省略最高位。x^8 + x^4 + x^3 + x + 1 的完整系数是 1 0001 1011，写成十六进制是 0x11B；但很多代码里只保留低 8 位，写作 0x1B。这两个数差了整整一位，如果一边用 0x11B 做模约化、另一边用 0x1B 建表，结果一定对不上。
第二层是互反关系。因为 GF(2) 上 f 和它的互反多项式 f* 同时本原、同时不可约，很多资料给的表其实是反过来的版本。做移位寄存器实现时，MSB-first 和 LSB-first 两种写法对应的是互为反式的两个多项式，抽头位置看起来完全不一样，但生成的序列是时间反演的关系。
我处理这件事的固定流程是三步：
- 拿到一个多项式，先写出它和它的互反式；
- 用第 6 章的脚本确认哪个是原表给的、哪个是本原的；
- 在代码注释里写清楚当前实现用的是哪一个，以及位序约定。
这一步多花五分钟，能省掉后面一整天的调试。尤其是在跨团队协作、或者接手一份别人写的扰码模块时，"这个系数到底对应哪一位"这种问题如果不写清楚，后面的人一定会重新踩一遍。
8. 几道可以自己动手的判定题与参考答案
理论看完，最重要的还是自己动手算几道。下面这几道题我都只给答案，过程建议你先在纸上走一遍，尤其是阶的计算。
题 1：判断 GF(2) 上 x^5 + x^3 + x^2 + x + 1 的不可约性和本原性。
答案：不可约，且本原。它非零项 5 个（奇数），无一次因子；对 2 次因子 x^2 + x + 1 试除余式非零。它是 3.3 节列出的 6 个 5 次不可约多项式之一。由于 2^5 − 1 = 31 是素数，所有 5 次不可约多项式自动本原，所以它也是本原的，阶为 31。
题 2：GF(2) 上 x^5 + x^4 + 1 是不可约的吗？
答案：不是。它等于 (x^2 + x + 1)(x^3 + x + 1)，完整除法过程见 3.3 节。
题 3：GF(3) 上 x^2 + x + 1 是不可约的吗？
答案：不是。f(1) = 1 + 1 + 1 = 3 ≡ 0，x = 1 是根。事实上 x^2 + x + 1 = (x + 2)^2。这道题的教训是 GF(p) 上的求根必须遍历全部 p 个元素，只试 0 和 1 是不够的。
题 4：判断 GF(3) 上 x^3 + 2x + 1 的不可约性和本原性。
答案：不可约且本原。f(0) = 1，f(1) = 4 ≡ 1，f(2) = 13 ≡ 1，三次多项式无根即不可约。算阶：m = 3^3 − 1 = 26 = 2 × 13，素因子 2 和 13。由 x^3 = x + 2 逐步算出 x^12 = x^2 + 2，所以 x^13 = x^3 + 2x = (x + 2) + 2x = 3x + 2 ≡ 2 ≠ 1，而 x^26 = 2^2 = 4 ≡ 1。阶为 26，本原。
题 5：GF(2) 上 6 次本原多项式有几个？
答案：φ(63)/6 = 36/6 = 6。而 6 次不可约多项式有 9 个，也就是说有 3 个不可约但不本原。用第 6 章的脚本可以把这 3 个直接找出来。
题 6：验证 x^2 + x + 1 是 GF(2) 上的本原多项式。
答案：由 x^2 = x + 1，x^3 = x(x+1) = x^2 + x = (x+1) + x = 1，阶为 3 = 2^2 − 1，本原。顺便说一句，它也是 GF(2) 上唯一的 2 次不可约多项式，所以 2 次情形下两个概念重合。
题 7：AES 的模约化多项式 x^8 + x^4 + x^3 + x + 1 是 GF(2) 上的本原多项式吗？如果不是，x 的阶是多少？
答案：不可约但不是本原。它对应的整数是 0x11B，用第 6 章的 ord_of_x 跑一下会得到 51。51 = 3 × 17 是 255 = 3 × 5 × 17 的真因子。想用生成元遍历整个乘法群的话，要用 0x03 而不是 0x02。
题 8：GF(3) 上 2 次不可约多项式有几个？分别是什么？
答案：3 个，分别是 x^2 + 1、x^2 + x + 2、x^2 + 2x + 2，验证与阶的计算见 5.2 节。其中只有后两个是本原的。
题 9：一个 8 次本原多项式用于 LFSR，寄存器状态一共会经历多少个非零状态？
答案：2^8 − 1 = 255 个。这里要注意区分"寄存器的 256 个可能状态"和"非零状态 255 个"，全零状态是自锁的，永远不会出现在本原多项式的循环里。
题 10：把 x^4 + x + 1 的系数顺序倒过来得到 x^4 + x^3 + 1，它还是本原多项式吗？
答案：是。互反操作保持本原性。这一点在 4.4 节解释过，它是查表时看到两个互为反式的多项式同时出现在本原表里的原因。
我自己在实际操作中的体会是，这套东西真正难的地方从来不是公式，而是"什么时候该用哪一条判据"。低次多项式手算求根最快，中等的靠试除，上规模的必须上 Rabin 加程序；判定不可约和判定本原之间差着一次素因子分解，漏掉一个素因子就会得出相反的结论。至于查表，永远自己跑一遍验证，比信任任何一份来源不明的表格都要稳妥。
