有限域上的算术

域的构造与元素表示

考虑有限域 F16F_{16} 的构造。我们将其看作是 F2F_2 的单代数扩张 F16=F2(α)F_{16} = F_2(\alpha)。
选取 F2F_2 上的一个 4 次不可约多项式：

p(x)=x4+x+1p(x) = x^4 + x + 1

1. 验证 p(x)p(x) 的不可约性
要证明 p(x)p(x) 在 F2F_2 上不可约，需验证它没有低次因子：

  • 无一次因子（无根）：
    代入 00：p(0)=1≠0p(0) = 1 \neq 0
    代入 11：p(1)=1+1+1=1≠0p(1) = 1 + 1 + 1 = 1 \neq 0
    故 p(x)p(x) 在 F2F_2 上无根，即无一次因子。
  • 无二次因子：
    F2F_2 上唯一的不可约二次多项式是 x2+x+1x^2+x+1。
    做多项式除法：(x4+x+1)÷(x2+x+1)=x2+x…余 1(x^4+x+1) \div (x^2+x+1) = x^2+x \dots \text{余 } 1。
    无法整除，故无二次因子。

综上，p(x)p(x) 是 F2F_2 上的不可约多项式。

2. 构造扩域
令 α\alpha 为 p(x)p(x) 的一个根，即 p(α)=0p(\alpha) = 0。
由此得到基本关系式：

α4+α+1=0  ⟹  α4=α+1\alpha^4 + \alpha + 1 = 0 \implies \alpha^4 = \alpha + 1

注：从抽象代数的角度，这等价于构造商环 F16≅F2[x]/⟨x4+x+1⟩F_{16} \cong F_2[x] / \langle x^4+x+1 \rangle。这里的 α\alpha 对应于商环中 xx 的陪集 xˉ\bar{x}。

3. 元素的枚举
在 F16F_{16} 中，所有元素都可以唯一表示为次数小于 4 的多项式：

β=c3α3+c2α2+c1α+c0,ci∈{0,1}\beta = c_3\alpha^3 + c_2\alpha^2 + c_1\alpha + c_0, \quad c_i \in \{0, 1\}

总共有 24=162^4 = 16 个元素，我们可以按次数对其进行分类：

  • 0 次（及零元素）：
    0,10, \quad 1
  • 1 次：
    α,α+1\alpha, \quad \alpha + 1
  • 2 次：
    α2,α2+1,α2+α,α2+α+1\alpha^2, \quad \alpha^2 + 1, \quad \alpha^2 + \alpha, \quad \alpha^2 + \alpha + 1
  • 3 次（共 8 个）：
    α3,α3+1,α3+α,α3+α+1\alpha^3, \quad \alpha^3 + 1, \quad \alpha^3 + \alpha, \quad \alpha^3 + \alpha + 1
    α3+α2,α3+α2+1,α3+α2+α,α3+α2+α+1\alpha^3 + \alpha^2, \quad \alpha^3 + \alpha^2 + 1, \quad \alpha^3 + \alpha^2 + \alpha, \quad \alpha^3 + \alpha^2 + \alpha + 1

4. 乘法群的循环结构
上述多项式表达虽然适合加法（系数对应相加），但在做乘法时较为繁琐。
为了简化乘法运算，我们利用有限域乘法群的性质：F16F_{16} 的非零元素构成的乘法群 F16∗F_{16}^* 是一个循环群 (Cyclic Group)。

这意味着存在生成元，使得每个非零元素 β∈F16∗\beta \in F_{16}^* 都可以唯一地表示为生成元的幂次。若 α\alpha 是生成元，则有：

F16∗=⟨α⟩={α0,α1,α2,…,α14}F_{16}^* = \langle \alpha \rangle = \{ \alpha^0, \alpha^1, \alpha^2, \dots, \alpha^{14} \}

这引入了元素的指数形式（Power Representation）。

两种表示法的对比

  • 多项式形式（Polynomial Basis）：如上所示的所有形式。非常适合进行加法运算（对应系数模 2 相加）。
  • 指数形式（Power Form）：如 αk\alpha^k。非常适合进行乘法运算。

本原元 (Primitive Element) 的验证

我们需要验证 α\alpha 是否为 F16∗F_{16}^* 的生成元（即本原元）。

  1. 群的阶：∣F16∗∣=24−1=15|F_{16}^*| = 2^4 - 1 = 15。
  2. 验证方法：α\alpha 的阶 (order) 必须是 15 的因子。15 的因子有 1, 3, 5, 15。
    • 显然 α1≠1\alpha^1 \neq 1。
    • 检查 α3\alpha^3：由于次数小于4，显然 α3≠1\alpha^3 \neq 1。
    • 检查 α5\alpha^5：
      利用 α4=α+1\alpha^4 = \alpha + 1，

      α5=α⋅α4=α(α+1)=α2+α≠1\alpha^5 = \alpha \cdot \alpha^4 = \alpha(\alpha+1) = \alpha^2 + \alpha \neq 1

  3. 结论：因为 α3≠1\alpha^3 \neq 1 且 α5≠1\alpha^5 \neq 1，所以 order(α)=15\text{order}(\alpha) = 15。因此，α\alpha 是 F16F_{16} 的本原元。同时 order(p(x))=15order(p(x)) = 15，表明 p(x)p(x) 为本原多项式。

幂次表推导（部分）：

  • α0=1\alpha^0 = 1
  • α1=α\alpha^1 = \alpha
  • α2=α2\alpha^2 = \alpha^2
  • α3=α3\alpha^3 = \alpha^3
  • α4=α+1\alpha^4 = \alpha + 1
  • α5=α(α+1)=α2+α\alpha^5 = \alpha(\alpha + 1) = \alpha^2 + \alpha
  • α6=α(α2+α)=α3+α2\alpha^6 = \alpha(\alpha^2 + \alpha) = \alpha^3 + \alpha^2
  • …
  • α15=1\alpha^{15} = 1

混合运算示例

例：计算 (α8+α4+1)(α3+α)(\alpha^8 + \alpha^4 + 1)(\alpha^3 + \alpha)

(α8+α4+1)(α3+α)= (0101+0011+0001)(1000+0010)= 0111⋅1010= α10⋅α9=α19=α4=α+1\begin{aligned} & (\alpha^8 + \alpha^4 + 1)(\alpha^3 + \alpha) \\ =\ & (0101 + 0011 + 0001)(1000 + 0010) \\ =\ & 0111 \cdot 1010 \\ =\ & \alpha^{10} \cdot \alpha^9 = \alpha^{19} = \alpha^4 = \alpha + 1 \end{aligned}

Frobenius 映射与共轭元

Frobenius 自同构

考虑映射 σ:F16→F16\sigma: F_{16} \to F_{16}，定义为 σ(β)=β2\sigma(\beta) = \beta^2。可以看出如果 β∈F2\beta \in F_2，那么 σ(β)=β\sigma(\beta) = \beta，即 σ\sigma 是 F2F_2-自同构。
对于 F2nF_{2^n}，Galois 群是循环群 ⟨σ⟩\langle \sigma \rangle。
在 F16F_{16} 中，σ4(β)=β16=β\sigma^4(\beta) = \beta^{16} = \beta，那么 ⟨σ⟩={σ0=ι,σ1,σ2,σ3}\langle \sigma \rangle = \{ \sigma^{0} = \iota, \sigma^{1}, \sigma^{2}, \sigma^{3} \}

共轭类与极小多项式

利用代数扩张的性质，F16F_{16} 中所有元素在 F2F_2 上代数。且对于域中元素 β\beta，其在 F2F_2 上的极小多项式 mβ(x)m_\beta(x) 的根是 β\beta 的所有共轭元（即 β\beta 在 σ\sigma 作用下的轨道）。

原因：
极小多项式 mβ(x)m_\beta(x) 的系数属于基域 F2F_2（即伽罗瓦群的不动点域）。因此，对于任意 σ∈G\sigma \in G，自同构 σ\sigma 保持系数不变。若 mβ(β)=0m_\beta(\beta) = 0，对两边施加 σ\sigma：

σ(mβ(β))=mβ(σ(β))=0\sigma(m_\beta(\beta)) = m_\beta(\sigma(\beta)) = 0

这说明如果 β\beta 是根，那么 σ(β)\sigma(\beta) 也一定是根。
因此，mβ(x)m_\beta(x) 的根集恰好就是 β\beta 在 Galois 群作用下的轨道（即共轭类）。

1. α\alpha 的共轭类
计算轨道：

  • α\alpha
  • α2\alpha^2
  • α4=α+1\alpha^4 = \alpha + 1
  • α8=(α+1)2=α2+1\alpha^8 = (\alpha+1)^2 = \alpha^2 + 1
  • α16=α\alpha^{16} = \alpha (循环)

共轭元为 {α,α2,α4,α8}\{ \alpha, \alpha^2, \alpha^4, \alpha^8 \}。
对应极小多项式：mα(x)=(x−α)(x−α2)(x−α4)(x−α8)=x4+x+1m_\alpha(x) = (x-\alpha)(x-\alpha^2)(x-\alpha^4)(x-\alpha^8) = x^4+x+1。

2. α3\alpha^3 的共轭类
计算轨道：

  • α3\alpha^3
  • (α3)2=α6(\alpha^3)^2 = \alpha^6
  • (α6)2=α12(\alpha^6)^2 = \alpha^{12}
  • (α12)2=α24=α15⋅α9=α9(\alpha^{12})^2 = \alpha^{24} = \alpha^{15}\cdot\alpha^9 = \alpha^9
  • (α9)2=α18=α3(\alpha^9)^2 = \alpha^{18} = \alpha^3 (循环)

共轭元为 {α3,α6,α12,α9}\{ \alpha^3, \alpha^6, \alpha^{12}, \alpha^9 \}。
对应极小多项式：mα3(x)=x4+x3+x2+x+1m_{\alpha^3}(x) = x^4 + x^3 + x^2 + x + 1。
注意：(α3)5=α15=1(\alpha^3)^5 = \alpha^{15} = 1，α3\alpha^3 的阶为 5，不是本原元。

3. α5\alpha^5 的共轭类
计算轨道：

  • α5\alpha^5
  • (α5)2=α10(\alpha^5)^2 = \alpha^{10}
  • (α10)2=α20=α5(\alpha^{10})^2 = \alpha^{20} = \alpha^5 (循环)

共轭元为 {α5,α10}\{ \alpha^5, \alpha^{10} \}。
对应极小多项式：mα5(x)=(x−α5)(x−α10)=x2+x+1m_{\alpha^5}(x) = (x-\alpha^5)(x-\alpha^{10}) = x^2 + x + 1。
这说明 F2(α5)≅F4F_2(\alpha^5) \cong F_4 是 F16F_{16} 的子域。

4. α7\alpha^7 的共轭类
类似可得共轭元 {α7,α14,α13,α11}\{ \alpha^7, \alpha^{14}, \alpha^{13}, \alpha^{11} \}。
对应极小多项式：mα7(x)=x4+x3+1m_{\alpha^7}(x) = x^4 + x^3 + 1。

多项式分解应用

利用上述结果，可以将 x15−1x^{15}-1 在 F2F_2 上分解为不可约因子的乘积：

x15−1=∏β∈F16∗(x−β)x^{15}-1 = \prod_{\beta \in F_{16}^*} (x-\beta)

根据共轭类分组：

x15−1=m0(x)m1(x)m3(x)m5(x)m7(x)x^{15}-1 = m_0(x) m_1(x) m_3(x) m_5(x) m_7(x)

  • m0(x)=x+1m_0(x) = x+1
  • m1(x)=x4+x+1m_1(x) = x^4+x+1
  • m3(x)=x4+x3+x2+x+1m_3(x) = x^4+x^3+x^2+x+1
  • m5(x)=x2+x+1m_5(x) = x^2+x+1
  • m7(x)=x4+x3+1m_7(x) = x^4+x^3+1

Berlekamp 因式分解算法

Berlekamp 算法用于在有限域上分解多项式。为方便起见，本节主要考虑 Zp\mathbb{Z}_p 上的多项式。

算法思路与核心公式

设 f(x)∈Zp[x]f(x) \in \mathbb{Z}_p[x]，且 deg⁡(f)=d\deg(f) = d。
我们的目标是寻找一个非平凡的多项式 g(x)∈Zp[x]g(x) \in \mathbb{Z}_p[x]，满足以下条件：

  1. deg⁡(g)≤d−1\deg(g) \le d-1
  2. f(x)∣g(x)p−g(x)f(x) \mid g(x)^p - g(x)

推导过程：

  • 基本恒等式：
    考虑 Zp\mathbb{Z}_p 上的恒等式 xp−x=∏s∈Zp(x−s)x^p - x = \prod_{s \in \mathbb{Z}_p} (x-s)。
    将 g(x)g(x) 代入上式：

    g(x)p−g(x)=∏s=0p−1(g(x)−s)g(x)^p - g(x) = \prod_{s=0}^{p-1} (g(x) - s)

  • 互素性质：
    由于 Zp\mathbb{Z}_p 是域，对于不同的 i,j∈Zpi, j \in \mathbb{Z}_p (i≠ji \neq j)，有 gcd⁡(g(x)−i,g(x)−j)=1\gcd(g(x)-i, g(x)-j) = 1。即 g(x)−ig(x)-i 各项两两互素。

  • GCD 分解公式的证明：
    我们要证明为何 f(x)=∏s=0p−1gcd⁡(f(x),g(x)−s)f(x) = \prod_{s=0}^{p-1} \gcd(f(x), g(x)-s)。

    1. 设 g(x)−ig(x)-i 的分解：
      设 g(x)−ig(x)-i 在 Zp\mathbb{Z}_p 上的不可约因子分解为：

      g(x)−i=fi,1ei,1⋯fi,miei,mig(x)-i = f_{i,1}^{e_{i,1}} \cdots f_{i,m_i}^{e_{i,m_i}}

    2. f(x)f(x) 的结构：
      因为 f(x)∣∏i=0p−1(g(x)−i)f(x) \mid \prod_{i=0}^{p-1} (g(x)-i)，且各个 g(x)−ig(x)-i 互素，所以 f(x)f(x) 的因子必然分布在这些 g(x)−ig(x)-i 中。
      我们可以将 f(x)f(x) 写为：

      f(x)=∏i=0p−1(fi,1ai,1⋯fi,miai,mi)f(x) = \prod_{i=0}^{p-1} \left( f_{i,1}^{a_{i,1}} \cdots f_{i,m_i}^{a_{i,m_i}} \right)

      其中 0≤ai,k≤ei,k0 \le a_{i,k} \le e_{i,k}。这表示 f(x)f(x) 中包含的 g(x)−ig(x)-i 的因子部分。

    3. 提取 GCD：
      考察 gcd⁡(f(x),g(x)−i)\gcd(f(x), g(x)-i)：

      gcd⁡(f,g−i)=fi,1ai,1⋯fi,miai,mi\gcd(f, g-i) = f_{i,1}^{a_{i,1}} \cdots f_{i,m_i}^{a_{i,m_i}}

      这恰好提取了 f(x)f(x) 中属于 g(x)−ig(x)-i 因子的那一缩部分。

    4. 结论：
      将所有部分的 GCD 相乘，即可还原 f(x)f(x)：

      f(x)=gcd⁡(f,gp−g)=∏s=0p−1gcd⁡(f(x),g(x)−s)f(x) = \gcd(f, g^p-g) = \prod_{s=0}^{p-1} \gcd(f(x), g(x)-s)

通过计算 gcd⁡(f(x),g(x)−s)\gcd(f(x), g(x)-s)，我们有望将 f(x)f(x) 分解为更小的因子。

预处理：无重因子 (Square-free)

在进行分解前，不失一般性 (W.L.O.G)，我们只考虑 f(x)f(x) 没有重因子 的情况。

原因分析：

  1. 计算 d(x)=gcd⁡(f(x),f′(x))d(x) = \gcd(f(x), f'(x))。
  2. 若 d(x)=1d(x) = 1，则 f(x)f(x) 无重因子。
  3. 若 d(x)≠1d(x) \neq 1，则 d(x)d(x) 包含 f(x)f(x) 的重因子。
    此时，f(x)f(x) 的分解可以转化为对 f(x)/d(x)f(x)/d(x) 和 d(x)d(x) 的分解。
    因此，我们只需要掌握如何处理无重因子的多项式即可。

结论：在无重因子的假设下，一定存在多个（非平凡）g(x)g(x)，deg⁡(g)<d\deg(g) < d，使得 f∣gp−gf \mid g^p - g。这样的 g(x)g(x) 称为 f-reducing polynomial。

寻找 g(x)g(x) 的线性代数方法

我们要寻找 g(x)=∑i=0d−1gixig(x) = \sum_{i=0}^{d-1} g_i x^i (gi∈Zpg_i \in \mathbb{Z}_p) 满足 f(x)∣g(x)p−g(x)f(x) \mid g(x)^p - g(x)。

推导步骤：

  1. 计算 g(x)pg(x)^p：
    在 Zp\mathbb{Z}_p 中，利用 (a+b)p=ap+bp(a+b)^p = a^p + b^p 和 ap=aa^p = a 的性质：

    [g(x)]p=(∑i=0d−1gixi)p=∑i=0d−1gip(xi)p=∑i=0d−1gixip[g(x)]^p = \left(\sum_{i=0}^{d-1} g_i x^i\right)^p = \sum_{i=0}^{d-1} g_i^p (x^i)^p = \sum_{i=0}^{d-1} g_i x^{ip}

  2. 代入整除条件：

    gp−g=∑i=0d−1gixip−∑i=0d−1gixi=∑i=0d−1gi(xip−xi)g^p - g = \sum_{i=0}^{d-1} g_i x^{ip} - \sum_{i=0}^{d-1} g_i x^i = \sum_{i=0}^{d-1} g_i (x^{ip} - x^i)

    我们需要 f(x)∣∑i=0d−1gi(xip−xi)f(x) \mid \sum_{i=0}^{d-1} g_i (x^{ip} - x^i)。

  3. 多项式模运算：
    对 xipx^{ip} 做带余除法：

    xip=qi(x)f(x)+ri(x),0≤deg⁡(ri)≤d−1x^{ip} = q_i(x)f(x) + r_i(x), \quad 0 \le \deg(r_i) \le d-1

    代回原式：

    f(x)∣∑i=0d−1gi(ri(x)−xi)f(x) \mid \sum_{i=0}^{d-1} g_i (r_i(x) - x^i)

    观察发现，上式右边 ∑gi(ri(x)−xi)\sum g_i (r_i(x) - x^i) 的次数严格小于 dd（因为 deg⁡(ri)<d\deg(r_i) < d 且 deg⁡(xi)<d\deg(x^i) < d）。
    一个次数小于 dd 的多项式若能被 dd 次多项式 f(x)f(x) 整除，它必须恒等于 0。

    因此，我们要解的方程是：

    ∑i=0d−1gi(ri(x)−xi)=0\sum_{i=0}^{d-1} g_i (r_i(x) - x^i) = 0

构造矩阵方程求解

为了求解系数 gig_i，我们进一步展开上述多项式方程。

设 ri(x)=ri,0+ri,1x+⋯+ri,d−1xd−1r_i(x) = r_{i,0} + r_{i,1}x + \cdots + r_{i, d-1}x^{d-1}。
考虑方程中 xjx^j (0≤j≤d−10 \le j \le d-1) 的系数：

对于固定的 jj，系数为：

∑i=0d−1gi(ri,j−δi,j)=0\sum_{i=0}^{d-1} g_i (r_{i,j} - \delta_{i,j}) = 0

其中 δi,j\delta_{i,j} 是 Kronecker delta 符号（当 i=ji=j 时为 1，否则为 0）。

矩阵定义：
定义矩阵 MM 为 d×dd \times d 矩阵，其元素为 ri,jr_{i,j}：

M=def(ri,j)0≤i,j≤d−1M \stackrel{\text{def}}{=} (r_{i,j})_{0 \le i, j \le d-1}

（注：MM 的第 ii 行即为 xip(modf(x))x^{ip} \pmod{f(x)} 的系数向量）

定义系数向量 GG：

G=def(g0,g1,…,gd−1)G \stackrel{\text{def}}{=} (g_0, g_1, \dots, g_{d-1})

最终方程：
上述系数条件等价于线性方程组：

G⋅(M−I)=0G \cdot (M - I) = 0

算法总结：

  1. 求出 G⋅(M−I)=0G \cdot (M - I) = 0 的解空间基底 g0,g1,…g_0, g_1, \dots。
  2. 利用非平凡解构造 g(x)g(x)。
  3. 计算 f=gcd⁡(f,g)⋯gcd⁡(f,g−p+1)f = \gcd(f, g) \cdots \gcd(f, g-p+1) 完成分解。

计算示例

在 Z2\mathbb{Z}_2 上分解 f(x)=x6+x5+x4+x3+x2+1f(x) = x^6 + x^5 + x^4 + x^3 + x^2 + 1。