4 · 有限域与多项式

$\mathbb{F}_p$ 只能有质数个元素。但 AES 要 256 元、Reed–Solomon 要 $2^n$ 元。这些 $\mathbb{F}_{p^n}$ 怎么造出来？答案是多项式。本节是编码与对称密码的数学地基。

一、多项式环 $\mathbb{F}_p[x]$

系数取自 $\mathbb{F}_p$ 的多项式集合，配上多项式加乘，成一个环。它与整数环 $\mathbb{Z}$ 惊人地相似：有「质多项式」（不可约）、有带余除法、有唯一分解。

二、用不可约多项式造 $\mathbb{F}_{p^n}$

类比：$\mathbb{Z}_p$ = 整数模一个质数；$\mathbb{F}_{p^n}$ = 多项式模一个「质多项式」（次数 n、不可在 $\mathbb{F}_p$ 上分解）。元素是所有次数 < n 的多项式，共 $p^n$ 个。

例：$\mathbb{F}_{2^8}$（AES）用不可约多项式 $x^8+x^4+x^3+x+1$。元素就是 8 位比特串（一个字节）。

三、有限域上的运算

• 加法：系数逐位模 p 相加。特征 2 时就是异或（XOR）。
• 乘法：多项式相乘后，再模那个不可约多项式取余。
• 逆元：用多项式版的扩展欧几里得算法求（与整数模运算求逆元同一思路：解 $a(x)s(x)+m(x)t(x)=1$）。

四、本原元与乘法循环群

关键事实：有限域的非零元在乘法下构成循环群（计 $p^n-1$ 个元）。能生成它（反复自乘能跑遍所有非零元）的元叫本原元（primitive element）。有了本原元，离散对数、查表乘法都成为可能。

五、为什么这是 Reed–Solomon 的地基

RS 码把 k 个数据块看成 $\mathbb{F}_{2^n}$ 上一个次数 < k 的多项式的系数，在 n>k 个点求值得到带冗余的编码块；任取其中 k 个点就能唯一插值恢复出原多项式，也就恢复了数据。本节讲的有限域构造，正是「为什么能在 $2^n$ 元域上做这些运算」的结构根据。QR 码、光盘纠错、以太坊 Danksharding 都是同一套。

六、数字例题（步步算）

在 $\mathbb{F}_{2^3}$（不可约多项式 $x^3+x+1$）中算 $x^2\cdot x^2$。

$x^2\cdot x^2=x^4$。模 $x^3+x+1$：因 $x^3\equiv x+1$，所以 $x^4=x\cdot x^3\equiv x(x+1)=x^2+x$。结果是 $x^2+x$（位串 110）。

七、Python 代码（GF(2^8) 乘法）

def gf_mul(a, b, mod=0x11B):      # AES 的 GF(2^8) 乘法
    p = 0
    for _ in range(8):
        if b & 1:
            p ^= a
        b >>= 1
        carry = a & 0x80
        a = (a << 1) & 0xFF
        if carry:
            a ^= (mod & 0xFF)
    return p

print("0x57 · 0x83 in GF(2^8) =", hex(gf_mul(0x57, 0x83)))   # 0xc1

# 生成元验证：3 能生成 GF(2^8) 全部 255 个非零元
seen, x = set(), 1
for _ in range(255):
    x = gf_mul(x, 3)
    seen.add(x)
print("3 是本原元？", len(seen) == 255)

八、动手想一想

1. $\mathbb{F}_{2^8}$ 与 $\mathbb{Z}_{256}$ 都有 256 个元，本质区别是什么？
2. 为什么特征 2 的域里「加法和减法是同一个操作」？
3. 不可约多项式选错会怎样？

答案：(1) $\mathbb{F}_{2^8}$ 是域（人人可逆），$\mathbb{Z}_{256}$ 只是环（很多元无逆）；乘法规则完全不同。(2) 特征 2 时 $-1=1$，所以 $a-b=a+b=a\oplus b$。(3) 若多项式可约，商环会出现零因子，不再是域，部分元素失去逆元。

小结：有限域 $\mathbb{F}_{p^n}$ 是「多项式模一个不可约多项式」造出来的，它让 AES、纠错码这些需要 $2^n$ 个元素的场景有了精确可逆的运算。