在之前的章节中，我们学习了数论变换（NTT），它在多项式的 k 次单位根处对其进行求值。这可以理解为将多项式从其系数表示法（coefficient form）转换为点值表示法（point-value form）。
通过将 k−1 次多项式的系数向量乘以一个 Vandermonde 矩阵可以执行 NTT，其时间复杂度为 O(k2)。更具吸引力的是，还可以使用该变换的快速递归版本，将时间复杂度降低至 O(klogk)。
在本章中，我们将开始学习 NTT 的逆变换，称为逆数论变换（Inverse Number Theoretic Transform，或 INTT）。它可以用于将多项式从点值表示法转换回系数表示法。这个过程被称为插值（interpolation）。
在我们关于 Lagrange interpolation 的文章中，我们已经看到了一种执行插值的方法。使用 Lagrange 插值与逆数论变换的区别有两方面：Lagrange 插值可以基于任何点集进行，而 INTT 只能在 k 次单位根的集合上进行。另一方面，Lagrange 插值的时间复杂度始终为 O(k2)，而 INTT 的时间复杂度可达到 O(klogk)。
在本章中，我们将：
- 回顾如何使用 Vandermonde 矩阵进行多项式求值；
- 提出一种同样使用 Vandermonde 矩阵进行计算的逆变换；
- 证明该逆变换可以撤销原始变换。换言之，我们将展示通过 NTT 进行求值，随后通过 INTT 进行插值，可以将多项式还原为其原始的系数表示法。
目前，我们将以次数为 3 的多项式的 INTT 为例，以便读者更容易跟上计算过程。
在后续章节中，我们将证明所提出的逆变换适用于任意次数的多项式。
回顾：从系数表示法到点值表示法
考虑多项式
f(x)=a0+a1x+a2x2+a3x3
要将该多项式从系数表示法转换为点值表示法，至少需要在 4 个点上对其进行求值。
例如，如果集合 S={1,ω,ω2,ω3} 代表求值点，其中 ω 是一个本原的 4 次单位根，则在这些点处的求值结果如下：
f(1)f(ω)f(ω2)f(ω3)=a0=a0=a0=a0++++a1a1ωa1ω2a1ω3++++a2a2ω2a2ω4a2ω6++++a3a3ω3a3ω6a3ω9
这可以用以下矩阵乘法来表示：
f(1)f(ω)f(ω2)f(ω3)y=11111ωω2ω31ω2ω4ω61ω3ω6ω9a0a1a2a3=V(ω)⋅ a
其中 V(ω) 称为 Vandermonde 矩阵，a 是表示系数的列向量。您可以参考关于 Vandermonde Matrices 的文章以详细了解它们。Vandermonde 矩阵的一个性质是其每一行都构成一个等比数列（geometric progression），即数列中的每一项都是通过将前一项乘以一个固定比率得到的。
在上面的矩阵 V(ω) 中，我们可以注意到：
- 第 1 行：[1 1 1 1] → 首项：1，公比：1
- 第 2 行：[1 ω ω2 ω3] → 首项：1，公比：ω
- 第 3 行：[1 ω2 ω4 ω6] → 首项：1，公比：ω2
- 第 4 行：[1 ω3 ω6 ω9] → 首项：1，公比：ω3
让我们回顾一下乘法 y=V(ω)⋅ a 是如何得出 f(x) 的求值结果的：
y=f(1)f(ω)f(ω2)f(ω3)=11111ωω2ω31ω2ω4ω61ω3ω6ω9a0a1a2a3
如果我们逐行执行 V(ω) 的矩阵乘法，可以得到：
f(1)=[1 1 1 1]⋅a0a1a2a3f(ω)=[1 ω ω2 ω3]⋅a0a1a2a3f(ω2)=[1 ω2 ω4 ω6]⋅a0a1a2a3f(ω3)=[1 ω3 ω6 ω9]⋅a0a1a2a3=1⋅a0+1⋅a1+1⋅a2+1⋅a3=a0+a1+a2+a3=1⋅a0+ω⋅a1+ω2⋅a2+ω3⋅a3=a0+a1ω+a2ω2+a3ω3=1⋅a0+ω2⋅a1+ω4⋅a2+ω6⋅a3=a0+a1ω2+a2ω4+a3ω6=1⋅a0+ω3⋅a1+ω6⋅a2+ω9⋅a3=a0+a1ω3+a2ω6+a3ω9
因此，我们得到：
y=f(1)f(ω)f(ω2)f(ω3)=a0a0a0a0++++a1a1ωa1ω2a1ω3++++a2a2ω2a2ω4a2ω6++++a3a3ω3a3ω6a3ω9
因此，如果已知多项式的系数表示法（由向量 a 表示），我们可以通过将 a 左乘 Vandermonde 矩阵 V(ω)，来获得它的点值表示法（由向量 y 表示）。
但是，如果我们反过来已知求值结果（即向量 y），并要求计算系数（即向量 a）呢？
这可以使用 Vandermonde 矩阵 V(ω) 的逆矩阵（记为 V−1(ω)）通过以下运算来实现：
a=V(ω)−1⋅y
我们断言矩阵 V(ω)−1 如下所示：
V(ω)−1=4111111ω−1ω−2ω−31ω−2ω−4ω−61ω−3ω−6ω−9
观察到 V(ω)−1 也具有类似的性质，即其每一行均构成一个等比数列：
- 第 1 行：[1 1 1 1] → 首项：1，公比：1
- 第 2 行：[1 ω−1 ω−2 ω−3] → 首项：1，公比：ω−1
- 第 3 行：[1 ω−2 ω−4 ω−6] → 首项：1，公比：ω−2
- 第 4 行：[1 ω−3 ω−6 ω−9] → 首项：1，公比：ω−3
因此，在这种情况下，Vandermonde 矩阵的逆矩阵本身也是另一个 Vandermonde 矩阵。
在接下来的小节中，我们将使用 4 次单位根的例子来展示我们的断言是正确的。在后续章节中，我们将给出一般性的证明。
我们将证明，在 k 次单位根的情况下，当使用以下 Vandermonde 矩阵实现 NTT 时，
V(ω)=111⋮11ωω2⋮ωk−11ω2ω4⋮ω2(k−1)⋯⋯⋯⋱⋯1ωk−1ω2(k−1)⋮ω(k−1)(k−1),
其逆矩阵 V(ω)−1 可以通过将每个 ω 的幂替换为 ω1 并除以因子 k 来得到，如下所示：
V(ω)−1=k1111⋮11ω−1ω−2⋮ω−(k−1)1ω−2ω−4⋮ω−2(k−1)⋯⋯⋯⋱⋯1ω−(k−1)ω−2(k−1)⋮ω−(k−1)(k−1).
逆 Vandermonde 矩阵在与给定多项式在单位根处的求值向量相乘时，会返回该多项式的系数向量。
计算 V(ω)−1⋅y
为了演示 V(ω)−1 和 y 之间的矩阵乘法能够还原系数向量 a，让我们使用之前的例子，其中 f(x)=a0+a1x+a2x2+a3x3，S={1,ω,ω2,ω3} 且 k=4。
回想一下，y 是 f(x) 在集合 S 中各点处的求值向量，其给出如下：
y=f(1)f(ω)f(ω2)f(ω3)=a0a0a0a0++++a1a1ωa1ω2a1ω3++++a2a2ω2a2ω4a2ω6++++a3a3ω3a3ω6a3ω9
让我们执行 V(ω)−1 和 y 之间的矩阵乘法：
a~a0~a1~a2~a3~=V(ω)−1⋅y=4111111ω−1ω−2ω−31ω−2ω−4ω−61ω−3ω−6ω−9f(1)f(ω)f(ω2)f(ω3)
我们的目标是证明从上述矩阵乘法中获得的向量 a~ 等于 f(x) 的系数向量 a。
将向量 y 中的求值结果 f(1),f(ω),f(ω2) 和 f(ω3) 代入，我们可以计算系数 a~：
a~a0~a1~a2~a3~=V(ω)−1⋅y=4111111ω−1ω−2ω−31ω−2ω−4ω−61ω−3ω−6ω−9a0a0a0a0++++a1a1ωa1ω2a1ω3++++a2a2ω2a2ω4a2ω6++++a3a3ω3a3ω6a3ω9
我们现在证明向量 a~ 和 a 相等。换言之，我们要证明
a0~a1~a2~a3~=a0,=a1,=a2,=a3.
计算系数 a0~,a1~,a2~ 和 a3~
我们在等式右侧（RHS）逐行执行矩阵乘法，以观察等式左侧（LHS）对应的系数是如何得出的。对于系数 a0~，我们将 V(ω)−1 的第一行与向量 y 进行点积运算：
a0~a1~a2~a3~=4111111ω−1ω−2ω−31ω−2ω−4ω−61ω−3ω−6ω−9f(1)f(ω)f(ω2)f(ω3)
a0~ V(ω)−1 的第一行与 y 的点积=41(1⋅f(1)+1⋅f(ω)+1⋅f(ω2)+1⋅f(ω3))=41(1⋅f(1)(a0+a1+a2+a3)+1⋅f(ω)(a0+a1ω+a2ω2+a3ω3)+1⋅f(ω2)(a0+a1ω2+a2ω4+a3ω6)+1⋅f(ω3)(a0+a1ω3+a2ω6+a3ω9))=41(4a0+a1(1+ω+ω2+ω3)+a2(1+ω2+ω4+ω6)+a3(1+ω3+ω6+ω9))
回顾上一章的内容，由于 ω 是一个本原的 4 次单位根，因此求和
k=0∑3ωmk
只要 m 不是 4 的倍数，就等于零。具体而言，
k=0∑3ωmk=ωm⋅0+ωm⋅1+ωm⋅2+ωm⋅3=1+ωm+ω2m+ω3m=0
有关该概念的详细解析，请参阅关于 Orthogonality of Roots of Unity 的文章。通过代入不是 4 的倍数的 m 值，我们得到以下恒等式：
当 m当 m当 m当 m当 m当 m=1=2=3=−1=−2=−3→→→→→→1+ω+ω2+ω3=0,1+ω2+ω4+ω6=0,1+ω3+ω6+ω9=0,1+ω−1+ω−2+ω−3=0,1+ω−2+ω−4+ω−6=0,1+ω−3+ω−6+ω−9=0,
因此，所有乘以 a1、a2 和 a3 的项都消失了，剩下
a0~a0~=41(4a0=41⋅4a0=a0+++a1=0(1+ω+ω2+ω3)a2=0(1+ω2+ω4+ω6)a3=0(1+ω3+ω6+ω9))
类似地，为了计算 a1~，我们将 V(ω)−1 的第二行与 y 进行点积运算：
a0~a1~a2~a3~=4111111ω−1ω−2ω−31ω−2ω−4ω−61ω−3ω−6ω−9f(1)f(ω)f(ω2)f(ω3)
a1~V(ω)−1 的第 2 行与 y 的点积=41(1⋅f(1)+ω−1f(ω)+ω−2f(ω2)+ω−3f(ω3))
代入求值结果 f(1),f(ω),f(ω2) 和 f(ω3) 的表达式，我们得到：
a1~=41(1(a0+a1+a2+a3)+ω−1(a0+a1ω+a2ω2+a3ω3)+ω−2(a0+a1ω2+a2ω4+a3ω6)+ω−3(a0+a1ω3+a2ω6+a3ω9))
将各项分组以提取 a0,a1,a2 和 a3 的因子，可得：
a1~=41(a0(1+ω−1+ω−2+ω−3)+a1(1+ω−1ω+ω−2ω2+ω−3ω3)+a2(1+ω−1ω2+ω−2ω4+ω−3ω6)+a3(1+ω−1ω3+ω−2ω6+ω−3ω9))=41(a0(1+ω−1+ω−2+ω−3)+4a1+a2(1+ω1+ω2+ω3)+a3(1+ω2+ω4+ω6))
同样，括号内与 a0,a2,a3 因子相关的项消失了，剩下：
a1~=41⋅4a1=a1
请尝试自行展开 a2~ 和 a3~ 的乘法运算，并观察它们如何按照我们上面使用的相同逻辑进行简化。如预期那样，您会发现 a2~=a2 且 a3~=a3。
这完成了对 V(ω)−1⋅y=a 的演示。据此，我们已经证明了在 k=4 的情况下，Vandermonde 矩阵的逆矩阵也是一个 Vandermonde 矩阵。一般性的 k 值情况将在后续章节中予以证明。
本文是我们 ZK Book 中关于数论变换系列文章的一部分。