在之前的章节中，我们学习了数论变换（NTT），它在多项式的 $k$ 次单位根处对其进行求值。这可以理解为将多项式从其系数表示法（coefficient form）转换为点值表示法（point-value form）。

通过将 $k-1$ 次多项式的系数向量乘以一个 Vandermonde 矩阵可以执行 NTT，其时间复杂度为 $\mathcal{O}(k^2)$。更具吸引力的是，还可以使用该变换的快速递归版本，将时间复杂度降低至 $\mathcal{O}(k \log k)$。

在本章中，我们将开始学习 NTT 的逆变换，称为逆数论变换（Inverse Number Theoretic Transform，或 INTT）。它可以用于将多项式从点值表示法转换回系数表示法。这个过程被称为插值（interpolation）。

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

在本章中，我们将：

• 回顾如何使用 Vandermonde 矩阵进行多项式求值；
• 提出一种同样使用 Vandermonde 矩阵进行计算的逆变换；
• 证明该逆变换可以撤销原始变换。换言之，我们将展示通过 NTT 进行求值，随后通过 INTT 进行插值，可以将多项式还原为其原始的系数表示法。

目前，我们将以次数为 $3$ 的多项式的 INTT 为例，以便读者更容易跟上计算过程。

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

回顾：从系数表示法到点值表示法

考虑多项式

要将该多项式从系数表示法转换为点值表示法，至少需要在 $4$ 个点上对其进行求值。

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

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

其中 $V(\omega)$ 称为 Vandermonde 矩阵，$\mathbf{a}$ 是表示系数的列向量。您可以参考关于 Vandermonde Matrices 的文章以详细了解它们。Vandermonde 矩阵的一个性质是其每一行都构成一个等比数列（geometric progression），即数列中的每一项都是通过将前一项乘以一个固定比率得到的。

在上面的矩阵 $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)$ 的求值结果的：

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

因此，我们得到：

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

但是，如果我们反过来已知求值结果（即向量 $\mathbf{y}$），并要求计算系数（即向量 $\mathbf{a}$）呢？

这可以使用 Vandermonde 矩阵 $V(\omega)$ 的逆矩阵（记为 $V^{-1}(\omega)$）通过以下运算来实现：

我们断言矩阵 $V(\omega)^{-1}$ 如下所示：

观察到 $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$ 次单位根的情况下，当使用以下 Vandermonde 矩阵实现 NTT 时，

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

逆 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$ 中各点处的求值向量，其给出如下：

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

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

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

我们现在证明向量 $\tilde{\mathbf{a}}$ 和 ${\mathbf{a}}$ 相等。换言之，我们要证明

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

我们在等式右侧（RHS）逐行执行矩阵乘法，以观察等式左侧（LHS）对应的系数是如何得出的。对于系数 $\tilde{a_0}$，我们将 $V(\omega)^{-1}$ 的第一行与向量 $\mathbf{y}$ 进行点积运算：

回顾上一章的内容，由于 $\omega$ 是一个本原的 $4$ 次单位根，因此求和

只要 $m$ 不是 $4$ 的倍数，就等于零。具体而言，

有关该概念的详细解析，请参阅关于 Orthogonality of Roots of Unity 的文章。通过代入不是 $4$ 的倍数的 $m$ 值，我们得到以下恒等式：

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

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

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

将各项分组以提取 $a_0,a_1,a_2$ 和 $a_3$ 的因子，可得：

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

请尝试自行展开 $\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 Book 中关于数论变换系列文章的一部分。