使用卷积定理证明系数表示法与点值表示法中乘法的等价性

Last updated on Jun 16, 2026

在本系列文章的开头，我们讨论过，如果两个次数不超过 $n$ 的多项式乘法都采用点值形式，那么可以在 $\mathcal{O}(n)$ 的时间复杂度内完成。

在实际应用中，困难在于多项式通常以系数形式给出，而且我们希望乘法的结果也采用系数形式。

幸运的是，这些问题可以通过使用快速版本的 NTT 和 INTT 来解决。

要在 $\mathcal{O}(n \log n)$ 时间内对以系数形式表示的两个多项式进行相乘，过程如下：

使用 NTT，将多项式从系数形式转换为点值形式。
将点值形式的多项式进行逐点乘法。这可以在 $\mathcal{O}(n)$ 的时间复杂度内完成，结果同样为点值形式。
使用 INTT 将得到的结果多项式转换回系数形式。

使用 $n$ 次单位根（其中 $n$ 是 2 的幂），步骤 1 和 3 可以在 $\mathcal{O}(n \log n)$ 的时间内完成。

唯一的限制是，我们必须限制结果多项式的最高次数为 $n-1$ 。因此，我们要相乘的两个多项式的次数之和不能超过 $n-1$ 。

在实践中，这通常不是问题，因为我们通常可以使用包含足够大的 $n$ 次单位根的域，使得多项式的次数保持在允许的范围内。

次数小于 $n-1$ 的多项式也不会成为问题，因为可以用值为零的系数将它们填充至 $n-1$ 次。

如果不使用快速 NTT 和 INTT，多项式乘法的时间复杂度将为 $\mathcal{O}(n^2)$ 。

本章的目的就是证明我们的主张。我们将证明：在系数形式下将两个多项式相乘，等价于对每个多项式应用 NTT，进行逐点乘法，然后对通过该操作得到的结果多项式应用 INTT。

这个结果在多项式乘法的语境中被称为卷积定理。在更一般的语境下，卷积定理指出：

“原域中的卷积等价于变换域中的逐点乘法。”

为了正确理解这个定理，我们需要从定义什么是卷积开始。

不太倾向于数学的读者可以跳过本章，这不会影响阅读的连贯性。在接下来的正文中，我们将证明卷积定理，但如果读者只对其应用感兴趣，只需接受它可以用于在 $\mathcal{O}(n \log n)$ 而不是 $\mathcal{O}(n^2)$ 的时间复杂度内进行多项式乘法即可。

卷积

在系数形式下将两个多项式相乘是卷积操作的一个例子。

考虑两个次数为 2 的多项式，

f(x) = a_0 + a_1x + a_2 x^2

和

g(x) = b_0 + b_1 x + b_2 x^2.

在系数形式下进行乘法，得到多项式

\begin{aligned} h(x) = f(x)g(x) &= a_0b_0 + a_0b_1 x+a_0b_2x^2 + \\ &+ a_1b_0x + a_1b_1x^2 + a_1b_2x^3 \\ &+ a_2 b_0 x^2 + a_2 b_1 x^3 + a_2b_2x^4. \end{aligned}

重新排列这个表达式，我们得到

\begin{aligned} h(x) = f(x)g(x) &= a_0b_0 \\ &+ (a_0 b_1 + a_1b_0)x \\ &+ (a_0 b_2 + a_1 b_1 + a_2 b_0) x^2 \\ &+ (a_1 b_2 + a_2 b_1) x^3 \\ &+ a_2 b_2 x^4. \end{aligned}

因此， $f(x)$ 和 $g(x)$ 相乘所得多项式的系数为

\begin{aligned} c_0 &= a_0b_0, \\ c_1 &= a_0 b_1 + a_1b_0, \\ c_2 &= a_0 b_2 + a_1 b_1 + a_2 b_0, \\ c_3 &= a_1 b_2 + a_2 b_1, \\ c_4 &= a_2 b_2. \end{aligned}

这些系数可以用以下公式简洁地表达

c_k = \sum_{i=0}^{k} a_i b_{k-i}

其中 $k=0,1,2,3,4$ ，即多项式 $h(x)$ 的次数。让我们检查其中一个系数 $c_3$ 。对于这个系数，我们有

c_3 = \sum_{i=0}^{3} a_i b_{3-i} = a_0 b_3 + a_1 b_ 2 + a_2 b_1 + a_3 b_0.

因为 $a_3$ 和 $b_3$ 均为零（因为多项式 $f(x)$ 和 $g(x)$ 的次数为 2），该式化简为

c_3 = a_1 b_2 + a_2 b_1,

正如预期。

由下式定义的操作

c_k = \sum_{i=0}^{k} a_i b_{k-i}

称为卷积，通常写为

c_k = (a \ast b)_k,

其中 $\ast$ 表示卷积运算符。

卷积定理

我们的目标是证明：将 $f(x)$ 和 $g(x)$ 转换为点值形式，将对应的点相乘，再将结果转换回系数形式，这一过程等价于对 $f(x)$ 和 $g(x)$ 的系数进行卷积。

考虑多项式

f(x)=a_0 + a_1x+a_2x^2 + ... +a_px^p

和

g(x)=b_0 + b_1x+b_2x^2 + ... +b_qx^q

它们的次数分别为 $p$ 和 $q$ 。

将 $f(x)$ 和 $g(x)$ 相乘会产生一个新的多项式 $h(x)$ ，其次数分别是 $f(x)$ 和 $g(x)$ 的次数 $p$ 和 $q$ 的和。

假设 $h(x)$ 的次数为 $n-1$ 。

因此，我们想要计算

h(x) = f(x)g(x) = c_0 + c_1 x + c_2 x^2 + \ldots + c_{n-1} x^{n-1}

如果次数小于 $n-1$ ，我们可以用零来填充高次项的系数。

我们将多项式 $f(x)$ 和 $g(x)$ 的系数表示为

\begin{aligned} [a_0, a_1, a_2, ..., a_{n-1}], \\ [b_0, b_1, b_2, ..., b_{n-1}]. \end{aligned}

上面的一些高次系数将为零，因为 $f(x)$ 和 $g(x)$ 的次数之和最多只能为 $n-1$ 。这不是问题。我们唯一的限制是

deg⁡(f)+deg⁡(g)=deg⁡(h)≤n−1.

我们的第一步是将多项式 $f(x)$ 和 $g(x)$ 从系数形式转换为点值形式。

第一步：将多项式转换为点值形式。

为了将这些多项式转换为点值形式，我们使用 NTT。通过选择 $n$ 为 2 的幂，我们可以应用快速变换。然而，由于最终结果等价于乘以范德蒙德矩阵，我们将展示矩阵形式的表述。

例如，对于多项式 $f(x)$ ，其在 $n$ 次单位根处的计算值由下式给出

\begin{bmatrix} f(1) \\ f(\omega) \\ f(\omega^2) \\ \vdots \\ f(\omega^{n-1}) \end{bmatrix} = \begin{bmatrix}1 & 1 & 1 & \cdots & 1 \\1 & \omega & \omega^{2} & \cdots & \omega^{n-1} \\1 & \omega^{2} & \omega^{4} & \cdots & \omega^{2(n-1)} \\\vdots & \vdots & \vdots & \ddots & \vdots \\1 & \omega^{n-1} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)(n-1)}\end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2\\ \vdots \\ a_{n-1} \end{bmatrix}.

同样，对于 $g(x)$ ，

\begin{bmatrix} g(1) \\ g(\omega) \\ g(\omega^2) \\ \vdots \\ g(\omega^{n-1}) \end{bmatrix} = \begin{bmatrix}1 & 1 & 1 & \cdots & 1 \\1 & \omega & \omega^{2} & \cdots & \omega^{n-1} \\1 & \omega^{2} & \omega^{4} & \cdots & \omega^{2(n-1)} \\\vdots & \vdots & \vdots & \ddots & \vdots \\1 & \omega^{n-1} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)(n-1)}\end{bmatrix} \begin{bmatrix} b_0 \\ b_1 \\ b_2\\ \vdots \\ b_{n-1} \end{bmatrix}.

这些矩阵运算可以在分量形式上写成

f(\omega^i) = \sum_{r=0}^{n-1} a_r \omega^{ri}

和

g(\omega^i) = \sum_{s=0}^{n-1} b_s \omega^{si}.

例如， $f(\omega^2)$ 的求值由下式给出

f(\omega^2) = \sum_{r=0}^{n-1} a_r \omega^{r2} = a_0 \omega^{0 \cdot 2} + a_1 \omega^{1 \cdot 2} + a_2 \omega^{2 \cdot 2} + \ldots + a_{n-1} \omega^{{(n-1)} \cdot 2}

第二步：对点值形式的多项式进行逐点乘法。

我们现在将 $f(x)$ 和 $g(x)$ 的计算值进行逐点乘法，以得到乘积多项式 $h(x)$ 的计算值：

\begin{aligned} h(\omega^0)&= f(\omega^0)g(\omega^0) \\ h(\omega^1)&= f(\omega^1)g(\omega^1) \\ &\vdots \\ h(\omega^{n-1})&= f(\omega^{n-1})g(\omega^{n-1}) \end{aligned}

在索引记法中，这可以写成

h(\omega^i) = f(\omega^i) g(\omega^i).

使用上一步得到的 $f(\omega^i)$ 和 $g(\omega^i)$ 的表达式，我们得到

h(\omega^i) = \left(\sum_{r=0}^{n-1} a_r \omega^{ri} \right) \left( \sum_{s=0}^{n-1} b_s \omega^{si}\right).

简而言之，我们想要证明的是，如果我们对点值形式（即上述形式）的多项式 $h(x)$ 执行 INTT，结果与对 $f(x)$ 和 $g(x)$ 执行卷积相同。

最后一步：对点值形式的多项式 $h(x)$ 应用 INTT

在 $n$ 次单位根上执行的逆数论变换（Inverse Number Theoretic Transform）是使用按比例 $\frac{1}{n}$ 缩放的范德蒙德矩阵 $V(\omega^{-1})$ 来计算的。

因此，通过对点集 $h(\omega^i)$ 应用 INTT，我们得到系数形式的多项式 $h(x)$ ：

\begin{bmatrix} c_0 \\ c_1 \\ c_2\\ \vdots \\ c_{n-1} \end{bmatrix} = \frac{1}{n}\begin{bmatrix}1 & 1 & 1 & \cdots & 1 \\1 & \omega^{-1} & \omega^{-2} & \cdots & \omega^{-(n-1)} \\1 & \omega^{-2} & \omega^{-4} & \cdots & \omega^{-2(n-1)} \\\vdots & \vdots & \vdots & \ddots & \vdots \\1 & \omega^{-(n-1)} & \omega^{-2(n-1)} & \cdots & \omega^{-(n-1)(n-1)}\end{bmatrix} \begin{bmatrix} h(\omega^0) \\ h(\omega^1) \\ h(\omega^2) \\ \vdots \\ h(\omega^{n-1}) \end{bmatrix}

这可以写成分量形式：

c_p = \frac{1}{n} \sum_{i=0}^{n-1} h(\omega^i) \omega^{-ip}.

利用 $h(\omega^i)$ 由下式给出这一事实：

h(\omega^i) = \left(\sum_{r=0}^{n-1} a_r \omega^{ri} \right) \left( \sum_{s=0}^{n-1} b_s \omega^{si} \right),

我们得到

c_p = \frac{1}{n} \sum_{i=0}^{n-1} \underbrace{\left(\sum_{r=0}^{n-1} a_r \omega^{ri} \right) \left( \sum_{s=0}^{n-1} b_s \omega^{si} \right)}_{h(\omega^i)} \omega^{-ip}.

这个表达式很长，但可以通过应用单位根的正交性来进行化简。

首先，让我们将所有 $\omega$ 的幂项分组：

\begin{aligned} c_p &= \frac{1}{n} \sum_{i=0}^{n-1} \left(\sum_{r=0}^{n-1} a_r \omega^{ri} \right) \left( \sum_{s=0}^{n-1} b_s \omega^{si} \right) \omega^{-ip} && \text{\small 上方得到的表达式} \\ &= \frac{1}{n} \sum_{i=0}^{n-1} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s)\,\omega^{ri}\,\omega^{si}\,\omega^{-ip} && \text{\small 对求和与项进行分组} \\ &= \frac{1}{n} \sum_{i=0}^{n-1} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s)\,\omega^{i(r+s-p)} && \text{\small 合并 }\omega^i\text{\small 的指数} \\ &= \frac{1}{n} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s) \left( \sum_{i=0}^{n-1} \omega^{i(r+s-p)} \right) && \text{\small 提取单位根之和} \end{aligned}

上述表达式表明，我们可以使用单位根的正交性来对其进行化简。

回顾一下单位根的正交性公式：

\sum_{i=0}^{n-1} (\omega^{i})^{r-s}=\begin{cases}n, & \text{如果 } r\equiv s \pmod{n},\\[6pt]0, & \text{否则}.\end{cases}

在 $c_p$ 提取出的单位根之和中使用上述公式，我们注意到

\sum_{i=0}^{n-1} \omega^{i(r+s-p)}

如果 $s = p-r \pmod{n}$ （等价于 $r=p-s \pmod{n}$ ），则其等于 $n$ ；否则等于 0。

这可以表示为 $n$ 乘以克罗内克 δ 函数（Kronecker delta）：

\sum_{i=0}^{n-1} \omega^{i(r+s-p)} = n \delta_{s,p-r}

将 $c_p$ 表达式中的

\sum_{i=0}^{n-1} \omega^{i(r+s-p)}

替换掉，我们得到

c_p = \frac{1}{n} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s)(n \delta_{s, p-r})

常数 $\frac{1}{n}$ 和 $n$ 相互抵消：

c_p = \frac{1}{\cancel{n}} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s)(\cancel{n} \delta_{s, p-r})

更重要的是，当对索引 $s$ 求和时，除了 $s=p-r$ 的情况外，所有项都消失了。这是由于单位根的正交性。

结果，关于 $s$ 的求和被折叠（消除），我们可以将 $b_s$ 中的求和替换为单一元素 $b_{p-r}$ 。我们得到

c_p = \sum_{r=0}^{n-1} a_r b_{p-r}

这正是卷积公式！

让我们回顾一下刚才所做的步骤：

我们对多项式 $f(x)$ 和 $g(x)$ 应用了 NTT，将其系数表示转换为点值表示，也就是包含了它们在 $n$ 次单位根处计算值的向量：

\big(f(1), f(\omega), \ldots, f(\omega^{n-1})\big)\quad \text{and} \quad\big(g(1), g(\omega), \ldots, g(\omega^{n-1})\big)

我们将这些计算值进行了逐点乘法，也就是说对于每个单位根 $\omega^i$ ，我们计算了

h(\omega^i)=f(\omega^i)g(\omega^i)

从而获得了乘积多项式 $h(x)$ 的点值表示。

我们对这个数值向量

\big(h(1), h(\omega), \ldots, h(\omega^{n-1})\big)

应用了 INTT，以恢复 $h(x)$ 的系数表示。

我们证明了这三个步骤与多项式 $f(x)$ 和 $g(x)$ 相乘（即将 $f(x)$ 和 $g(x)$ 的系数进行卷积）产生的结果完全相同。

然而，直接卷积的时间复杂度为 $\mathcal{O}(n^2)$ ，而上述过程可以在 $\mathcal{O}(n \log n)$ 时间内执行，并得到相同的最终多项式。

这正是卷积定理所述的内容。用更正式的方式，我们可以这样写：

设 $f$ 和 $g$ 为两个系数形式的多项式。令 $*$ 表示卷积操作， $\cdot$ 表示乘法。

设 $\mathcal{F}(f)$ 表示对 $f$ 应用 NTT（即如果 $f$ 是系数向量，则 $\mathcal{F}(f)$ 为计算值向量），并设 $\mathcal{F}^{-1}(\mathcal{F}(f))$ 表示对 $\mathcal{F}(f)$ 应用 INTT。那么，

f *g =\mathcal{F}^{-1}(\mathcal{F}(f)\cdot\mathcal{F}(g)).

表达卷积定理的另一种方式是

\mathcal{F}(f *g) =\mathcal{F}(f)\cdot\mathcal{F}(g).

这是一个线性变换，可以这样理解：系数域中的卷积等价于点值域中的逐点乘法。

本文是我们 ZK Book 中关于数论变换（Number Theoretic Transform）系列文章的一部分