不同商环上的多项式乘法

深入解析不同商环上的多项式乘法：从理论到实现

在现代密码学（特别是后量子密码学）、纠错码和数字信号处理等领域，多项式环及其商环扮演着至关重要的角色。在这些环上的运算，尤其是多项式乘法，是许多核心算法的性能关键。

本文旨在深入探讨在三种常见的商环上的多项式乘法 h(x) = f(x)g(x)，并为其计算表达式提供完整、详尽的推导。这三种商环分别是：

1. 二次幂分圆环 (Ring of Powers-of-Two Cyclotomic Polynomials): Z_q[x]/(x^n + 1)
2. 三项分圆环 (Trinary Cyclotomic Polynomial Ring): Z_q[x]/(x^n - x^(n/2) + 1)
3. 素阶数域相关的环 (Ring related to prime order fields): Z_q[x]/(x^n - x - 1)

我们将逐一揭示这些结构中多项式乘法的奥秘。

核心概念：商环中的多项式乘法

在进入具体案例之前，让我们先回顾一下商环 Z_q[x]/P(x) 中多项式乘法的基本流程。这里的 Z_q[x] 表示系数在整数模 q 环 Z_q 上的多项式环，而 P(x) 是一个 n 次的模多项式 (modulus polynomial)。

任意两个该商环中的多项式 f(x) 和 g(x)（次数通常小于 n），其乘积 h(x) 的计算都遵循两个基本步骤：

1. 标准多项式乘法： 首先，像在普通多项式环中一样，计算出 f(x) 和 g(x) 的乘积。我们称这个中间结果为 c(x) = f(x)g(x)。如果 f(x) 和 g(x) 的次数都是 n-1，那么 c(x) 的次数最高可达 2n-2。
2. 模约减 (Modular Reduction)： 接着，将 c(x) 对模多项式 P(x) 进行取模运算，得到最终结果 h(x) = c(x) mod P(x)。这一步会将所有次数大于等于 n 的项进行“降次”，直到结果多项式的次数小于 n。

真正的区别和计算技巧，就蕴含在第二步的模约减之中。不同的模多项式 P(x) 对应着完全不同的降次规则，从而产生了不同的计算表达式和算法结构。

情况一：二次幂分圆环

这种结构在基于格的密码学中极为常见，例如 Kyber 和 NTRU 等知名方案。当 n 是 2 的幂时，该环上的多项式乘法可以利用数论变换 (NTT) 进行高效加速。其底层代数结构被称为负折叠卷积 (Negative Wrapped Convolution)。

推导过程

在商环 Z_q[x]/(x^n + 1) 中，我们拥有核心的代数关系：
x^n ≡ -1 (mod x^n + 1)

这个简单的关系是所有计算的关键。

第一步：标准乘法

给定两个 n-1 次多项式：
f(x) = f₀ + f₁x + ... + fₙ₋₁xⁿ⁻¹
g(x) = g₀ + g₁x + ... + gₙ₋₁xⁿ⁻¹

它们的乘积 c(x) 是一个最高 2n-2 次的多项式：
c(x) = f(x)g(x) = c₀ + c₁x + ... + c₂ₙ₋₂x²ⁿ⁻²
其中系数 cₖ = Σ_{i+j=k} fᵢgⱼ。

第二步：模约减

现在，我们对 c(x) 进行约减。可以将 c(x) 拆分为次数低于 n 的部分和次数大于等于 n 的部分：
c(x) = (c₀ + ... + cₙ₋₁xⁿ⁻¹) + (cₙxⁿ + ... + c₂ₙ₋₂x²ⁿ⁻²)

对于后半部分中的任意一项 c_{k+n}x^{k+n} (其中 0 ≤ k)，我们可以利用核心关系进行降次：
x^{k+n} = x^k * x^n ≡ x^k * (-1) = -x^k (mod x^n + 1)

因此，整个后半部分可以被重写为：
cₙxⁿ + ... + c₂ₙ₋₂x²ⁿ⁻² ≡ cₙ(-1) + cₙ₊₁(-x) + ... + c₂ₙ₋₂(-xⁿ⁻²) (mod x^n + 1)
≡ -(cₙ + cₙ₊₁x + ... + c₂ₙ₋₂xⁿ⁻²) (mod x^n + 1)

最后，我们将降次后的部分与 c(x) 的前半部分合并，得到最终的 h(x) = h₀ + h₁x + ... + hₙ₋₁xⁿ⁻¹。h(x) 的第 k 项系数 hₖ 由 c(x) 中 x^k 的系数 cₖ 和 x^{k+n} 的系数 c_{k+n} 共同决定。

h(x) 的计算表达式

hₖ = cₖ - c_{k+n} (mod q)

其中 k 的取值范围是 0, 1, ..., n-1。如果 k+n 超出了 c(x) 的最高次数 2n-2，则 c_{k+n} 视为 0。这个简洁而优美的表达式正是负折叠卷积的定义。

情况二：三项分圆环

Z_q[x]/(x^n - x^(n/2) + 1)

当模多项式是一个三项式时，约减过程会变得稍微复杂。这里我们假设 n 是一个偶数。

推导过程

此环中的核心关系是：
x^n ≡ x^(n/2) - 1 (mod x^n - x^(n/2) + 1)

第一步：标准乘法

和之前一样，我们首先计算 c(x) = f(x)g(x) = Σ cₖxᵏ。

第二步：模约减

对于 c(x) 中任意次数 k ≥ n 的项 cₖxᵏ，我们可以进行如下降次：
x^k = x^{k-n} * x^n ≡ x^{k-n} * (x^(n/2) - 1) = x^{k-n/2} - x^{k-n} (mod x^n - x^(n/2) + 1)

这个规则告诉我们，一个高次项 cₖxᵏ 在降次后，会分裂成两个低次项：它的系数 cₖ 会贡献给 x^{k-n/2} 项，同时它的相反数 -cₖ 会贡献给 x^{k-n} 项。

为了推导一个更具体的表达式，我们将 c(x) 按照 n 次项进行分解：
c(x) = A(x) + B(x)x^n
其中 deg(A)，deg(B)。

h(x) = c(x) mod (x^n - x^(n/2) + 1)
≡ A(x) + B(x)(x^(n/2) - 1)
≡ A(x) - B(x) + B(x)x^(n/2)

让我们进一步分析 B(x)x^(n/2) 这一项。B(x) 的次数小于 n，所以 B(x)x^(n/2) 的次数可能依然大于等于 n。设 B(x) = B₁(x) + B₂(x)x^(n/2)，其中 deg(B₁), deg(B₂)。
那么 B(x)x^(n/2) = B₁(x)x^(n/2) + B₂(x)x^n。再次对 x^n 进行约减：
B₂(x)x^n ≡ B₂(x)(x^(n/2) - 1) = B₂(x)x^(n/2) - B₂(x)。

将所有部分合并，h(x) 的系数 hₖ 由 cₖ 以及来自 c_{k+n/2} 和 c_{k+n} 的贡献组成。

h(x) 的计算表达式

令 $c(x) = Σ{i=0}^{2n-2} cᵢxⁱ。最终h(x) = Σ{k=0}^{n-1} hₖxᵏ$ 的系数表达式为：

• 对于 0 ≤ k:
  hₖ = cₖ - c_{k+n} - c_{k+3n/2} (mod q)

• 对于 n/2 ≤ k:
  hₖ = cₖ + c_{k+n/2} - c_{k+n} (mod q)

(注：此处的索引 k+3n/2 等可能超出 c(x) 的范围，对应的 c 系数视为 0。)

情况三：素阶数域相关的环

Z_q[x]/(x^n - x - 1)
这类环的模多项式 x^n - x - 1 在编码理论和伪随机序列生成中非常重要。它的结构类似于一个线性反馈移位寄存器 (LFSR)。

推导过程

该环的核心关系为：
x^n ≡ x + 1 (mod x^n - x - 1)

第一步：标准乘法

我们照例计算 c(x) = f(x)g(x) = Σ cₖxᵏ。

第二步：模约减

对于任何次数 k ≥ n 的项 cₖxᵏ，其降次规则如下：
x^k = x^{k-n} * x^n ≡ x^{k-n} * (x + 1) = x^{k-n+1} + x^{k-n} (mod x^n - x - 1)

这意味着，一个高次项 cₖxᵏ 的系数 cₖ 会被分别加到 x^{k-n+1} 和 x^{k-n} 这两个低次项的系数上。

与前两种情况不同，这种“移位-相加”的结构很难写出一个简洁的封闭表达式。描述其计算过程的最好方式是使用一个迭代算法。

h(x) 的计算表达式 (算法描述)

我们可以从 c(x) 的最高次项开始，逐项进行降次，直到所有项的次数都小于 n。

1. 初始化： 将 h(x) 的系数向量 (h₀, ..., h_{2n-2}) 初始化为 c(x) 的系数向量 (c₀, ..., c_{2n-2})。
2. 迭代降次： 从最高次项开始，即 k from 2n-2 down to n：
   a. 取出当前 x^k 项的系数 coeff = hₖ。
   b. 将 hₖ 清零。
   c. 将 coeff 加到 x^{k-n+1} 的系数上，即 h_{k-n+1} = h_{k-n+1} + coeff (mod q)。
   d. 将 coeff 加到 x^{k-n} 的系数上，即 h_{k-n} = h_{k-n} + coeff (mod q)。
3. 完成： 当循环结束时，h(x) 的系数向量 (h₀, ..., h_{n-1}) 就是我们最终的结果。

这个过程精确地模拟了信息在 LFSR 中的反馈和移位行为。

结论与比较

通过上述分析，我们看到，尽管基本原理相同，三种不同商环上的多项式乘法展现了截然不同的计算结构。