如果你做过 AES、Reed-Solomon 或者 CRC那你一定遇到过「伽罗华域」这个词。我第一次认真啃它不是从定义开始而是写 Reed-Solomon 编码时调试一个根据索引查表的乘法越调越觉得不对劲为什么乘法可以通过查一张表完成表是怎么算出来的有限域里的元素到底是怎么生成的这篇文章就把这条线索完整捋一遍——从域的正式定义到扩展域元素的生成过程再到加法、乘法、逆元这些运算背后的原理最后用手推和代码两种方式完整生成 GF(2^4) 并验证运算。想搞清楚 Galois Field 是什么、会查会算、能迁移到 AES 或 RS 场景里的朋友可以直接当一份带推导的实操笔记来用。1. 有限域“有限”在哪从集合到封闭性1.1 两层群结构让四则运算都自洽域这个数学概念听起来吓人拆开就是两个条件集合里所有元素对加法构成一个交换群去掉零元之后对乘法也构成一个交换群另外乘法和加法之间满足分配律。第一条保证每个元素都有相反数所以能做减法第二条保证每个非零元素都有倒数所以能做除法。加、减、乘、除全部在集合内部封闭不管你怎么折腾结果都不会跑到集合外面这才叫域。无限域里最常见的例子是全体有理数、全体实数。你随便拿两个实数相加、相乘、取逆结果还是实数不会突然飘到复数里去。有限域则把这种“封闭性”强行压缩到一个有限集合里。那么问题来了这个集合里到底能放多少元素答案是只能放 p^m 个其中 p 是素数m 是正整数。这不是随意规定的而是由域的结构决定的。这句话是整个 Galois Field 的出发点也是后面所有生成和运算规则的基石。1.2 为什么元素个数必须是素数幂说个直观的论证。如果有限域的元素个数是合数 n那么用整数模 n 的方式构造集合一定无法形成域。拿 n4 举例集合是 {0, 1, 2, 3}模 4 加法没问题但乘法会出问题2 乘以任何整数再模 4 都得不到 1。也就是说元素 2 没有乘法逆元。一个非零元素找不到逆元除法就没法定义域的条件立刻被打破。所以有限域的“底盘”必须是一个素数域 GF(p)。在这个素域里加法和乘法都按模 p 进行。例如 GF(7) 中3 的逆元是 5因为 3×515模 7 等于 1。只有 p 是素数时每一个非零元素才能通过费马小定理找到逆元a^(p-1)≡1 (mod p)所以 a 的逆元就是 a^(p-2) (mod p)。这套数学结构一旦搭好有限域就有了“地基”。GF(p) 只能表示 p 个元素工程上用起来太局促。真正大量使用的是 GF(2^m)也就是二进制域每个元素都能对应一个 m 位的二进制串既方便存储又能直接映射到计算机的字长上。要把这些 m 位元素“生成”出来我们需要从 GF(2) 出发做一次域扩张。1.3 一个看得见的规矩特征 2 的“加等于减”GF(2^m) 有个非常特殊的性质域的特征是 2。特征 2 意味着任何元素和自己相加都等于 0也就是加法等价于减法。这在普通算术里看着很别扭但在计算机里简直是天赐的礼物——异或运算就是模 2 加法一个 XOR 门同时完成了加法和减法。这个特性会一路影响后面的所有运算规则。比如我们在 GF(2^m) 里推导时遇到 a a 直接写成 0遇到多项式减法不需要额外处理因为减去一个多项式就等于加上同一个多项式。很多初学的人在这里被惯性绊倒总想把减号当作独立的操作实际上在二进制域里减号只是加号的别名。理解这一点后面所有运算推导才顺得下去。2. 扩展域如何“长”出来多项式表示与模余规则2.1 把“数字”换成“多项式”素域 GF(2) 里只有 0 和 1能做的事情非常有限。为了得到 GF(2^m)数学家换了一种思路不再把元素看成单个数字而是看成系数在 GF(2) 上的多项式。GF(2^m) 的每个元素都是一个次数不超过 m-1 的多项式每一项的系数只能是 0 或 1。比如 GF(2^4) 里的元素可以写作 a3·x^3 a2·x^2 a1·x a0其中所有 ai 都属于 {0,1}。这种表示方法非常容易映射到二进制直接把多项式的系数当成一个 m 位二进制串低位对齐。比如多项式 x^3 x 1 对应二进制 1011对应十六进制 0xB多项式 x^2 1 对应二进制 0101对应十进制 5。从这个角度看GF(2^m) 里的“数字”本质上是一个二进制向量只不过这个向量被赋予了多项式的代数结构。有人会问为什么非要用多项式直接用整数模 2^m 不行吗不行。因为整数模 2^m 的乘法不能保证每个非零元素都有逆元比如 2 在模 16 下没有逆元。多项式表示配合特定的“模约化”规则才能得到一个真正的域。这套设计是整个扩展域生成的核心逻辑。2.2 不可约多项式决定了商结构的边界多项式之间可以做加法和乘法但两个次数不超过 m-1 的多项式相乘后次数可能超过 m-1。例如在 GF(2^4) 里(x^3 1) × (x^3 x) x^6 x^4 x^3 x。这个结果次数是 6超过了 3所以不是域内的合法元素。要让乘法结果落回 m 次以内必须引入模约化选一个固定的 m 次不可约多项式 p(x)把任何超过 m-1 次的多项式都对 p(x) 取余数。这里的关键在于 p(x) 必须不可约也就是不能分解成两个次数更低的多项式乘积。只有选了不可约多项式商环 GF(2)[x]/(p(x)) 才是一个域。这个概念可以类比整数里的素数素数不可被进一步分解所以模素数后的剩余类构成域同样不可约多项式“扮演”了多项式世界里的素数角色。整数的模约化靠除法取余数多项式的模约化也靠多项式长除法取余数两者在思想上是完全同构的。实际做模约化的时候可以利用一个非常朴素的技巧因为 p(x) 是 m 次而 x^m 对 p(x) 取余等于 p(x) - x^m在特征 2 下就是 p(x) x^m。当我们算到乘积之后只要从高位开始不断用这个等价关系把高于 m-1 次的项替换掉直到所有项次数都小于 m。这个技巧在代码里就表现为“移位后异或”后面第 5 节会具体展示。2.3 值得说透的等效多项式关系如果说“扩展域长出来”的过程有个总开关那就是本原多项式给出的一个关键等式。假设我们选定一个 m 次不可约多项式 p(x)并且它在 GF(2^m) 里有一个根 α那么根据“根的定义”一定有p(α)0如果 p(x) x^4 x 1就得到α^4 α 1 0因为特征 2 下加法和减法一样所以α^4 α 1这是一个特别要紧的式子。它告诉我们“α 的 4 次方”并不会跑到域外去而是等价于一个低次多项式“α1”。每一次我遇到高于 3 次的 α 幂都可以反复用这个等式把它降下来。域运算里的所有“取模”最终都可以归结为这条等式的一次次套用。这也正是扩展域元素生成过程里最核心的一步。不要小看这个降幂操作。它看起来像代数变形其实就是多项式除法的简称。你可以在纸上手动做多项式长除法也可以用这个递推等式快速心算。后面第 5 节我会把整个 GF(2^4) 的 15 个非零元素全部列出来每一步都由这个等式驱动。3. 元素生成的核心本原多项式与生成元 α3.1 不可约还不够要能“循环”起来不可约多项式保证了域结构存在但元素生成还差一口气我们想用最省力的方式枚举出域里全部非零元素。最好的办法是找一个“生成元”。如果某个元素 g 的 0 次幂、1 次幂、2 次幂……能把所有非零元素都遍历一遍我们就叫它本原元。不是所有不可约多项式的根都能当本原元。如果一个不可约多项式的根不能生成全部非零元素这个多项式只是不可约不是本原。本原多项式的要求更严格它必须是某个本原元 α 的极小多项式。把这条要求翻译成容易操作的语言就是——α 在域里的乘法阶必须恰好等于 2^m - 1也就是 α^(2^m-1)1并且对任何更小的正整数 kα^k 都不等于 1。这里面的“恰好”至关重要。如果 α 的周期短了重复出现的地方就会提前到来遍历到的元素数量比全部非零元素少那这个 α 就无法生成整个域。判断一个多项式是本原还是仅仅不可约通常需要查表或借助计算机代数系统。工程实现中我们常常直接查现成的本原多项式表而不是现场验证。3.2 α 的幂直接是全部非零元素一旦选定了本原多项式 p(x)并且让 α 是它的根整个 GF(2^m) 的非零元素就可以统一写成 α 的幂α^0, α^1, α^2, ..., α^(2^m-2)这些幂总共正好有 2^m - 1 个再加上零元素就凑齐了 2^m 个元素。这是指数视角的表示方法。它和多项式视角之间的桥梁就是第 2.3 节那个降幂等式。任意一个幂 α^i只要 i ≥ m就不断用等式降下来最终得到一个次数小于 m 的多项式反过来任意一个非零多项式都可以表示成某个唯一的 α^i。这个“一一对应”关系非常值钱它是后面指数对数查表法的全部依据。为什么说这件事“值钱”因为一旦建立了指数表示乘法就变成了指数加法α^i × α^j α^(ij)只需要注意指数相加的模数是 2^m - 1超过这个值就循环回 0。这样复杂的多项式乘法和模约化就被压缩成了一个整数加法。代价是把多项式表示转成指数表示需要查一张对数表把指数表示转回多项式表示需要查一张指数表。表换时间归根结底还是那个经典的工程权衡。3.3 常用本原多项式查表为了避免每次构造域时都现场验算工程上通常会直接用权威本原多项式。下面是我常用的几个做嵌入式或者算法移植时可以直接抄域本原多项式多项式的十六进制/二进制表示GF(2^2)x^2 x 10b111GF(2^3)x^3 x 10b1011GF(2^4)x^4 x 10b10011GF(2^8)x^8 x^4 x^3 x 10x11BGF(2^16)x^16 x^12 x^3 x 10x1100BAES 用的就是 GF(2^8) 和多项式 0x11B这也是为什么你在各类密码学代码里总能看到这个常数。Reed-Solomon 在不同应用场景会选用不同本原多项式要根据码长、生成多项式、纠错能力这些因素综合考虑。有一点要特别注意二进制表示里最高位代表 x^m所以 GF(2^4) 的本原多项式 x^4x1 对应二进制 10011共 5 位。截断成 4 位是常见错误会导致整个域的乘法运算表对不上。4. 运算原理详拆加法、乘法、幂与求逆4.1 加法比特级 XOR简单到能上硬件GF(2^m) 的加法每一比特都独立做模 2 加法。两个 m 位多项式相加先对齐位数然后逐位异或。比如 GF(2^4) 里(x^3 x 1) (x^2 x) x^3 x^2 1对应二进制就是 1011 XOR 0110 1101。没有进位没有借位连个加法器都用不上硬件上拉几条 XOR 门就能完事。这是二进制域在通信和密码芯片里极度流行的原因之一加法电路极其便宜速度极快。由于特征 2加法等于减法所以“校验码”这类计算里天然能容忍数据被重复异或因为两个相同的项会直接抵消。这在实现 Reed-Solomon 编码中的伴随式计算时可以简化很多边界判断不必像普通整数域那样区分加减符号。4.2 乘法多项式相乘后再模回来GF(2^m) 的乘法分两步。第一步两个 m 位多项式按普通多项式乘法展开注意所有系数都是模 2 的同类项会合并或抵消第二步用本原多项式 p(x) 对结果做模约化把次数压回 m-1 以下。举个例子就更清楚了。在 GF(2^4) 中计算 (x^2 1) × (x^3 x)展开x^5 x^3 x^3 x x^5 (x^3 x^3) x x^5 x注意中间 x^3 出现两次在模 2 下 2·x^3 0所以直接消掉。然后用 p(x)x^4x1 来降幂。因为 x^4 x1所以x^5 x·x^4 x·(x1) x^2 x因此 x^5 x (x^2 x) x x^2最终结果就是 x^2。这个过程如果用二进制计算会变成纯位运算先无进位乘法再按位异或约化。很多文档直接给出一张乘法表其实就是对所有可能的输入组合执行了这个两步骤过程。4.3 快速幂与乘法逆元有限域的幂运算可以直接套用整数里的快速幂思路。要算 a^kk 写成二进制按位决定是否乘入当前结果同时不断自乘底数。因为域乘法封闭中间结果不会溢出效率也高。比幂运算更重要的是乘法逆元。在 GF(2^m) 里任意非零元素 a 都满足 a^(2^m - 1) 1所以 a 的乘法逆元就是a^(-1) a^(2^m - 2)这个公式可以直接用来求逆代价是要做指数为 2^m - 2 的快速幂大约需要 O(m) 次域乘法。在 GF(2^4) 里求逆就是计算 a^14在 GF(2^8) 里求逆就是计算 a^254。AES 的 S-Box 构造里就大量使用这个思路先求乘法逆元再做仿射变换。当然也可以用扩展欧几里得算法在多项式环上求逆但相比之下指数公式代码更短不容易写错边界条件。4.4 指数对数视角为什么一张表能解决所有乘法既然每个非零元素都能唯一表示成 α^i那我可以预先构建两张表指数表 exp[i]给出 α^i 对应的多项式二进制值对数表 log[v]给出非零元素 v 对应的指数 i建表完成后乘法就变成a × b exp[(log[a] log[b]) mod (2^m - 1)]这个技巧把最复杂的多项式乘法和模约化完全转化成查表和模加。我第一次看到这个优化时确实觉得被打开了一扇门查表看似是牺牲内存换速度实际上对嵌入式平台而言往往也是降低延迟的最佳方案。一个 2^m 大小的对数表加一个同样大小的指数表总共 2^(m1) 个条目的存储对 m ≤ 16 的场景完全可接受。除了乘法除法也能用同样的办法a / b exp[(log[a] - log[b]) mod (2^m - 1)]。注意这里因为特征 2减法和加法在底层一致但在指数运算里log[b] 可能比 log[a] 大所以必须先加模数再取模避免出现负数索引。5. 手推 GF(2^4)从生成元到完整运算5.1 选定本原多项式 p(x)x^4x1理论说了那么多现在动手推一个完整的 GF(2^4)。这个域一共有 16 个元素。选定本原多项式p(x) x^4 x 1令 α 是 p(x) 的根则得到降幂核心公式α^4 α 1所有运算都由这一条等式驱动。只要遇到 α^4 或者更高次幂就把 α^4 替换成 α1然后继续合并同类项。5.2 元素表同一元素的三种身份从 α^0 开始不断乘以 α再用上面的公式降幂可以推得全部 15 个非零元素。过程如下α^0 1α^1 αα^2 α^2α^3 α^3α^4 α 1α^5 α^2 αα^6 α^3 α^2α^7 α^4 α^3 α^3 α 1α^8 α^4 α^2 α (α1) α^2 α α^2 1α^9 α^3 αα^10 α^4 α^2 (α1) α^2 α^2 α 1α^11 α^3 α^2 αα^12 α^4 α^3 α^2 (α1) α^3 α^2 α^3 α^2 1α^13 α^4 α^3 α (α1) α^3 α α^3 1α^14 α^4 α (α1) α 1到 α^14 之后再乘一次 α 就会得到 1所以 α^15 α^0 1。这意味着非零元素的乘法周期正好是 15等于 2^4 - 1。这个“恰好等于”说明 α 确实是本原元也说明我们选对了本原多项式。把这张表整理成工程里常用的多项式、二进制、十进制三列对照指数表示多项式表示4 位二进制十进制数值0000000α^0100011α^1α00102α^2α^201004α^3α^310008α^4α100113α^5α^2α01106α^6α^3α^2110012α^7α^3α1101111α^8α^2101015α^9α^3α101010α^10α^2α101117α^11α^3α^2α111014α^12α^3α^21110113α^13α^3110019α^14100011注意十进制数值很容易让人误以为这里做的是普通整数乘法实际上完全不是。比如 α^14 的多项式写出来就是 1所以它和 α^0 在多项式表示上完全相同这是对的——因为指数周期是 15两个相差 15 的幂对应同一个元素。5.3 验证两套乘法算法结果一致现在拿刚才那个例子再验算一遍x^2 1 对应二进制 0101也就是十进制 5x^3 x 对应二进制 1010也就是十进制 10。用指数法计算 5 × 10查表log[5] 8log[10] 9指数相加得到 17对 15 取模得到 2。exp[2] 0100对应 x^2。这和第 4.2 节多项式乘法的结果完全一致。再用代码跑一遍整个 GF(2^4) 的生成和乘法方便你把算法抄到自己的项目里。下面这一段是短小但完整的 Python 实现def make_gf16(poly_p0b10011): exp [0] * 15 log [0] * 16 v 1 # α^0 for i in range(15): exp[i] v log[v] i v 1 if v 0b10000: # 出现 x^4 项需要约化 v ^ poly_p # 用 x^4 x 1 消去高次项 return exp, log def gf16_mul(a, b, exp, log): if a 0 or b 0: return 0 return exp[(log[a] log[b]) % 15] exp, log make_gf16() print(exp) # [1, 2, 4, 8, 3, 6, 12, 11, 5, 10, 7, 14, 13, 9, 1] print(gf16_mul(5, 10, exp, log)) # 4对应 x^2这段代码里v 1相当于多项式乘以 α如果第 4 位变成了 1说明出现了 x^4 项就用异或本原多项式把它“约”回去。这正好对应手推步骤里的 α^4 α1。这里我故意把 15 个 exp 全部列出来方便做对照测试第四行打印结果 4和前面手推一致。6. 工程落地时的常见错误与性能取舍6.1 别把非本原不可约多项式当成生成规则工程上最容易踩的坑是把“不可约”和“本原”混为一谈。随便找一个不可约多项式就能定义域但如果它给出的根不是本原元那么按指数表生成一遍会发现遍历的前几个元素就开始循环根本覆盖不了全部非零元素。最典型的是 GF(2^4) 里x^4 x^3 x^2 x 1 也是不可约多项式但用它来生成会得到较短的周期结果就是乘法表错得一塌糊涂。我调试老代码时见过这类 Bug算法看起来没问题乘法表也算出来了但和硬件模块联调时 CRC 或 RS 校验码始终对不上。最后逐项对比才发现根因是本原多项式选错。所以我的建议是所有乘法或者逆元计算都先用小型白盒测试跑一遍比如对 GF(2^4) 验证 α^15 是不是回落到 1对 GF(2^8) 验证 0x02 的 255 次方是不是 1。只要这两个成立基本能确认生成规则没问题。6.2 0 没有逆元边界条件的处理0 是唯一一个不能参与乘法逆的元素。逻辑上这是自然的但工程实现里很容易在查表法里漏掉这个边界。如果直接查log[0]任何实现都会返回一个无意义的索引或者破坏后续计算。在实现除法或者求逆的函数时必须在入口处判断输入是否为 0。这类代码错误通常不会立刻报错而是会在统计计算里悄悄引入异常值最难排查。我在 AES S-Box 的实现里也踩过类似的坑。S-Box 的第一步是对每个字节求 GF(2^8) 的乘法逆元但字节 0x00 的逆元按 AES 规范要映射成 0x00而不是去查表得到一个非法值。也就是说逆元的边界策略要按业务规则单独处理不能拿到哪一帧都机械套公式。写代码时把这些边界条件显式写成注释会让后续维护的人少掉很多头发。6.3 查表与实时计算的取舍查表法的优势是快缺点是表格大小随 2^m 指数增长。对 GF(2^8)指数表和对数表各 256 项一共 512 个字节随便一个嵌入式芯片都放得下。对 GF(2^16)两张表各 65536 项每项至少两个字节总内存超过 256 KB很多资源紧张的设备就不再愿意全量建表了。此时可以考虑混合方案小表存多项式约化表乘法实时做只对高频使用的小型域建全量表或者只建指数表对数表靠离散对数在线求解。性能方面还有另一个细节查表法虽然减少了计算量但破坏了常规的 CPU 流水线预测频繁查表时的 cache miss 开销也很大。在软件实现里如果 m 较小比如 GF(2^4)实时位运算甚至比查表更快在硬件实现里XOR 门的链路延时通常远低于查 ROM 的访问延时。所以选型应该根据目标平台的存储层次和硬件资源来决定不能一概而论。在我自己的算法库演进过程中最后的结论是分层设计小域用全表中域用半表大域用纯计算。没有哪种方案是银弹但把任何一层做好都需要先彻底理解元素生成和运算原理。有了这套基础再根据系统瓶颈去调整才不会在被问到“加法为什么能用 XOR”“乘法为什么要模一个多项式”时心里发虚。