伽罗华域GF(2^m)全解析：从本原多项式到运算实践

双击任意位置可以查看完整笔记。完整的表我放在这里大家可以对照着做乘法。如果是GF(2^8)就是下面这张表的“放大版”原理完全一样只是本原多项式换了、表变大了而已。2. 有限域元素到底是怎么“长”出来的2.1 三种表示法幂、多项式、二进制GF(2^m)里的每一个元素其实有三种等价的“面孔”。理解这三种表示法是理解整个伽罗华域的关键因为你会在不同场合需要切换到不同的表示形式。第一种是指数形式。把本原多项式的一个根记为α那么域里的所有非零元素都可以写成α^0、α^1、α^2……一直到α^(2^m-2)一共2^m-1个。0比较特殊它不在这个循环里后面专门说。这种表示的价值在于乘法特别好算α^i × α^j α^(ij)指数相加就行不需要做多项式乘法。第二种是多项式形式。每个元素被看成是一个m-1次多项式系数只能在{0,1}里取。比如GF(2^4)里一个元素可能是x^3 x 1也可能是x^2 1。这种表示的好处是加法直接对应系数异或但乘法需要先展开、再模约化稍微麻烦一点。第三种是二进制/十六进制形式。把多项式系数从高次到低次排成一排就是一个m位的二进制数。x^3 x 1对应二进制1011也就是十六进制0xB。计算机处理的其实就是这个数所有域运算最终都会落到整数加减、移位、异或这些底层操作上。我把三种形式对应起来看以GF(2^4)为例指数形式多项式二进制十六进制α^0100010x1α^1x00100x2α^2x^201000x4α^3x^310000x8α^4x 100110x3α^5x^2 x01100x6α^6x^3 x^211000xCα^7x^3 x 110110xBα^8x^2 101010x5α^9x^3 x10100xAα^10x^2 x 101110x7α^11x^3 x^2 x11100xEα^12x^3 x^2 x 111110xFα^13x^3 x^2 111010xDα^14x^3 110010x9α^1510001回到α^0注意α^15又变回了1说明这15个非零元素形成了一个闭合循环这正是本原多项式“本原”二字的来源。2.2 本原多项式决定整个域长相的“宪法”既然α是某个多项式的根那这个多项式的选择就至关重要。这里涉及两个概念不可约多项式和本原多项式。不可约多项式类似整数里的素数它不能被分解成两个更低次多项式的乘积系数仍在GF(2)里。但不可约还不够——如果选的不可约多项式不是本原的就会导致元素周期不到2^m-1就开始重复域表直接“缩水”。举个不严格的例子就好比你要跑一个15天的循环赛程结果运动员第5天就绕回来了后面的对手全都没碰到。本原多项式必须额外满足一个条件它的根α的乘法阶正好是2^m-1。也就是说α^1到α^(2^m-1)遍历所有非零元素直到最后α^(2^m-1)才等于1。选对了本原多项式元素生成才有完整周期。实际工程里常见的选择已经固化下来了我列几个常用的域多项式十六进制常见场景GF(2^4)0x13x^4x1教学、小型验算GF(2^8)0x11Bx^8x^4x^3x1AES加密GF(2^8)0x11Dx^8x^4x^3x^21Reed-Solomon、QR码GF(2^16)0x1100Bx^16x^12x^3x1某些RS纠错、存储系统写代码时通常只需要存“去掉最高位后的低字节”。比如0x11B完整展开是1 0001 1011去掉最高位的1之后剩下0x1B代码里写poly0x1B就够了因为进位约化时正好用它和左移后的结果异或。2.3 手算生成GF(2^4)完整域表纸上得来终觉浅我带着大家手算一遍GF(2^4)的域表。选本原多项式x^4 x 1也就是说α^4 α 1 0。在系数模2的世界里减等于加所以这个等式可以改写成α^4 α 1这条规则是后面所有递推的核心只要看到α^4就把它替换成α1。从α^01开始α^0 1α^1 x记为0x2α^2 x^2记为0x4α^3 x^3记为0x8α^4按规则替换等于x1记为0x3α^5 α^4·α (x1)·x x^2x记为0x6α^6 (x^2x)·x x^3x^2记为0xCα^7 (x^3x^2)·x x^4x^3把x^4换成x1得到x^3x1记为0xBα^8 (x^3x1)·x x^4x^2x替换x^4后得到x^21记为0x5α^9 (x^21)·x x^3x记为0xAα^10 (x^3x)·x x^4x^2替换后得到x^2x1记为0x7α^11 (x^2x1)·x x^3x^2x记为0xEα^12 (x^3x^2x)·x x^4x^3x^2替换后得到x^3x^2x1记为0xFα^13 (x^3x^2x1)·x x^4x^3x^2x替换后得到x^3x^21记为0xDα^14 (x^3x^21)·x x^4x^3x替换后得到x^31记为0x9α^15 (x^31)·x x^4x替换后得到1回到起点算完这串递推你会发现两个细节第一整个过程每次只须做一次“乘以x”而“乘以x”在二进制里其实就是左移一位溢出的话就异或本原多项式的低字节这直接对应了后面代码里的移位XOR算法第二0x1到0xF十五个非零值全出现了恰好各一次这就是本原多项式保证的“全遍历”。我强烈建议读者自己动手算一遍GF(2^4)甚至GF(2^8)的前面若干项。我当年第一次看AES源码时头疼为什么乘一个0x02要左移加异或直到手算了一张域表才真正通透了。3. 有限域四种运算的原理、图解与代码实现先建立一个整体认知GF(2^m)里所有的运算都是“先按普通规则算再对结果做模约化”。加法和减法最简单因为系数模2异或就是一切乘法和除法稍微绕一些需要借助域表或者移位算法。3.1 加法就是按位异或GF(2^m)中两个元素的加法对应两个多项式逐项相加系数按模2相加。系数110所以本质上就是按位异或。比如在GF(2^4)里(x^3 x 1) (x^2 1) x^3 x^2 x也就是0xB ^ 0x5 0xE。用十六进制算就是0xB XOR 0x5得到0xE一模一样。更妙的是在GF(2^m)里减法和加法完全相同因为110所以负x就是x本身。这意味着平时我们头疼的“借位减法”在这里消失了一个XOR操作同时搞定加和减。对于习惯十进制思维的人这是第一个需要转弯的地方。在代码层面加法根本不需要函数直接写a ^ b。很多搞密码学的人会把加法和异或混着说原因就在这里。3.2 乘法多项式相乘后模本原多项式乘法分两步先做普通的多项式乘法注意系数仍然是模2的所以同类项合并时用XOR再对结果做模本原多项式的约化把次数压回m-1以内。举一个GF(2^4)的例子计算0x3 × 0xC也就是(x1) × (x^3x^2)第一步展开x·x^3 x·x^2 1·x^3 1·x^2 x^4 x^3 x^3 x^2。中间两项x^3的系数是110互相抵消于是结果是x^4 x^2。第二步约化x^4用x1替换因为α^4α1得到(x1)x^2 x^2x1十六进制0x7。验算一下在域表里0x3α^40xCα^6α^(46)α^100x7结果一致。这种验算方式在调试代码时非常好用。接下来是工程实现。最经典的移位XOR算法本质就是“二进制乘法竖式异或加法”def gf_mul(a, b, poly0x1B, mask0xFF): result 0 while b: if b 1: result ^ a b 1 high a mask ((-1 7) mask) # 取a的最高位 # 更严谨一点可以写成: high a (1 (m - 1)) a (a 1) mask if high: a ^ poly return result这段代码的逻辑是遍历乘数b的每一位如果当前位是1就把被乘数a异或进结果随后a左移一位相当于乘以x如果左移前最高位是1说明乘出了x^m项需要异或poly做约化。我自己写代码时会把mask这个参数也传进去方便在不同位宽下复用。上面的写法里high a (1 (m - 1))最直观m就是域的位数。以GF(2^8)为例poly0x1Bmask0xFF。一个简单的验证gf_mul(0x02, 0x03)应该得到0x01因为0x02是x0x03是x1乘积是x^2x模本原多项式后仍为x^2x0x06不对这里举例需要小心。0x02α^10x03α^4α^1·α^4α^50x06所以gf_mul(0x02,0x03)0x06。我之前试算时用错指数了。正确的黄金验证对应该找类似0x03×0x0C0x07这样的或者直接用域表索引验证。3.3 求逆AES的S-box幕后功臣在GF(2^m)里每个非零元素a都有唯一的乘法逆元a^(-1)满足a·a^(-1)1。这个操作在密码学里极为重要因为AES的S-box第一步就是计算每个字节在GF(2^8)里的乘法逆元。求逆有两大思路。第一是费马小定理路线。GF(2^m)的乘法群阶是2^m-1所以a^(2^m-1)1于是a^(-1) a^(2^m - 2)在GF(2^8)里就是a^254。用快速幂配合gf_mul函数就能实现def gf_pow(a, n, poly0x1B, mask0xFF): result 1 while n: if n 1: result gf_mul(result, a, poly, mask) a gf_mul(a, a, poly, mask) n 1 return result def gf_inv(a, poly0x1B, mask0xFF): return gf_pow(a, 0xFE, poly, mask) # 254第二种是扩展欧几里得算法。它与整数版的扩展欧几里得几乎一样只是把“整数除法”换成“多项式除法”把“数的大小比较”换成“多项式次数比较”。这种方法的运算量通常比快速幂低但代码写起来更绕。对工程而言最方便的还是查表域表里已经记录了每个元素的指数i它的逆元就是α^(255-i)一次查表加一次取模即可。这里给个小提示如果你在写AES的S-box网上很多现成的S-box表其实已经把“求逆仿射变换”揉在了一起。你如果要自己实现建议先独立算一遍S-box再和标准表对一下对得上说明你的求逆函数是对的。3.4 对数表如何把乘法变加法既然α^i × α^j α^(ij)那只要预先建立“元素值→指数”和“指数→元素值”两张表就能把乘法从耗时的移位循环变成两次查表和一次加法。这对高吞吐场景特别有价值。建表方法也很直接用gf_mul(0x02)不断累乘记录每个指数对应的元素值再反向记录对数。核心代码如下def build_galois_tables(poly0x1B, m8): size (1 m) - 1 exp [0] * (size 1) # exp[i] α^i log [0] * (1 m) # log[x] ix α^i x 1 for i in range(size): exp[i] x log[x] i x gf_mul(x, 0x02, poly, (1 m) - 1) exp[size] exp[0] return exp, log def gf_mul_table(a, b, exp, log): if a 0 or b 0: return 0 return exp[(log[a] log[b]) % 255] def gf_div_table(a, b, exp, log): if b 0: raise ZeroDivisionError(GF域中不能除以0) if a 0: return 0 return exp[(log[a] - log[b] 255) % 255]注意两个细节。其一0没有对数所以查表前必须判零。其二模数不是256而是255因为非零乘法群的阶是2^m-1。做Reed-Solomon编解码时这种表驱动方式几乎是标配。AES里很多查表实现也类似把有限域乘法和仿射变换预先融合成四个T表提升加解密速度。4. 实际项目中踩过的四个大坑4.1 本原多项式选错域表会“提前闭环”有段时间我给一个自定义的RS纠错模块选本原多项式图省事随便拿了一个不可约但没有验证本原性的8次多项式。结果生成的域表跑到第51项就开始循环后面的元素全部错乱。排查时最明显的症状就是“乘法器在某些特定输入组合下永远返回1”这是域表周期严重缩水的典型表现。所以拿到一个多项式第一步先用代码验证它的“遍历性”从α^0开始连续乘以α统计能到达多少个不同的非零元素。如果数量正好是2^m-1才有资格当本原多项式。严谨起见还可以遍历2^m-1的所有真因子d确认α^d都不等于1这样能进一步排除那些“只在部分指数上表现为遍历”的假本原。4.2 0元素查对数表是典型的隐蔽错误用表驱动乘法时我见过无数人包括我自己在最开始写出这样的代码return exp[(log[a] log[b]) % 255]然后当a和b都不为0时一切正常一旦某个值为0结果就莫名其妙。原因很简单0不在乘法群里log[0]没有意义。很多语言里数组初始化为0导致log[0]恰好是0查出来变成α^0·α^b的假结果。正确做法是先判零if a 0 or b 0: return 0千万别省这一步。我在项目里甚至建议把判零逻辑封装在同一个函数里避免调用方忘记。4.3 表驱动与实时计算没有绝对好坏只有场景适配表驱动的优势是快适合加密、编解码这种热点路径。实时计算的优势是不需要初始化、不占内存适合RAM紧张的嵌入式环境。我自己的经验是方案初始化耗时单次乘法开销内存占用典型场景移位XOR实时计算无几十个时钟周期0MCU、FPGA软核对数/反对数表毫秒级查表加法512字节GF(2^8)RS编解码、高速存储字段专用硬件无1个时钟周期逻辑资源硬件S-box、纠错引擎在嵌入式里我一般用移位XOR实现。在服务端、Android/iOS端跑RS纠错我直接用对数表。如果初始化时间可以接受表驱动几乎总是更优解。4.4 同一个十六进制值在不同域里含义可能完全不同这是最隐蔽的坑。0x02在GF(2^8)的任意本原多项式下都表示x所以都是α。但0x03在不同本原多项式下的“指数位置”不一样。比如在0x11B域里0x03是α^4在0x11D域里0x03对应的指数是多少需要重新建表才能知道。因此不同本原多项式的log/exp表绝对不允许混用。AES用0x11BRS码和QR码常用0x11D如果你把两者的表搞混结果就是加解密偶尔出错、纠错结果时好时坏。这个问题在联调阶段特别难查因为错误是“间歇性”的。我给自己定了一条规矩所有用到有限域的模块必须在代码里显式标注本原多项式十六进制值和一张提前算好的黄金测试向量表比如gf_mul(0x53, 0xCA) 0x01这类固定的对。每次改配置都先跑一遍向量能挡住绝大部分低级错误。最后分享一个我自己的习惯拿到一个新的本原多项式先手工把域表写到第16项再让程序输出整张表人工核对一遍有没有“断链”。这一步看起来原始但比任何调试器都好使。域表对了后面的乘法器、求逆、RS纠错、AES S-box全部都会顺起来。