在前几章中，我们研究了数论变换（NTT），它计算多项式在 $k$ 次单位根上的取值。可以将其理解为将多项式从系数形式转换为点值形式。

NTT 可以通过将次数为 $(k-1)$ 的多项式的系数向量乘以一个 Vandermonde 矩阵来实现，时间复杂度为 $\mathcal{O}(k^2)$。此外，还有一种更有趣的快速递归版本，可将时间复杂度降低到 $\mathcal{O}(k \log k)$。

在本章中，我们开始研究 NTT 的逆变换，称为逆数论变换，或 INTT。它可以用于将多项式从点值形式转换回系数形式。这个过程称为插值。

在我们关于 Lagrange 插值 的文章中，我们已经看到了一种执行插值的方法。使用 Lagrange 插值与使用逆数论变换的区别有两方面：Lagrange 插值可以从任意点集执行，而 INTT 只能在 $k$ 次单位根集上执行。相反，Lagrange 插值的时间复杂度始终为 $\mathcal{O}(k^2)$，而 INTT 可以在 $\mathcal{O}(k \log k)$ 的时间复杂度内完成。

在本章中，我们将：

• 回顾如何使用 Vandermonde 矩阵进行求值；
• 提出一种也使用 Vandermonde 矩阵的逆变换；
• 证明该逆变换能撤销原始变换。换句话说，我们证明通过 NTT 求值，再通过 INTT 插值，多项式将恢复为原始的系数形式。

现在，我们将处理一个 3 次多项式的 INTT，以便读者更容易理解计算过程。

在后续章节中，我们将证明所提出的逆变换适用于任意次数的多项式。

回顾：从系数形式到点值形式

考虑多项式

$$f(x)=a_0+a_1x+a_2x^2+a_3x^3$$

要将该多项式从系数形式转换为点值形式，至少需要在 4 个点上求值。

例如，如果集合 $S={1,\omega,\omega^2,\omega^3}$ 表示求值点，其中 $\omega$ 是一个本原 4 次单位根，则这些点上的求值为：

$$ \begin{aligned} f(1) &= a_0 + a_1 + a_2 + a_3 \ f(\omega) &= a_0 + a_1\omega + a_2\omega^2 + a_3\omega^3 \ f(\omega^2) &= a_0 + a_1\omega^2 + a_2\omega^4 + a_3\omega^6 \ f(\omega^3) &= a_0 + a_1\omega^3 + a_2\omega^6 + a_3\omega^9 \end{aligned} $$

这可以用以下矩阵乘法表示：

$$ \begin{aligned} \begin{bmatrix}f(1) \ f(\omega) \ f(\omega^2) \ f(\omega^3)\end{bmatrix} &= \begin{bmatrix} 1 & 1 & 1 & 1 \ 1 & \omega & \omega^2 & \omega^3 \ 1 & \omega^2 & \omega^4 & \omega^6 \ 1 & \omega^3 & \omega^6 & \omega^9 \end{bmatrix} \begin{bmatrix}a_0 \ a_1 \ a_2 \ a_3\end{bmatrix} \ \mathbf{y} &= V(\omega) \cdot \mathbf{a} \end{aligned} $$

其中 $V(\omega)$ 称为 Vandermonde 矩阵，$\mathbf{a}$ 是表示系数的列向量。你可以参考关于 Vandermonde 矩阵 的文章详细了解它们。Vandermonde 矩阵 的一个性质是，它的每一行都构成一个几何级数，即一个序列，其中每一项都通过将前一项乘以一个常数比得到。

在上述矩阵 $V(\omega)$ 中，我们可以注意到：

• 第 1 行：$[1 \ 1\ 1\ 1]$ $\rightarrow$ 首项：$1$，公比：$1$
• 第 2 行：$[1 \ \omega\ \omega^2\ \omega^3]$ $\rightarrow$ 首项：$1$，公比：$\omega$
• 第 3 行：$[1 \ \omega^2\ \omega^4\ \omega^6]$ $\rightarrow$ 首项：$1$，公比：$\omega^2$
• 第 4 行：$[1 \ \omega^3\ \omega^6\ \omega^9]$ $\rightarrow$ 首项：$1$，公比：$\omega^3$

让我们回顾一下乘法 $\mathbf{y}=V(\omega) \cdot \mathbf{a}$ 如何给出 $f(x)$ 的求值结果：

$$ \mathbf{y}= \begin{bmatrix}f(1)\[4pt]f(\omega)\[4pt]f(\omega^2)\[4pt]f(\omega^3)\end{bmatrix}

\begin{bmatrix} 1 & 1 & 1 & 1\[4pt] 1 & \omega & \omega^2 & \omega^3\[4pt] 1 & \omega^2 & \omega^4 & \omega^6\[4pt] 1 & \omega^3 & \omega^6 & \omega^9 \end{bmatrix} \begin{bmatrix} a_0\ a_1\ a_2\ a_3 \end{bmatrix} $$

如果我们逐行执行 $V(\omega)$ 的矩阵乘法，我们得到：

$$ \begin{aligned} f(1) &= [1\ 1\ 1\ 1] \cdot \begin{bmatrix}a_0\ a_1\ a_2\ a_3\end{bmatrix} = 1\cdot a_0 + 1 \cdot a_1 + 1\cdot a_2 + 1\cdot a_3 = a_0 + a_1 + a_2 + a_3 \[6pt] f(\omega) &= [1\ \omega\ \omega^2\ \omega^3] \cdot \begin{bmatrix}a_0\ a_1\ a_2\ a_3\end{bmatrix} = 1 \cdot a_0 + \omega \cdot a_1 + \omega^2 \cdot a_2 + \omega^3 \cdot a_3 = a_0 + a_1\omega + a_2\omega^2 + a_3\omega^3 \[6pt] f(\omega^2) &= [1\ \omega^2\ \omega^4\ \omega^6] \cdot \begin{bmatrix}a_0\ a_1\ a_2\ a_3\end{bmatrix} = 1 \cdot a_0 + \omega^2 \cdot a_1 + \omega^4 \cdot a_2 + \omega^6 \cdot a_3 = a_0 + a_1\omega^2 + a_2\omega^4 + a_3\omega^6 \[6pt] f(\omega^3) &= [1\ \omega^3\ \omega^6\ \omega^9] \cdot \begin{bmatrix}a_0\ a_1\ a_2\ a_3\end{bmatrix} = 1 \cdot a_0 + \omega^3 \cdot a_1 + \omega^6 \cdot a_2 + \omega^9 \cdot a_3 = a_0 + a_1\omega^3 + a_2\omega^6 + a_3\omega^9 \end{aligned} $$

因此，我们得到：

$$ \mathbf{y}= \begin{bmatrix}f(1) \ f(\omega) \ f(\omega^2) \ f(\omega^3)\end{bmatrix}

\begin{bmatrix} a_0 + a_1 + a_2 + a_3\ a_0 + a_1\omega + a_2\omega^2 + a_3\omega^3\ a_0 + a_1\omega^2 + a_2\omega^4 + a_3\omega^6\ a_0 + a_1\omega^3 + a_2\omega^6 + a_3\omega^9 \end{bmatrix} $$

因此，如果我们给定一个多项式的系数形式（用向量 $\mathbf{a}$ 表示），我们可以通过将 $\mathbf{a}$ 左乘 Vandermonde 矩阵 $V(\omega)$ 来获得它的点值形式（用向量 $\mathbf{y}$ 表示）。

但如果我们反过来已知求值结果，即向量 $\mathbf{y}$，并要求计算系数，即向量 $\mathbf{a}$，该怎么办？

这可以通过使用 Vandermonde 矩阵 $V(\omega)$ 的逆矩阵 $V^{-1}(\omega)$ 来实现，通过以下操作：

$$\mathbf{a} = V(\omega)^{-1}\cdot \mathbf{y}$$

我们声称矩阵 $V(\omega)^{-1}$ 由下式给出

$$ V(\omega)^{-1} = \frac{1}{4} \begin{bmatrix} 1 & 1 & 1 & 1 \ 1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \ 1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \ 1 & \omega^{-3} & \omega^{-6} & \omega^{-9} \end{bmatrix} $$

观察到 $V(\omega)^{-1}$ 也具有每一行构成几何级数的性质：

• 第 1 行：$[1 \ \ 1\ \ 1\ \ 1]$ $\rightarrow$ 首项：$1$，公比：$1$
• 第 2 行：$[1 \ \omega^{-1}\ \omega^{-2}\ \omega^{-3}]$ $\rightarrow$ 首项：$1$，公比：$\omega^{-1}$
• 第 3 行：$[1 \ \omega^{-2}\ \omega^{-4}\ \omega^{-6}]$ $\rightarrow$ 首项：$1$，公比：$\omega^{-2}$
• 第 4 行：$[1 \ \omega^{-3}\ \omega^{-6}\ \omega^{-9}]$ $\rightarrow$ 首项：$1$，公比：$\omega^{-3}$

因此，在这种情况下，Vandermonde 矩阵的逆本身就是另一个 Vandermonde 矩阵。

在接下来的部分中，我们将使用 4 次单位根的示例证明我们的主张是正确的。在下一章中，我们将一般性地证明这一点。

我们将证明，对于 $k$ 次单位根的情况，当 NTT 使用以下 Vandermonde 矩阵实现时，

$$ V(\omega)= \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \ 1 & \omega & \omega^{2} & \cdots & \omega^{k-1} \ 1 & \omega^{2} & \omega^{4} & \cdots & \omega^{2(k-1)} \ \vdots & \vdots & \vdots & \ddots & \vdots \ 1 & \omega^{k-1} & \omega^{2(k-1)} & \cdots & \omega^{(k-1)(k-1)} \end{bmatrix}, $$

逆矩阵 $V(\omega)^{-1}$ 可以通过将每个 $\omega$ 的幂替换为 $\frac{1}{\omega}$ 并除以因子 $k$ 得到，如下所示

$$ V(\omega)^{-1}= \frac{1}{k} \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \ 1 & \omega^{-1} & \omega^{-2} & \cdots & \omega^{-(k-1)} \ 1 & \omega^{-2} & \omega^{-4} & \cdots & \omega^{-2(k-1)} \ \vdots & \vdots & \vdots & \ddots & \vdots \ 1 & \omega^{-(k-1)} & \omega^{-2(k-1)} & \cdots & \omega^{-(k-1)(k-1)} \end{bmatrix}. $$

逆 Vandermonde 矩阵乘以给定多项式在单位根上的求值向量后，将返回该多项式的系数向量。

计算 $V(\omega)^{-1} \cdot \mathbf{y}$

为了证明 $V(\omega)^{-1}$ 与 $\mathbf{y}$ 的矩阵乘法能给我们返回系数向量 $\mathbf{a}$，让我们使用之前的例子，其中 $f(x)=a_0+a_1x+a_2x^2+a_3x^3$，$S={1,\omega,\omega^2,\omega^3}$ 且 $k=4$。

回想一下 $\mathbf{y}$，即 $f(x)$ 在 $S$ 中点上的求值向量，由下式给出：

$$ \mathbf{y}= \begin{bmatrix}f(1) \ f(\omega) \ f(\omega^2) \ f(\omega^3)\end{bmatrix}

\begin{bmatrix} a_0 + a_1 + a_2 + a_3\ a_0 + a_1\omega + a_2\omega^2 + a_3\omega^3\ a_0 + a_1\omega^2 + a_2\omega^4 + a_3\omega^6\ a_0 + a_1\omega^3 + a_2\omega^6 + a_3\omega^9 \end{bmatrix} $$

让我们执行 $V(\omega)^{-1}$ 与 $\mathbf{y}$ 的矩阵乘法：

$$ \begin{aligned} \tilde{\mathbf{a}} &= V(\omega)^{-1}\cdot \mathbf{y} \ \begin{bmatrix}\tilde{a_0} \ \tilde{a_1} \ \tilde{a_2} \ \tilde{a_3}\end{bmatrix} &= \frac{1}{4} \begin{bmatrix} 1 & 1 & 1 & 1 \ 1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \ 1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \ 1 & \omega^{-3} & \omega^{-6} & \omega^{-9} \end{bmatrix} \begin{bmatrix} f(1) \ f(\omega) \ f(\omega^2) \ f(\omega^3) \end{bmatrix} \end{aligned} $$

我们的目标是证明从上述矩阵乘法得到的向量 $\tilde{\mathbf{a}}$ 等于 $f(x)$ 的系数向量 $\mathbf{a}$。

将向量 $\mathbf{y}$ 中的求值结果 $f(1),f(\omega),f(\omega^2)$ 和 $f(\omega^3)$ 代入，我们可以计算系数 $\tilde{\mathbf{a}}$ 为：

$$ \begin{aligned} \tilde{\mathbf{a}} &= V(\omega)^{-1}\cdot \mathbf{y} \ \begin{bmatrix}\tilde{a_0} \ \tilde{a_1} \ \tilde{a_2} \ \tilde{a_3}\end{bmatrix} &= \frac{1}{4} \begin{bmatrix} 1 & 1 & 1 & 1 \ 1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \ 1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \ 1 & \omega^{-3} & \omega^{-6} & \omega^{-9} \end{bmatrix} \begin{bmatrix} a_0 + a_1 + a_2 + a_3\ a_0 + a_1\omega + a_2\omega^2 + a_3\omega^3\ a_0 + a_1\omega^2 + a_2\omega^4 + a_3\omega^6\ a_0 + a_1\omega^3 + a_2\omega^6 + a_3\omega^9 \end{bmatrix} \end{aligned} $$

我们现在证明向量 $\tilde{\mathbf{a}}$ 和 ${\mathbf{a}}$ 相等。换句话说，我们想要证明

$$ \begin{aligned} \tilde{a_0} &= a_0, \ \tilde{a_1} &= a_1, \ \tilde{a_2} &= a_2, \ \tilde{a_3} &= a_3. \end{aligned} $$

计算系数 $\tilde{a_0},\tilde{a_1},\tilde{a_2}$ 和 $\tilde{a_3}$

让我们逐行执行右侧的矩阵乘法，看看左侧对应的系数是如何得到的。对于系数 $\tilde{a_0}$，我们取 $V(\omega)^{-1}$ 的第一行与向量 $\mathbf{y}$ 的点积：

$$ \begin{aligned} \begin{bmatrix}\color{red}\tilde{a_0} \ \tilde{a_1} \ \tilde{a_2} \ \tilde{a_3}\end{bmatrix} &= \frac{1}{4} \begin{bmatrix} \color{red}1 & \color{red}1 & \color{red}1 & \color{red}1 \ 1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \ 1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \ 1 & \omega^{-3} & \omega^{-6} & \omega^{-9} \end{bmatrix} \begin{bmatrix} \color{red}f(1) \ \color{red}f(\omega) \ \color{red}f(\omega^2) \ \color{red}f(\omega^3) \end{bmatrix} \end{aligned} $$

$$ \begin{aligned} &\quad \text{取 } V(\omega)^{-1} \text{ 的第一行与 } \mathbf{y} \text{ 的点积}\ \tilde{a_0}&= \frac{1}{4}\big(1\cdot f(1)+1\cdot f(\omega)+1\cdot f(\omega^2)+1\cdot f(\omega^3)\big) \[6pt] &=\frac{1}{4}\Big(1\cdot \underbrace{(a_0+a_1+a_2+a_3)}{f(1)} \ &\qquad; + 1\cdot \underbrace{(a_0+a_1\omega+a_2\omega^2+a_3\omega^3)}{f(\omega)}\ &\qquad; + 1\cdot \underbrace{(a_0+a_1\omega^2+a_2\omega^4+a_3\omega^6)}{f(\omega^2)}\ &\qquad; + 1\cdot \underbrace{(a_0+a_1\omega^3+a_2\omega^6+a_3\omega^9)}{f(\omega^3)}\Big)\[6pt] &=\frac{1}{4}\Big(4a_0 ;+; a_1(1+\omega+\omega^2+\omega^3) \ &\qquad; +; a_2(1+\omega^2+\omega^4+\omega^6) \ &\qquad; +; a_3(1+\omega^3+\omega^6+\omega^9)\Big) \end{aligned} $$

从前一章中回忆，由于 $\omega$ 是一个本原 4 次单位根，求和

$$\sum_{k=0}^3 \omega^{mk}$$

当 $m$ 不是 $4$ 的倍数时等于零。具体地，

$$\sum_{k=0}^3 \omega^{mk} = \omega^{m\cdot 0} + \omega^{m\cdot 1} + \omega^{m\cdot 2} + \omega^{m\cdot 3} = 1 + \omega^m + \omega^{2m} + \omega^{3m}=0$$

要详细了解这个概念，请参考关于单位根的正交性的文章。

通过代入不是 $4$ 的倍数的 $m$ 值，我们得到以下恒等式：

$$ \begin{aligned} \text{对于 } m&=1 &\rightarrow& 1+\omega+\omega^2+\omega^3=0, \quad \ \text{对于 }m&=2&\rightarrow&1+\omega^2+\omega^4+\omega^6=0 , \quad \ \text{对于 }m&=3&\rightarrow&1+\omega^3+\omega^6+\omega^9=0, \quad \ \text{对于 }m&=-1&\rightarrow&1+\omega^{-1}+\omega^{-2}+\omega^{-3}=0, \quad \ \text{对于 }m&=-2&\rightarrow&1+\omega^{-2}+\omega^{-4}+\omega^{-6}=0, \quad \ \text{对于 }m&=-3&\rightarrow&1+\omega^{-3}+\omega^{-6}+\omega^{-9}=0, \quad \end{aligned} $$

因此，所有乘以 $a_1$、$a_2$ 和 $a_3$ 的项都消失了，剩下

$$ \begin{aligned} \tilde{a_0}&=\frac{1}{4}\Big(4a_0 ;+; a_1\underbrace{(1+\omega+\omega^2+\omega^3)}{=,0} \ &\qquad; +; a_2\underbrace{(1+\omega^2+\omega^4+\omega^6)}{=,0} \ &\qquad; +; a_3\underbrace{(1+\omega^3+\omega^6+\omega^9)}_{=,0}\Big) \ \tilde{a_0}&=\frac{1}{4}\cdot 4a_0 \ &= a_0 \end{aligned} $$

类似地，为了计算 $\tilde{a_1}$，我们取 $V(\omega)^{-1}$ 的第二行与 $\mathbf{y}$ 的点积：

$$ \begin{aligned} \begin{bmatrix}\tilde{a_0} \ \color{red}\tilde{a_1} \ \tilde{a_2} \ \tilde{a_3}\end{bmatrix} &= \frac{1}{4} \begin{bmatrix} 1 & 1 & 1 & 1 \ \color{red}1 & \color{red}\omega^{-1} & \color{red}\omega^{-2} & \color{red}\omega^{-3} \ 1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \ 1 & \omega^{-3} & \omega^{-6} & \omega^{-9} \end{bmatrix} \begin{bmatrix} \color{red}f(1) \ \color{red}f(\omega) \ \color{red}f(\omega^2) \ \color{red}f(\omega^3) \end{bmatrix} \end{aligned} $$

$$ \begin{aligned} &\qquad \text{取 } V(\omega)^{-1} \text{ 的第二行与 } \mathbf{y} \text{ 的点积} \ \tilde{a_1} &= \frac{1}{4}\big(1\cdot f(1) + \omega^{-1}f(\omega) + \omega^{-2}f(\omega^2) + \omega^{-3}f(\omega^3)\big) \[6pt] \end{aligned} $$

代入求值结果 $f(1), f(\omega), f(\omega^2)$ 和 $f(\omega^3)$ 的表达式，我们得到，

$$ \begin{aligned} \tilde{a_1} &= \frac{1}{4}\Big( 1(a_0+a_1+a_2+a_3) \ &\qquad + \omega^{-1}(a_0 + a_1\omega + a_2\omega^2 + a_3\omega^3) \ &\qquad + \omega^{-2}(a_0 + a_1\omega^2 + a_2\omega^4 + a_3\omega^6) \ &\qquad + \omega^{-3}(a_0 + a_1\omega^3 + a_2\omega^6 + a_3\omega^9) \Big) \[6pt] \end{aligned} $$

将项分组以得到 $a_0,a_1,a_2$ 和 $a_3$ 的因子，得到

$$ \begin{aligned} \tilde{a_1} &= \frac{1}{4}\Big( a_0(1+\omega^{-1}+\omega^{-2}+\omega^{-3}) \ &\qquad + a_1(1+\omega^{-1}\omega+\omega^{-2}\omega^2+\omega^{-3}\omega^3) \ &\qquad + a_2(1+\omega^{-1}\omega^2+\omega^{-2}\omega^4+\omega^{-3}\omega^6) \ &\qquad + a_3(1+\omega^{-1}\omega^3+\omega^{-2}\omega^6+\omega^{-3}\omega^9) \Big) \[6pt] &= \frac{1}{4}\Big( a_0(1+\omega^{-1}+\omega^{-2}+\omega^{-3}) + 4a_1 \ &\qquad + a_2(1+\omega^{1}+\omega^{2}+\omega^{3}) \ &\qquad + a_3(1+\omega^{2}+\omega^{4}+\omega^{6}) \Big) \end{aligned} $$

同样，与因子 $a_0,a_2,a_3$ 相关的括号内的项消失了，剩下

$$ \begin{aligned} \tilde{a_1}&=\frac{1}{4}\cdot 4a_1 = a_1 \end{aligned} $$

尝试自行展开 $\tilde{a_2}$ 和 $\tilde{a_3}$ 的乘法，观察它们如何根据我们使用的相同逻辑简化。你会发现 $\tilde{a_2}=a_2$ 和 $\tilde{a_3}=a_3$，正如预期的那样。

这完成了 $V(\omega)^{-1} \cdot \mathbf{y} = \mathbf{a}$ 的证明。这样，我们已经证明了对于 $k=4$ 的情况，Vandermonde 矩阵的逆也是一个 Vandermonde 矩阵。对于一般 $k$ 值的情况将在下一章中证明。

本文是我们 ZK 书 中关于数论变换系列的一部分。

• 原文链接： rareskills.io/post/inver...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～