手算 NTT 算法

Last updated on Nov 12, 2025

NTT（数论变换）算法将有限域上的多项式从系数表示法转换为点值表示法。

如果多项式的次数为 $d$ ，那么我们会在 $k$ 次单位根上对其进行求值，其中 $k\gt d.$

我们不是在 $k$ 次单位根集合 $\set{1,\omega,\omega^2,...,\omega^{k-1}}$ 的每个点上逐一计算多项式 $f(x)$ ，而是利用多值函数的像保持定理来对多值函数进行求值，该多值函数是通过在定义域 $\set{1}$ 上将 $f$ 中的 $x$ 替换为 $\sqrt[k]{x}$ 创建的。然后我们将平方根的计算结果从 $\set{1}$ 迭代扩展到 $\set{1,\omega^{k/2}}$ ，再扩展到 $\set{1,\omega^{k/4},\omega^{k/2},-\omega^{k/4}}$ ，依此类推，直到将计算结果扩展到 $k$ 次单位根。

该方法的运行时间为 $\mathcal{O}(n \log n)$ 。

在 4 次单位根上计算 $f(x)=a_0+a_1x+a_2x^2+a_3x^3$

首先，我们对该函数进行因式分解，以最大化 $x^2$ 的出现次数，因为 $2=k/2$ ，且 $x^{k/2}$ 在单位根上很容易求值（根据单位根的幂是偶数还是奇数，结果只为 $\set{1,-1}$ ）。

这将得到以下函数：

f(x)=a_0+a_2x^2+x(a_1+a_3x^2)

接下来，我们对 $f$ 进行变换，使得 $x\rightarrow\sqrt[4]{x}$ ，这会得到：

f(x)=a_0+a_2\sqrt{x}+\sqrt[4]{x}(a_1+a_3\sqrt{x})

这是平方根展开图：

现在，我们将此结果与逐一在 4 次单位根上计算 $f(x)$ 进行比较：

\begin{align*} f(1) &= a_0 &+& a_1(1) &+& a_2(1)^2 &+& a_3(1)^3\\ f(-1) &= a_0 &+& a_1(-1) &+& a_2(-1)^2 &+& a_3(-1)^3\\ f(\omega) &= a_0 &+& a_1(\omega) &+& a_2(\omega)^2 &+& a_3(\omega)^3\\ f(-\omega) &= a_0 &+& a_1(-\omega) &+& a_2(-\omega)^2 &+& a_3(-\omega)^3 \end{align*}

我们已知 $\omega^2=(-\omega^2)=-1$ 且 $\omega^3=-\omega$ ，并且 $(-\omega)^3=(-1)^3(\omega)^3=-\omega^3=-(-\omega)=\omega$ 。通过代入，我们得到：

\begin{align*} f(1) &= a_0 &+& a_1 &+& a_2 &+& a_3\\ f(-1) &= a_0 &-& a_1 &+& a_2 &-& a_3\\ f(\omega) &= a_0 &+& a_1\omega &-& a_2 &-& a_3\omega\\ f(-\omega) &= a_0 &-& a_1\omega &-& a_2 &+& a_3\omega \end{align*}

练习： 使用上述方法在 4 次单位根上计算 $a_0+a_1x+a_2x^2$ 。提示：使用上面的示例并设 $a_3=0$ 。

树的高度为 $\log n$ ，我们在每一行执行 $\mathcal{O}(n)$ 次操作，因此运行时间为 $\mathcal{O}(n \log n)$ 。

在 8 次单位根上计算 $f(x)=a_0+a_1x+...+a_7x^7$

首先，我们重新排列多项式以最大化 $x^4$ 项的数量（因为 k = 8）。这得到：

f(x)=a_0+a_4x^4+x^2(a_2+a_6x^4)+x((a_1+a_5x^4)+x^2(a_3+a_7x^4))

现在我们代入 $x\rightarrow\sqrt[8]{x}$ 以得到多值函数 $g(x)$ ：

g(x)=a_0+a_4\sqrt{x}+\sqrt[4]{x}(a_2+a_6\sqrt{x})+\sqrt[8]{x}((a_1+a_5\sqrt{x})+\sqrt[4]{x}(a_3+a_7\sqrt{x}))

由于在一张图里画出整棵求值树会非常大，我们将画出求值树的左侧，即我们计算 $\sqrt{1}=1$ 的部分，并首先展示该图：

从上图可以得出：

\begin{align*} f(1)=((a_0+a_4)+(a_2+a_6))+((a_1+a_5)+(a_3+a_7))\\ f(-1)=((a_0+a_4)+(a_2+a_6))+((a_1+a_5)+(a_3+a_7))\\ f(\omega^2)=((a_0+a_4)-(a_2+a_6))+\omega((a_1+a_5)-(a_3+a_7))\\ f(-\omega^2)=((a_0+a_4)-(a_2+a_6))-\omega((a_1+a_5)-(a_3+a_7))\\ \end{align*}

现在我们展开求值树的右侧，此时 $\sqrt{x}=-1$ ：

由该结果，我们得出：

\begin{align*} f(\omega)=((a_0-a_4)+\omega^2(a_2-a_6))+\omega((a_1-a_5)+\omega^2(a_3-a_7))\\ f(-\omega)=((a_0-a_4)+\omega^2(a_2-a_6))-\omega((a_1-a_5)+\omega^2(a_3-a_7))\\ f(\omega^3)=((a_0-a_4)-\omega^2(a_2-a_6))+\omega^3((a_1-a_5)-\omega^2(a_3-a_7))\\ f(-\omega^3)=((a_0-a_4)-\omega^2(a_2-a_6))-\omega^3((a_1-a_5)-\omega^2(a_3-a_7)) \end{align*}

将求值结果合并并展开 omega 项，我们得到：

\begin{align*} f(1) &= a_0 &+ a_4 &+ a_2 &+ a_6 &+ a_1 &+ a_5 &+ a_3 &+ a_7\\f(-1) &= a_0 &+ a_4 &+ a_2 &+ a_6 &- a_1 &- a_5 &- a_3 &- a_7\\f(\omega^2) &= a_0 &+ a_4 &- a_2 &- a_6 &+ a_1\omega^2 &+ a_5\omega^2 &- a_3\omega^2 &- a_7\omega^2\\f(-\omega^2)&= a_0 &+ a_4 &- a_2 &- a_6 &- a_1\omega^2 &- a_5\omega^2 &+ a_3\omega^2 &+ a_7\omega^2\\f(\omega) &= a_0 &- a_4 &+ a_2\omega^2 &- a_6\omega^2 &+ a_1\omega &- a_5\omega &+ a_3\omega^3 &- a_7\omega^3\\f(-\omega) &= a_0 &- a_4 &+ a_2\omega^2 &- a_6\omega^2 &- a_1\omega &+ a_5\omega &- a_3\omega^3 &+ a_7\omega^3\\f(\omega^3) &= a_0 &- a_4 &- a_2\omega^2 &+ a_6\omega^2 &+ a_1\omega^3 &- a_5\omega^3 &+ a_3\omega &- a_7\omega\\f(-\omega^3)&= a_0 &- a_4 &- a_2\omega^2 &+ a_6\omega^2 &- a_1\omega^3 &+ a_5\omega^3 &- a_3\omega & a_7\omega\end{align*}

接下来，我们按系数升序排列：

\begin{align*} f(1) &= a_0 &+ a_1 &+ a_2 &+ a_3 &+ a_4 &+ a_5 &+ a_6 &+ a_7\\ f(-1) &= a_0 &- a_1 &+ a_2 &- a_3 &+ a_4 &- a_5 &+ a_6 &- a_7\\ f(\omega^2) &= a_0 &+ a_1\omega^2 &- a_2 &- a_3\omega^2 &+ a_4 &+ a_5\omega^2 &- a_6 &- a_7\omega^2\\ f(-\omega^2)&= a_0 &- a_1\omega^2 &- a_2 &+ a_3\omega^2 &+ a_4 &- a_5\omega^2 &- a_6 &+ a_7\omega^2\\ f(\omega) &= a_0 &+ a_1\omega &+ a_2\omega^2 &+ a_3\omega^3 &- a_4 &- a_5\omega &- a_6\omega^2 &- a_7\omega^3\\ f(-\omega) &= a_0 &- a_1\omega &+ a_2\omega^2 &- a_3\omega^3 &- a_4 &+ a_5\omega &- a_6\omega^2 &+ a_7\omega^3\\ f(\omega^3) &= a_0 &+ a_1\omega^3 &- a_2\omega^2 &+ a_3\omega &- a_4 &- a_5\omega^3 &+ a_6\omega^2 &- a_7\omega\\ f(-\omega^3)&= a_0 &- a_1\omega^3 &- a_2\omega^2 &- a_3\omega &- a_4 &+ a_5\omega^3 &+ a_6\omega^2 &+ a_7\omega \end{align*}

现在，让我们重新排列求值结果，使其按照 $f(1)$ 、 $f(\omega)$ 、…、 $f(\omega^7)$ 的顺序排列：

\begin{align*} f(1) &= a_0 &+ a_1 &+ a_2 &+ a_3 &+ a_4 &+ a_5 &+ a_6 &+ a_7\\ f(\omega) &= a_0 &+ a_1\omega &+ a_2\omega^2 &+ a_3\omega^3 &- a_4 &- a_5\omega &- a_6\omega^2 &- a_7\omega^3\\ f(\omega^2) &= a_0 &+ a_1\omega^2 &- a_2 &- a_3\omega^2 &+ a_4 &+ a_5\omega^2 &- a_6 &- a_7\omega^2\\ f(\omega^3) &= a_0 &+ a_1\omega^3 &- a_2\omega^2 &+ a_3\omega &- a_4 &- a_5\omega^3 &+ a_6\omega^2 &- a_7\omega\\ f(-1) &= a_0 &- a_1 &+ a_2 &- a_3 &+ a_4 &- a_5 &+ a_6 &- a_7\\ f(-\omega) &= a_0 &- a_1\omega &+ a_2\omega^2 &- a_3\omega^3 &- a_4 &+ a_5\omega &- a_6\omega^2 &+ a_7\omega^3\\ f(-\omega^2)&= a_0 &- a_1\omega^2 &- a_2 &+ a_3\omega^2 &+ a_4 &- a_5\omega^2 &- a_6 &+ a_7\omega^2\\ f(-\omega^3)&= a_0 &- a_1\omega^3 &- a_2\omega^2 &- a_3\omega &- a_4 &+ a_5\omega^3 &+ a_6\omega^2 &+ a_7\omega \end{align*}

如果我们将此结果与 8 次单位根的 Vandermonde 矩阵进行比较，可以看到我们正确地计算了 $\omega$ 的各次幂。

\mathbf{V} =\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & \omega & \omega^{2} & \omega^{3} & -1 & -\omega & -\omega^{2} & -\omega^{3} \\ 1 & \omega^{2} & -1 & -\omega^{2} & 1 & \omega^{2} & -1 & -\omega^{2} \\ 1 & \omega^{3} & -\omega^{2} & \omega & -1 & -\omega^{3} & \omega^{2} & -\omega \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ 1 & -\omega & \omega^{2} & -\omega^{3} & -1 & \omega & -\omega^{2} & \omega^{3} \\ 1 & -\omega^{2} & -1 & \omega^{2} & 1 & -\omega^{2} & -1 & \omega^{2} \\ 1 & -\omega^{3} & -\omega^{2} & -\omega & -1 & \omega^{3} & \omega^{2} & \omega \end{bmatrix}

Vandermonde 矩阵计算

上述 Vandermonde 矩阵的推导过程如下。在 $x=\set{1,\omega,\omega^2,...,\omega^7}$ 时，矩阵的每一行都是 $f(x)=a_0+a_1x+...+a_7x^7$ 中 $x$ 的对应幂。

\mathbf{V}= \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & \omega & \omega^{2} & \omega^{3} & \omega^{4} & \omega^{5} & \omega^{6} & \omega^{7}\\ 1 & \omega^{2} & \omega^{4} & \omega^{6} & \omega^{8} & \omega^{10} & \omega^{12} & \omega^{14}\\ 1 & \omega^{3} & \omega^{6} & \omega^{9} & \omega^{12} & \omega^{15} & \omega^{18} & \omega^{21}\\ 1 & \omega^{4} & \omega^{8} & \omega^{12} & \omega^{16} & \omega^{20} & \omega^{24} & \omega^{28}\\ 1 & \omega^{5} & \omega^{10} & \omega^{15} & \omega^{20} & \omega^{25} & \omega^{30} & \omega^{35}\\ 1 & \omega^{6} & \omega^{12} & \omega^{18} & \omega^{24} & \omega^{30} & \omega^{36} & \omega^{42}\\ 1 & \omega^{7} & \omega^{14} & \omega^{21} & \omega^{28} & \omega^{35} & \omega^{42} & \omega^{49} \end{bmatrix}

接下来，我们将指数分离出 8 的倍数因子：

\mathbf{V}= \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & \omega & \omega^{2} & \omega^{3} & \omega^{4} & \omega^{5} & \omega^{6} & \omega^{7}\\ 1 & \omega^{2} & \omega^{4} & \omega^{6} & \omega^{8} & \omega^{8}\omega^{2} & \omega^{8}\omega^{4} & \omega^{8}\omega^{6}\\ 1 & \omega^{3} & \omega^{6} & \omega^{8}\omega & \omega^{8}\omega^{4} & \omega^{8}\omega^{7} & \omega^{16}\omega^{2} & \omega^{16}\omega^{5}\\ 1 & \omega^{4} & \omega^{8} & \omega^{8}\omega^{4} & \omega^{16} & \omega^{16}\omega^{4} & \omega^{24} & \omega^{24}\omega^{4}\\ 1 & \omega^{5} & \omega^{8}\omega^{2} & \omega^{8}\omega^{7} & \omega^{16}\omega^{4} & \omega^{24}\omega & \omega^{24}\omega^{6} & \omega^{32}\omega^{3}\\ 1 & \omega^{6} & \omega^{8}\omega^{4} & \omega^{16}\omega^{2} & \omega^{24} & \omega^{24}\omega^{6} & \omega^{32}\omega^{4} & \omega^{40}\omega^{2}\\ 1 & \omega^{7} & \omega^{8}\omega^{6} & \omega^{16}\omega^{5} & \omega^{24}\omega^{4} & \omega^{32}\omega^{3} & \omega^{40}\omega^{2} & \omega^{48}\omega\\ \end{bmatrix}

消去 8 的倍数因子后，我们有：

\mathbf{V} = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & \omega & \omega^{2} & \omega^{3} & \omega^{4} & \omega^{5} & \omega^{6} & \omega^{7}\\ 1 & \omega^{2} & \omega^{4} & \omega^{6} & 1 & \omega^{2} & \omega^{4} & \omega^{6}\\ 1 & \omega^{3} & \omega^{6} & \omega & \omega^{4} & \omega^{7} & \omega^{2} & \omega^{5}\\ 1 & \omega^{4} & 1 & \omega^{4} & 1 & \omega^{4} & 1 & \omega^{4}\\ 1 & \omega^{5} & \omega^{2} & \omega^{7} & \omega^{4} & \omega & \omega^{6} & \omega^{3}\\ 1 & \omega^{6} & \omega^{4} & \omega^{2} & 1 & \omega^{6} & \omega^{4} & \omega^{2}\\ 1 & \omega^{7} & \omega^{6} & \omega^{5} & \omega^{4} & \omega^{3} & \omega^{2} & \omega \end{bmatrix}

在代入 $\omega^4=-1$ 、 $\omega^5=-\omega$ 、 $\omega^6=-\omega^2$ 、 $\omega^7=-\omega^3$ 进行替换后，我们得到了最初的 Vandermonde 矩阵：

\mathbf{V} =\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & \omega & \omega^{2} & \omega^{3} & -1 & -\omega & -\omega^{2} & -\omega^{3} \\ 1 & \omega^{2} & -1 & -\omega^{2} & 1 & \omega^{2} & -1 & -\omega^{2} \\ 1 & \omega^{3} & -\omega^{2} & \omega & -1 & -\omega^{3} & \omega^{2} & -\omega \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ 1 & -\omega & \omega^{2} & -\omega^{3} & -1 & \omega & -\omega^{2} & \omega^{3} \\ 1 & -\omega^{2} & -1 & \omega^{2} & 1 & -\omega^{2} & -1 & \omega^{2} \\ 1 & -\omega^{3} & -\omega^{2} & -\omega & -1 & \omega^{3} & \omega^{2} & \omega \end{bmatrix}

练习： 在 8 次单位根上计算 $f(x)=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5+a_6x^6$ 。同样，请注意你可以设 $a_7=0$ 。

练习： 在 $\mathbb{F}_q$ （其中 $q=17$ ）的 4 次单位根上计算 $f(x)=3 +2x+9x^2+x^3$ 。使用 Python 寻找一个本原 4 次单位根作为起点。

总结

使用平方根展开法在 $k$ 次单位根上计算多项式，与逐一在单位根上计算该多项式会得到相同的求值结果。这之所以成立，归功于多值函数的像保持定理（Image Preservation Theorem for Multivalued Functions），因为我们仅仅是在定义域 $\set{1}$ 上对该多值函数进行求值。

这种方法节省了计算成本，因为在每一步中，只有一半的平方根需要被计算并与配对的系数或系数和相乘。对于剩余的求值项，结果只需直接向下复制，而无需重新计算。

Last updated on Nov 12, 2025

NTT（数论变换）算法将有限域上的多项式从系数表示法转换为点值表示法。

如果多项式的次数为 $d$ ，那么我们会在 $k$ 次单位根上对其进行求值，其中 $k\gt d.$

该方法的运行时间为 $\mathcal{O}(n \log n)$ 。

在 4 次单位根上计算 $f(x)=a_0+a_1x+a_2x^2+a_3x^3$

这将得到以下函数：

f(x)=a_0+a_2x^2+x(a_1+a_3x^2)

接下来，我们对 $f$ 进行变换，使得 $x\rightarrow\sqrt[4]{x}$ ，这会得到：

f(x)=a_0+a_2\sqrt{x}+\sqrt[4]{x}(a_1+a_3\sqrt{x})

这是平方根展开图：

现在，我们将此结果与逐一在 4 次单位根上计算 $f(x)$ 进行比较：

\begin{align*} f(1) &= a_0 &+& a_1(1) &+& a_2(1)^2 &+& a_3(1)^3\\ f(-1) &= a_0 &+& a_1(-1) &+& a_2(-1)^2 &+& a_3(-1)^3\\ f(\omega) &= a_0 &+& a_1(\omega) &+& a_2(\omega)^2 &+& a_3(\omega)^3\\ f(-\omega) &= a_0 &+& a_1(-\omega) &+& a_2(-\omega)^2 &+& a_3(-\omega)^3 \end{align*}

我们已知 $\omega^2=(-\omega^2)=-1$ 且 $\omega^3=-\omega$ ，并且 $(-\omega)^3=(-1)^3(\omega)^3=-\omega^3=-(-\omega)=\omega$ 。通过代入，我们得到：

\begin{align*} f(1) &= a_0 &+& a_1 &+& a_2 &+& a_3\\ f(-1) &= a_0 &-& a_1 &+& a_2 &-& a_3\\ f(\omega) &= a_0 &+& a_1\omega &-& a_2 &-& a_3\omega\\ f(-\omega) &= a_0 &-& a_1\omega &-& a_2 &+& a_3\omega \end{align*}

练习： 使用上述方法在 4 次单位根上计算 $a_0+a_1x+a_2x^2$ 。提示：使用上面的示例并设 $a_3=0$ 。

树的高度为 $\log n$ ，我们在每一行执行 $\mathcal{O}(n)$ 次操作，因此运行时间为 $\mathcal{O}(n \log n)$ 。

在 8 次单位根上计算 $f(x)=a_0+a_1x+...+a_7x^7$

首先，我们重新排列多项式以最大化 $x^4$ 项的数量（因为 k = 8）。这得到：

f(x)=a_0+a_4x^4+x^2(a_2+a_6x^4)+x((a_1+a_5x^4)+x^2(a_3+a_7x^4))

现在我们代入 $x\rightarrow\sqrt[8]{x}$ 以得到多值函数 $g(x)$ ：

g(x)=a_0+a_4\sqrt{x}+\sqrt[4]{x}(a_2+a_6\sqrt{x})+\sqrt[8]{x}((a_1+a_5\sqrt{x})+\sqrt[4]{x}(a_3+a_7\sqrt{x}))

由于在一张图里画出整棵求值树会非常大，我们将画出求值树的左侧，即我们计算 $\sqrt{1}=1$ 的部分，并首先展示该图：

从上图可以得出：

\begin{align*} f(1)=((a_0+a_4)+(a_2+a_6))+((a_1+a_5)+(a_3+a_7))\\ f(-1)=((a_0+a_4)+(a_2+a_6))+((a_1+a_5)+(a_3+a_7))\\ f(\omega^2)=((a_0+a_4)-(a_2+a_6))+\omega((a_1+a_5)-(a_3+a_7))\\ f(-\omega^2)=((a_0+a_4)-(a_2+a_6))-\omega((a_1+a_5)-(a_3+a_7))\\ \end{align*}

现在我们展开求值树的右侧，此时 $\sqrt{x}=-1$ ：

由该结果，我们得出：

\begin{align*} f(\omega)=((a_0-a_4)+\omega^2(a_2-a_6))+\omega((a_1-a_5)+\omega^2(a_3-a_7))\\ f(-\omega)=((a_0-a_4)+\omega^2(a_2-a_6))-\omega((a_1-a_5)+\omega^2(a_3-a_7))\\ f(\omega^3)=((a_0-a_4)-\omega^2(a_2-a_6))+\omega^3((a_1-a_5)-\omega^2(a_3-a_7))\\ f(-\omega^3)=((a_0-a_4)-\omega^2(a_2-a_6))-\omega^3((a_1-a_5)-\omega^2(a_3-a_7)) \end{align*}

将求值结果合并并展开 omega 项，我们得到：

\begin{align*} f(1) &= a_0 &+ a_4 &+ a_2 &+ a_6 &+ a_1 &+ a_5 &+ a_3 &+ a_7\\f(-1) &= a_0 &+ a_4 &+ a_2 &+ a_6 &- a_1 &- a_5 &- a_3 &- a_7\\f(\omega^2) &= a_0 &+ a_4 &- a_2 &- a_6 &+ a_1\omega^2 &+ a_5\omega^2 &- a_3\omega^2 &- a_7\omega^2\\f(-\omega^2)&= a_0 &+ a_4 &- a_2 &- a_6 &- a_1\omega^2 &- a_5\omega^2 &+ a_3\omega^2 &+ a_7\omega^2\\f(\omega) &= a_0 &- a_4 &+ a_2\omega^2 &- a_6\omega^2 &+ a_1\omega &- a_5\omega &+ a_3\omega^3 &- a_7\omega^3\\f(-\omega) &= a_0 &- a_4 &+ a_2\omega^2 &- a_6\omega^2 &- a_1\omega &+ a_5\omega &- a_3\omega^3 &+ a_7\omega^3\\f(\omega^3) &= a_0 &- a_4 &- a_2\omega^2 &+ a_6\omega^2 &+ a_1\omega^3 &- a_5\omega^3 &+ a_3\omega &- a_7\omega\\f(-\omega^3)&= a_0 &- a_4 &- a_2\omega^2 &+ a_6\omega^2 &- a_1\omega^3 &+ a_5\omega^3 &- a_3\omega & a_7\omega\end{align*}

接下来，我们按系数升序排列：

\begin{align*} f(1) &= a_0 &+ a_1 &+ a_2 &+ a_3 &+ a_4 &+ a_5 &+ a_6 &+ a_7\\ f(-1) &= a_0 &- a_1 &+ a_2 &- a_3 &+ a_4 &- a_5 &+ a_6 &- a_7\\ f(\omega^2) &= a_0 &+ a_1\omega^2 &- a_2 &- a_3\omega^2 &+ a_4 &+ a_5\omega^2 &- a_6 &- a_7\omega^2\\ f(-\omega^2)&= a_0 &- a_1\omega^2 &- a_2 &+ a_3\omega^2 &+ a_4 &- a_5\omega^2 &- a_6 &+ a_7\omega^2\\ f(\omega) &= a_0 &+ a_1\omega &+ a_2\omega^2 &+ a_3\omega^3 &- a_4 &- a_5\omega &- a_6\omega^2 &- a_7\omega^3\\ f(-\omega) &= a_0 &- a_1\omega &+ a_2\omega^2 &- a_3\omega^3 &- a_4 &+ a_5\omega &- a_6\omega^2 &+ a_7\omega^3\\ f(\omega^3) &= a_0 &+ a_1\omega^3 &- a_2\omega^2 &+ a_3\omega &- a_4 &- a_5\omega^3 &+ a_6\omega^2 &- a_7\omega\\ f(-\omega^3)&= a_0 &- a_1\omega^3 &- a_2\omega^2 &- a_3\omega &- a_4 &+ a_5\omega^3 &+ a_6\omega^2 &+ a_7\omega \end{align*}

现在，让我们重新排列求值结果，使其按照 $f(1)$ 、 $f(\omega)$ 、…、 $f(\omega^7)$ 的顺序排列：

\begin{align*} f(1) &= a_0 &+ a_1 &+ a_2 &+ a_3 &+ a_4 &+ a_5 &+ a_6 &+ a_7\\ f(\omega) &= a_0 &+ a_1\omega &+ a_2\omega^2 &+ a_3\omega^3 &- a_4 &- a_5\omega &- a_6\omega^2 &- a_7\omega^3\\ f(\omega^2) &= a_0 &+ a_1\omega^2 &- a_2 &- a_3\omega^2 &+ a_4 &+ a_5\omega^2 &- a_6 &- a_7\omega^2\\ f(\omega^3) &= a_0 &+ a_1\omega^3 &- a_2\omega^2 &+ a_3\omega &- a_4 &- a_5\omega^3 &+ a_6\omega^2 &- a_7\omega\\ f(-1) &= a_0 &- a_1 &+ a_2 &- a_3 &+ a_4 &- a_5 &+ a_6 &- a_7\\ f(-\omega) &= a_0 &- a_1\omega &+ a_2\omega^2 &- a_3\omega^3 &- a_4 &+ a_5\omega &- a_6\omega^2 &+ a_7\omega^3\\ f(-\omega^2)&= a_0 &- a_1\omega^2 &- a_2 &+ a_3\omega^2 &+ a_4 &- a_5\omega^2 &- a_6 &+ a_7\omega^2\\ f(-\omega^3)&= a_0 &- a_1\omega^3 &- a_2\omega^2 &- a_3\omega &- a_4 &+ a_5\omega^3 &+ a_6\omega^2 &+ a_7\omega \end{align*}

如果我们将此结果与 8 次单位根的 Vandermonde 矩阵进行比较，可以看到我们正确地计算了 $\omega$ 的各次幂。

\mathbf{V} =\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & \omega & \omega^{2} & \omega^{3} & -1 & -\omega & -\omega^{2} & -\omega^{3} \\ 1 & \omega^{2} & -1 & -\omega^{2} & 1 & \omega^{2} & -1 & -\omega^{2} \\ 1 & \omega^{3} & -\omega^{2} & \omega & -1 & -\omega^{3} & \omega^{2} & -\omega \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ 1 & -\omega & \omega^{2} & -\omega^{3} & -1 & \omega & -\omega^{2} & \omega^{3} \\ 1 & -\omega^{2} & -1 & \omega^{2} & 1 & -\omega^{2} & -1 & \omega^{2} \\ 1 & -\omega^{3} & -\omega^{2} & -\omega & -1 & \omega^{3} & \omega^{2} & \omega \end{bmatrix}

Vandermonde 矩阵计算

上述 Vandermonde 矩阵的推导过程如下。在 $x=\set{1,\omega,\omega^2,...,\omega^7}$ 时，矩阵的每一行都是 $f(x)=a_0+a_1x+...+a_7x^7$ 中 $x$ 的对应幂。

\mathbf{V}= \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & \omega & \omega^{2} & \omega^{3} & \omega^{4} & \omega^{5} & \omega^{6} & \omega^{7}\\ 1 & \omega^{2} & \omega^{4} & \omega^{6} & \omega^{8} & \omega^{10} & \omega^{12} & \omega^{14}\\ 1 & \omega^{3} & \omega^{6} & \omega^{9} & \omega^{12} & \omega^{15} & \omega^{18} & \omega^{21}\\ 1 & \omega^{4} & \omega^{8} & \omega^{12} & \omega^{16} & \omega^{20} & \omega^{24} & \omega^{28}\\ 1 & \omega^{5} & \omega^{10} & \omega^{15} & \omega^{20} & \omega^{25} & \omega^{30} & \omega^{35}\\ 1 & \omega^{6} & \omega^{12} & \omega^{18} & \omega^{24} & \omega^{30} & \omega^{36} & \omega^{42}\\ 1 & \omega^{7} & \omega^{14} & \omega^{21} & \omega^{28} & \omega^{35} & \omega^{42} & \omega^{49} \end{bmatrix}

接下来，我们将指数分离出 8 的倍数因子：

\mathbf{V}= \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & \omega & \omega^{2} & \omega^{3} & \omega^{4} & \omega^{5} & \omega^{6} & \omega^{7}\\ 1 & \omega^{2} & \omega^{4} & \omega^{6} & \omega^{8} & \omega^{8}\omega^{2} & \omega^{8}\omega^{4} & \omega^{8}\omega^{6}\\ 1 & \omega^{3} & \omega^{6} & \omega^{8}\omega & \omega^{8}\omega^{4} & \omega^{8}\omega^{7} & \omega^{16}\omega^{2} & \omega^{16}\omega^{5}\\ 1 & \omega^{4} & \omega^{8} & \omega^{8}\omega^{4} & \omega^{16} & \omega^{16}\omega^{4} & \omega^{24} & \omega^{24}\omega^{4}\\ 1 & \omega^{5} & \omega^{8}\omega^{2} & \omega^{8}\omega^{7} & \omega^{16}\omega^{4} & \omega^{24}\omega & \omega^{24}\omega^{6} & \omega^{32}\omega^{3}\\ 1 & \omega^{6} & \omega^{8}\omega^{4} & \omega^{16}\omega^{2} & \omega^{24} & \omega^{24}\omega^{6} & \omega^{32}\omega^{4} & \omega^{40}\omega^{2}\\ 1 & \omega^{7} & \omega^{8}\omega^{6} & \omega^{16}\omega^{5} & \omega^{24}\omega^{4} & \omega^{32}\omega^{3} & \omega^{40}\omega^{2} & \omega^{48}\omega\\ \end{bmatrix}

消去 8 的倍数因子后，我们有：

\mathbf{V} = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & \omega & \omega^{2} & \omega^{3} & \omega^{4} & \omega^{5} & \omega^{6} & \omega^{7}\\ 1 & \omega^{2} & \omega^{4} & \omega^{6} & 1 & \omega^{2} & \omega^{4} & \omega^{6}\\ 1 & \omega^{3} & \omega^{6} & \omega & \omega^{4} & \omega^{7} & \omega^{2} & \omega^{5}\\ 1 & \omega^{4} & 1 & \omega^{4} & 1 & \omega^{4} & 1 & \omega^{4}\\ 1 & \omega^{5} & \omega^{2} & \omega^{7} & \omega^{4} & \omega & \omega^{6} & \omega^{3}\\ 1 & \omega^{6} & \omega^{4} & \omega^{2} & 1 & \omega^{6} & \omega^{4} & \omega^{2}\\ 1 & \omega^{7} & \omega^{6} & \omega^{5} & \omega^{4} & \omega^{3} & \omega^{2} & \omega \end{bmatrix}

在代入 $\omega^4=-1$ 、 $\omega^5=-\omega$ 、 $\omega^6=-\omega^2$ 、 $\omega^7=-\omega^3$ 进行替换后，我们得到了最初的 Vandermonde 矩阵：

\mathbf{V} =\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & \omega & \omega^{2} & \omega^{3} & -1 & -\omega & -\omega^{2} & -\omega^{3} \\ 1 & \omega^{2} & -1 & -\omega^{2} & 1 & \omega^{2} & -1 & -\omega^{2} \\ 1 & \omega^{3} & -\omega^{2} & \omega & -1 & -\omega^{3} & \omega^{2} & -\omega \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ 1 & -\omega & \omega^{2} & -\omega^{3} & -1 & \omega & -\omega^{2} & \omega^{3} \\ 1 & -\omega^{2} & -1 & \omega^{2} & 1 & -\omega^{2} & -1 & \omega^{2} \\ 1 & -\omega^{3} & -\omega^{2} & -\omega & -1 & \omega^{3} & \omega^{2} & \omega \end{bmatrix}

练习： 在 8 次单位根上计算 $f(x)=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5+a_6x^6$ 。同样，请注意你可以设 $a_7=0$ 。

练习： 在 $\mathbb{F}_q$ （其中 $q=17$ ）的 4 次单位根上计算 $f(x)=3 +2x+9x^2+x^3$ 。使用 Python 寻找一个本原 4 次单位根作为起点。

在 4 次单位根上计算 f(x)=a0+a1x+a2x2+a3x3f(x)=a_0+a_1x+a_2x^2+a_3x^3

在 8 次单位根上计算 f(x)=a0+a1x+...+a7x7f(x)=a_0+a_1x+...+a_7x^7

Vandermonde 矩阵计算

总结