尧图网站开发 多项式枚举、LFSR与AES选型)
第一次在项目里认真查不可约多项式这个词是因为一段 LFSR 代码的输出周期只有理论值的三分之一——反馈抽头明明是从手册上照抄的序列却在几十个时钟周期之后就重复了。当时把特征多项式拎出来一算才发现那个多项式在 GF(2) 上确实满足不可约但它的根只能生成 5 个非零元离满周期 2^4−115 差得远。也就是说不可约多项式并不等于本原多项式前者只是后者的必要门槛。那次之后我把这两个概念彻底拆开重学了一遍顺手把所有低次的情形都手算枚举了一遍这篇就是那段时间的笔记整理。内容会覆盖有限域上多项式除法的手算方法、不可约性的三种判定路径、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 长除法手算模板两个能背下来的例子不可约判定的第一步永远是试除而试除依赖长除法。这里给两个我练手时反复用的例子。例 1GF(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^4x^3x^2x1 的不可约性时还会再出现。例 2GF(3)计算 (x^3 2x 1) ÷ (x 2)。商首项 x^2x^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商次项 xx · (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^4x^3x^2x1非零项 5 个奇数所以它至少躲过了 x1 这一关。而 x^4x^3x1 有 4 个非零项偶数立刻可以断定它可约事实上它等于 (x1)^2(x^2x1)。这个判据能在枚举时帮你砍掉一半候选值不值得单独记你自己算两轮就知道了。2. 不可约性的三重判定求根、试除、Rabin 各管一段2.1 次数不超过 3 时求根法就是全部先给结论在 GF(p) 上次数为 2 或 3 的多项式不可约当且仅当它在 GF(p) 中没有根。理由是分解次数一个 2 次多项式如果真的能分解只可能是 11一个 3 次多项式如果真的能分解只可能是 12。两种情况下都必然存在一个一次因子而一次因子 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) 1f(1) 1但它是 (x^2 x 1)^2彻底可约。因为你完全可以把 4 次拆成 22两个因子都没有根但乘积有。求根法只在次数 ≤ 3 时是充分必要的4 次及以上它只能用来排除有根的情形不能用来确认不可约。2.2 试除法只需要试到 n/2 次对 n 次首一多项式 f如果它是可约的那它一定有一个次数不超过 n/2 的不可约因子。所以理论上只需要拿所有次数 ≤ ⌊n/2⌋ 的首一不可约多项式去试除即可。实际操作中我一般偷个懒直接拿所有次数 ≤ ⌊n/2⌋ 的首一多项式包括可约的去试除。因为可约因子里必然含有不可约因子多试几个不会改变结论只是多算几步但省掉了先把低次不可约多项式筛出来的准备工作。GF(2) 上 4 次多项式的试除只需要对付 x、x1、x^2x1 三个次数 ≤ 2 的首一式工作量完全可以接受。试除法的优点是直观、可手算、出错能被检查缺点是次数一高就崩。8 次多项式要试除次数 ≤ 4 的所有首一多项式GF(2) 上有 124816 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 同样通过它的根在某个扩域里的阶是 55 | 15所以 x^16 ≡ x。条件 2x^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等于 (x1)^2且 f(1) 0可约x^2 x等于 x(x1)且常数项为 0可约x^2 x 1f(0) 1f(1) 1无根不可约所以 2 次不可约多项式只有 1 个x^2 x 1。3 次首一多项式共 8 个。用奇数个非零项先砍非零项个数必须是奇数所以常数项必须是 1、并且 x^2 和 x 的系数里要有偶数个 11 个或 0 个。满足条件的是这 4 个x^3 1等于 (x1)(x^2x1)可约x^3 x 1无根不可约x^3 x^2 1无根不可约x^3 x^2 x 1等于 (x1)^3可约。2 个不可约多项式。这个数字和公式 (1/3)(2^3 − 2^1) 2 吻合。3.2 次数 416 个候选里的 3 个幸存者4 次首一多项式一共 16 个我把它们全部列出来。这一步不要跳因为哪些能被 2 次因子整除的直觉必须靠这种穷举建立起来。多项式分解形式结论x^4x·x·x·x可约x^4 1(x1)^4可约x^4 xx(x1)(x^2x1)可约x^4 x 1无低次因子不可约x^4 x^2x^2(x1)^2可约x^4 x^2 1(x^2x1)^2可约x^4 x^2 xx(x^3x1)可约x^4 x^2 x 1(x1)(x^3x^21)可约x^4 x^3x^3(x1)可约x^4 x^3 1无低次因子不可约x^4 x^3 xx(x^3x^21)可约x^4 x^3 x 1(x1)^2(x^2x1)可约x^4 x^3 x^2x^2(x^2x1)可约x^4 x^3 x^2 1(x1)(x^3x1)可约x^4 x^3 x^2 xx(x1)^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 1x^5 x^3 1x^5 x^3 x^2 x 1x^5 x^4 x^2 x 1x^5 x^4 x^3 x 1x^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 1x^5 x^4 1 除以 x^2 x 1第一步商 x^3x^3(x^2x1) x^5 x^4 x^3相减得 x^3 1再商 xx(x^2x1) 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)112(1/2)(4−2)113(1/3)(8−2)224(1/4)(16−4)325(1/5)(32−2)666(1/6)(64−8−42)967(1/7)(128−2)18188(1/8)(256−16)3016这张表里最值得盯住的是第 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 的阶就是 mf 本原。第 3 步的原理是一个元素若阶不是 m那么它的阶一定是 m 的某个真因子而 m 的任意真因子必然整除某个 m/r_ir_i 是素因子。所以只要排除了所有 m/r_i就不可能是真因子。注意这里必须做素因子分解不是因子分解。m 255 的素因子是 3、5、17检查三个即可如果你把 15、51、85 这些合因子也拿来检查只是多算几次结论不会错但效率低。反过来漏掉一个素因子就会把非本原多项式误判成本原的。4.2 把 x^4x1 的 15 个幂全部算出来理论说得再多不如把一次完整验算摊开。取 f x^4 x 1在 GF(2) 上。由 f(x) 0 得到关系式x^4 x 1注意 GF(2) 上 −(x1) 就是 x1。之后每一次乘法都往这个关系式上靠把次数压回 4 次以下。kx^k 的化简结果4 位向量表示0100011x00102x^201003x^310004x 100115x^2 x01106x^3 x^211007x^3 x 110118x^2 101019x^3 x101010x^2 x 1011111x^3 x^2 x111012x^3 x^2 x 1111113x^3 x^2 1110114x^3 110011510001第 15 行回到 1而且中间 14 个结果互不相同所以 x 的阶正好是 15 2^4 − 1f x^4 x 1 是本原多项式。这张表还能顺便验证很多事。比如你可以看到 1 到 15 次幂一共出现了 15 个不同的非零向量正好把 4 位二进制里除 0000 以外的全部 15 个状态走了一遍。这就是为什么本原多项式在 LFSR 里这么重要——用它做反馈寄存器状态会跑遍所有非零状态周期达到最大的 2^n − 1也就是所谓 m 序列。再比如顺着表看 x^8 x^2 1而 x^4 x1(x^4)^2 x^8 (x1)^2 x^2 1两者一致。这个平方关系在特征 2 的域里天然成立是检查算错没有的一个廉价手段任何 x^(2k) 都应该等于 (x^k)^2。4.3 阶的快速判定只查素因子对应的那几次幂有了 4.2 节的表验证本原性只需要看 255 或 15 这种数的素因子。回到 f x^4 x 1m 15 3 × 5素因子是 3 和 5只需确认x^(15/3) x^5 x^2 x ≠ 1x^(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 1n 5 时 φ(31)/5 30/5 6正好对应上一节列的 6 个全部都是本原的n 8 时 φ(255)/8 128/8 16255 个不可约里只有 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^4x^3x^2x1 只能跑出 5 个状态还是那个 x^4 x^3 x^2 x 1。它在 3.2 节被确认不可约现在我们算它的阶。由 f(x) 0 得 x^4 x^3 x^2 x 1。逐次算幂x^1 xx^2 x^2x^3 x^3x^4 x^3 x^2 x 1x^5 x · x^4 x^4 x^3 x^2 x (x^3 x^2 x 1) x^3 x^2 x 1x^5 1所以 x 的阶是 5而不是 15。它不是本原多项式。用 LFSR 的语言来说这个反馈多项式对应的寄存器只会在这 5 个状态之间打转0001 → 0010 → 0100 → 1000 → 1111 → 0001 → ...再加上全零状态永远自锁一共只用到 6 个状态剩下的 10 个状态永远进不去。用在伪随机序列发生器上周期从 15 掉到 5性能直接崩掉。这就是我开头说的那段代码周期异常的原因。关键点在于判定这个多项式不可约没有任何问题它的根确实落在 GF(2^4) 里且不在任何真子域里但根的阶只有 5。5 是 15 的真因子却又不整除 3GF(2^2) 的大小 4 减 1所以它既不属于任何子域也不生成整个群。这种元素在有限域里大量存在对应到多项式上就是不可约但不本原。5.2 换到 GF(3)x^21 与 x^2x2 的分野换一个素域逻辑完全一样但结论会更直观。x^2 1 在 GF(3) 上f(0) 1f(1) 2f(2) 4 1 5 ≡ 2三个值都不为 02 次多项式无根即不可约。现在算阶。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) 2f(1) 1 1 2 4 ≡ 1f(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 1x^2 x 1 (2x 1) x 1 3x 2 ≡ 2所以 x^4 2 ≠ 1而 x^8 2^2 1。阶为 8 3^2 − 1x^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 × 1751 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 19x^2 x 1 0b111 7x^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 # 条件 1x^(2^n) ≡ x (mod f) if powmod(X, 1 n, f) ! mod_poly(X, f): return False # 条件 2对 n 的每个素因子 rgcd(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 10b11001 x^4 x^3 10b11111 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^4x^3x^2x1 print(galois.is_primitive_poly(2, 0b10011)) # x^4x1 # 建成域对象后可以直接做运算 GF256 galois.GF(2**8, irreducible_poly0b100011011) # 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^8x^4x^3x^21 建域本原元就可以是 0x02。这就是为什么写涉及对数表的代码时先确认生成元这一步不能省。提示自己实现的版本和库版本结果不一致时先怀疑三件事——多项式的位序是否一致、本原判定有没有漏掉 m 的某个素因子、以及 m 的分解有没有把 1 当成素因子算进去。7. 工程选型的几个坑LFSR、CRC 与查表约定7.1 LFSR 周期只认阶不认不可约这是我最想强调的一条。LFSR 的输出周期由反馈多项式的根的阶决定不是由可不可约决定。反馈多项式是否不可约x 的阶状态周期x^4 x 1是1515满周期x^4 x^3 1是1515满周期x^4 x^3 x^2 x 1是55x^4 x^2 1 (x^2x1)^2否33两个都不可约的多项式一个跑 15 拍、一个跑 5 拍差距就是这么直接。所以选 LFSR 抽头时判断标准必须是本原多项式而不是不可约多项式。另外一个实际经验抽头少的多项式三项式硬件上最省异或门但不是每个次数都存在本原三项式。8 次里比较常见的选择是五项式 x^8 x^4 x^3 x^2 1。选型时如果查到某个次数只有五项式或七项式可用不要硬凑三项式先确认它确实本原再说。查表时也不能只抄系数最好自己用第 6 章的代码跑一遍验证阶是不是满的。7.2 CRC 生成多项式本来就不需要本原这一点经常被误解。CRC 的核心指标是最小距离和可检测错误长度不是能不能生成整个乘法群。具体来说很多标准 CRC 的生成多项式故意包含 (x 1) 因子目的是让所有奇数个位翻转的错误都能被检测到。而一个多项式含有 (x1) 因子就意味着它必然可约——这跟本原性的要求是背道而驰的。举一个能自己验证的例子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。题 2GF(2) 上 x^5 x^4 1 是不可约的吗答案不是。它等于 (x^2 x 1)(x^3 x 1)完整除法过程见 3.3 节。题 3GF(3) 上 x^2 x 1 是不可约的吗答案不是。f(1) 1 1 1 3 ≡ 0x 1 是根。事实上 x^2 x 1 (x 2)^2。这道题的教训是 GF(p) 上的求根必须遍历全部 p 个元素只试 0 和 1 是不够的。题 4判断 GF(3) 上 x^3 2x 1 的不可约性和本原性。答案不可约且本原。f(0) 1f(1) 4 ≡ 1f(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本原。题 5GF(2) 上 6 次本原多项式有几个答案φ(63)/6 36/6 6。而 6 次不可约多项式有 9 个也就是说有 3 个不可约但不本原。用第 6 章的脚本可以把这 3 个直接找出来。题 6验证 x^2 x 1 是 GF(2) 上的本原多项式。答案由 x^2 x 1x^3 x(x1) x^2 x (x1) x 1阶为 3 2^2 − 1本原。顺便说一句它也是 GF(2) 上唯一的 2 次不可约多项式所以 2 次情形下两个概念重合。题 7AES 的模约化多项式 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。题 8GF(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 加程序判定不可约和判定本原之间差着一次素因子分解漏掉一个素因子就会得出相反的结论。至于查表永远自己跑一遍验证比信任任何一份来源不明的表格都要稳妥。 
第一次在项目里认真查不可约多项式这个词是因为一段 LFSR 代码的输出周期只有理论值的三分之一——反馈抽头明明是从手册上照抄的序列却在几十个时钟周期之后就重复了。当时把特征多项式拎出来一算才发现那个多项式在 GF(2) 上确实满足不可约但它的根只能生成 5 个非零元离满周期 2^4−115 差得远。也就是说不可约多项式并不等于本原多项式前者只是后者的必要门槛。那次之后我把这两个概念彻底拆开重学了一遍顺手把所有低次的情形都手算枚举了一遍这篇就是那段时间的笔记整理。内容会覆盖有限域上多项式除法的手算方法、不可约性的三种判定路径、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 长除法手算模板两个能背下来的例子不可约判定的第一步永远是试除而试除依赖长除法。这里给两个我练手时反复用的例子。例 1GF(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^4x^3x^2x1 的不可约性时还会再出现。例 2GF(3)计算 (x^3 2x 1) ÷ (x 2)。商首项 x^2x^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商次项 xx · (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^4x^3x^2x1非零项 5 个奇数所以它至少躲过了 x1 这一关。而 x^4x^3x1 有 4 个非零项偶数立刻可以断定它可约事实上它等于 (x1)^2(x^2x1)。这个判据能在枚举时帮你砍掉一半候选值不值得单独记你自己算两轮就知道了。2. 不可约性的三重判定求根、试除、Rabin 各管一段2.1 次数不超过 3 时求根法就是全部先给结论在 GF(p) 上次数为 2 或 3 的多项式不可约当且仅当它在 GF(p) 中没有根。理由是分解次数一个 2 次多项式如果真的能分解只可能是 11一个 3 次多项式如果真的能分解只可能是 12。两种情况下都必然存在一个一次因子而一次因子 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) 1f(1) 1但它是 (x^2 x 1)^2彻底可约。因为你完全可以把 4 次拆成 22两个因子都没有根但乘积有。求根法只在次数 ≤ 3 时是充分必要的4 次及以上它只能用来排除有根的情形不能用来确认不可约。2.2 试除法只需要试到 n/2 次对 n 次首一多项式 f如果它是可约的那它一定有一个次数不超过 n/2 的不可约因子。所以理论上只需要拿所有次数 ≤ ⌊n/2⌋ 的首一不可约多项式去试除即可。实际操作中我一般偷个懒直接拿所有次数 ≤ ⌊n/2⌋ 的首一多项式包括可约的去试除。因为可约因子里必然含有不可约因子多试几个不会改变结论只是多算几步但省掉了先把低次不可约多项式筛出来的准备工作。GF(2) 上 4 次多项式的试除只需要对付 x、x1、x^2x1 三个次数 ≤ 2 的首一式工作量完全可以接受。试除法的优点是直观、可手算、出错能被检查缺点是次数一高就崩。8 次多项式要试除次数 ≤ 4 的所有首一多项式GF(2) 上有 124816 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 同样通过它的根在某个扩域里的阶是 55 | 15所以 x^16 ≡ x。条件 2x^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等于 (x1)^2且 f(1) 0可约x^2 x等于 x(x1)且常数项为 0可约x^2 x 1f(0) 1f(1) 1无根不可约所以 2 次不可约多项式只有 1 个x^2 x 1。3 次首一多项式共 8 个。用奇数个非零项先砍非零项个数必须是奇数所以常数项必须是 1、并且 x^2 和 x 的系数里要有偶数个 11 个或 0 个。满足条件的是这 4 个x^3 1等于 (x1)(x^2x1)可约x^3 x 1无根不可约x^3 x^2 1无根不可约x^3 x^2 x 1等于 (x1)^3可约。2 个不可约多项式。这个数字和公式 (1/3)(2^3 − 2^1) 2 吻合。3.2 次数 416 个候选里的 3 个幸存者4 次首一多项式一共 16 个我把它们全部列出来。这一步不要跳因为哪些能被 2 次因子整除的直觉必须靠这种穷举建立起来。多项式分解形式结论x^4x·x·x·x可约x^4 1(x1)^4可约x^4 xx(x1)(x^2x1)可约x^4 x 1无低次因子不可约x^4 x^2x^2(x1)^2可约x^4 x^2 1(x^2x1)^2可约x^4 x^2 xx(x^3x1)可约x^4 x^2 x 1(x1)(x^3x^21)可约x^4 x^3x^3(x1)可约x^4 x^3 1无低次因子不可约x^4 x^3 xx(x^3x^21)可约x^4 x^3 x 1(x1)^2(x^2x1)可约x^4 x^3 x^2x^2(x^2x1)可约x^4 x^3 x^2 1(x1)(x^3x1)可约x^4 x^3 x^2 xx(x1)^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 1x^5 x^3 1x^5 x^3 x^2 x 1x^5 x^4 x^2 x 1x^5 x^4 x^3 x 1x^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 1x^5 x^4 1 除以 x^2 x 1第一步商 x^3x^3(x^2x1) x^5 x^4 x^3相减得 x^3 1再商 xx(x^2x1) 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)112(1/2)(4−2)113(1/3)(8−2)224(1/4)(16−4)325(1/5)(32−2)666(1/6)(64−8−42)967(1/7)(128−2)18188(1/8)(256−16)3016这张表里最值得盯住的是第 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 的阶就是 mf 本原。第 3 步的原理是一个元素若阶不是 m那么它的阶一定是 m 的某个真因子而 m 的任意真因子必然整除某个 m/r_ir_i 是素因子。所以只要排除了所有 m/r_i就不可能是真因子。注意这里必须做素因子分解不是因子分解。m 255 的素因子是 3、5、17检查三个即可如果你把 15、51、85 这些合因子也拿来检查只是多算几次结论不会错但效率低。反过来漏掉一个素因子就会把非本原多项式误判成本原的。4.2 把 x^4x1 的 15 个幂全部算出来理论说得再多不如把一次完整验算摊开。取 f x^4 x 1在 GF(2) 上。由 f(x) 0 得到关系式x^4 x 1注意 GF(2) 上 −(x1) 就是 x1。之后每一次乘法都往这个关系式上靠把次数压回 4 次以下。kx^k 的化简结果4 位向量表示0100011x00102x^201003x^310004x 100115x^2 x01106x^3 x^211007x^3 x 110118x^2 101019x^3 x101010x^2 x 1011111x^3 x^2 x111012x^3 x^2 x 1111113x^3 x^2 1110114x^3 110011510001第 15 行回到 1而且中间 14 个结果互不相同所以 x 的阶正好是 15 2^4 − 1f x^4 x 1 是本原多项式。这张表还能顺便验证很多事。比如你可以看到 1 到 15 次幂一共出现了 15 个不同的非零向量正好把 4 位二进制里除 0000 以外的全部 15 个状态走了一遍。这就是为什么本原多项式在 LFSR 里这么重要——用它做反馈寄存器状态会跑遍所有非零状态周期达到最大的 2^n − 1也就是所谓 m 序列。再比如顺着表看 x^8 x^2 1而 x^4 x1(x^4)^2 x^8 (x1)^2 x^2 1两者一致。这个平方关系在特征 2 的域里天然成立是检查算错没有的一个廉价手段任何 x^(2k) 都应该等于 (x^k)^2。4.3 阶的快速判定只查素因子对应的那几次幂有了 4.2 节的表验证本原性只需要看 255 或 15 这种数的素因子。回到 f x^4 x 1m 15 3 × 5素因子是 3 和 5只需确认x^(15/3) x^5 x^2 x ≠ 1x^(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 1n 5 时 φ(31)/5 30/5 6正好对应上一节列的 6 个全部都是本原的n 8 时 φ(255)/8 128/8 16255 个不可约里只有 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^4x^3x^2x1 只能跑出 5 个状态还是那个 x^4 x^3 x^2 x 1。它在 3.2 节被确认不可约现在我们算它的阶。由 f(x) 0 得 x^4 x^3 x^2 x 1。逐次算幂x^1 xx^2 x^2x^3 x^3x^4 x^3 x^2 x 1x^5 x · x^4 x^4 x^3 x^2 x (x^3 x^2 x 1) x^3 x^2 x 1x^5 1所以 x 的阶是 5而不是 15。它不是本原多项式。用 LFSR 的语言来说这个反馈多项式对应的寄存器只会在这 5 个状态之间打转0001 → 0010 → 0100 → 1000 → 1111 → 0001 → ...再加上全零状态永远自锁一共只用到 6 个状态剩下的 10 个状态永远进不去。用在伪随机序列发生器上周期从 15 掉到 5性能直接崩掉。这就是我开头说的那段代码周期异常的原因。关键点在于判定这个多项式不可约没有任何问题它的根确实落在 GF(2^4) 里且不在任何真子域里但根的阶只有 5。5 是 15 的真因子却又不整除 3GF(2^2) 的大小 4 减 1所以它既不属于任何子域也不生成整个群。这种元素在有限域里大量存在对应到多项式上就是不可约但不本原。5.2 换到 GF(3)x^21 与 x^2x2 的分野换一个素域逻辑完全一样但结论会更直观。x^2 1 在 GF(3) 上f(0) 1f(1) 2f(2) 4 1 5 ≡ 2三个值都不为 02 次多项式无根即不可约。现在算阶。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) 2f(1) 1 1 2 4 ≡ 1f(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 1x^2 x 1 (2x 1) x 1 3x 2 ≡ 2所以 x^4 2 ≠ 1而 x^8 2^2 1。阶为 8 3^2 − 1x^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 × 1751 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 19x^2 x 1 0b111 7x^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 # 条件 1x^(2^n) ≡ x (mod f) if powmod(X, 1 n, f) ! mod_poly(X, f): return False # 条件 2对 n 的每个素因子 rgcd(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 10b11001 x^4 x^3 10b11111 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^4x^3x^2x1 print(galois.is_primitive_poly(2, 0b10011)) # x^4x1 # 建成域对象后可以直接做运算 GF256 galois.GF(2**8, irreducible_poly0b100011011) # 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^8x^4x^3x^21 建域本原元就可以是 0x02。这就是为什么写涉及对数表的代码时先确认生成元这一步不能省。提示自己实现的版本和库版本结果不一致时先怀疑三件事——多项式的位序是否一致、本原判定有没有漏掉 m 的某个素因子、以及 m 的分解有没有把 1 当成素因子算进去。7. 工程选型的几个坑LFSR、CRC 与查表约定7.1 LFSR 周期只认阶不认不可约这是我最想强调的一条。LFSR 的输出周期由反馈多项式的根的阶决定不是由可不可约决定。反馈多项式是否不可约x 的阶状态周期x^4 x 1是1515满周期x^4 x^3 1是1515满周期x^4 x^3 x^2 x 1是55x^4 x^2 1 (x^2x1)^2否33两个都不可约的多项式一个跑 15 拍、一个跑 5 拍差距就是这么直接。所以选 LFSR 抽头时判断标准必须是本原多项式而不是不可约多项式。另外一个实际经验抽头少的多项式三项式硬件上最省异或门但不是每个次数都存在本原三项式。8 次里比较常见的选择是五项式 x^8 x^4 x^3 x^2 1。选型时如果查到某个次数只有五项式或七项式可用不要硬凑三项式先确认它确实本原再说。查表时也不能只抄系数最好自己用第 6 章的代码跑一遍验证阶是不是满的。7.2 CRC 生成多项式本来就不需要本原这一点经常被误解。CRC 的核心指标是最小距离和可检测错误长度不是能不能生成整个乘法群。具体来说很多标准 CRC 的生成多项式故意包含 (x 1) 因子目的是让所有奇数个位翻转的错误都能被检测到。而一个多项式含有 (x1) 因子就意味着它必然可约——这跟本原性的要求是背道而驰的。举一个能自己验证的例子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。题 2GF(2) 上 x^5 x^4 1 是不可约的吗答案不是。它等于 (x^2 x 1)(x^3 x 1)完整除法过程见 3.3 节。题 3GF(3) 上 x^2 x 1 是不可约的吗答案不是。f(1) 1 1 1 3 ≡ 0x 1 是根。事实上 x^2 x 1 (x 2)^2。这道题的教训是 GF(p) 上的求根必须遍历全部 p 个元素只试 0 和 1 是不够的。题 4判断 GF(3) 上 x^3 2x 1 的不可约性和本原性。答案不可约且本原。f(0) 1f(1) 4 ≡ 1f(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本原。题 5GF(2) 上 6 次本原多项式有几个答案φ(63)/6 36/6 6。而 6 次不可约多项式有 9 个也就是说有 3 个不可约但不本原。用第 6 章的脚本可以把这 3 个直接找出来。题 6验证 x^2 x 1 是 GF(2) 上的本原多项式。答案由 x^2 x 1x^3 x(x1) x^2 x (x1) x 1阶为 3 2^2 − 1本原。顺便说一句它也是 GF(2) 上唯一的 2 次不可约多项式所以 2 次情形下两个概念重合。题 7AES 的模约化多项式 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。题 8GF(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 加程序判定不可约和判定本原之间差着一次素因子分解漏掉一个素因子就会得出相反的结论。至于查表永远自己跑一遍验证比信任任何一份来源不明的表格都要稳妥。