手算 INTT 算法

Last updated on May 5, 2026

正如上一篇文章中所见，Inverse Number Theoretic Transform (INTT) 与 NTT 一样，都是使用 Vandermonde 矩阵来执行的。这表明通过 NTT 进行的求值（evaluation）和通过 INTT 进行的插值（interpolation）是相似的操作。

直接使用 Vandermonde 矩阵进行求值或插值的问题在于，将一个 $k \times k$ 矩阵与一个向量相乘需要 $\mathcal{O}(k^2)$ 的时间。幸运的是，当使用 $k$ 次单位根（且 $k$ 是 2 的幂）时，可以使用一种不依赖于矩阵乘法的快速方法，将时间复杂度降低到 $\mathcal{O}(k \log k)$ 。

NTT 的快速方法已在“NTT Algorithm by Hand.”一章中介绍过。在本章中，我们将研究 INTT 的快速方法。

其思想很简单：将多项式插值解释为一种求值过程，从而允许使用与 NTT 相同的方法。

求值与插值

简而言之，NTT 允许我们将一个最高次数为 $k-1$ 的多项式从其系数形式（coefficient form）：

\begin{bmatrix}a_0 \\ a_1 \\ ... \\ a_{k-1} \end{bmatrix}

转换为点值形式（point-value form）：

\begin{bmatrix} f(\omega^0) \\ f(\omega^1) \\ ... \\ f(\omega^{k-1}) \end{bmatrix}

这是通过在 $k$ 次单位根处对多项式进行求值来实现的。这被称为求值（evaluation）。

插值（Interpolation）是求值的逆过程：它是将多项式从其点值形式转换为系数形式的过程。

将插值视为求值

在 $k$ 次单位根处的求值和插值是相似的操作，因为它们都是使用 Vandermonde 矩阵执行的。

为了更直观地理解，考虑一个最高次数为 3 的多项式，

f(x) = a + bx + cx^2 + dx^3,

在 $4$ 次单位根处进行求值：

f(1), f(\omega), f(\omega^{2}),f(\omega^{3}).

求值过程可以写成：

\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 \\b \\c \\d\end{bmatrix}.\end{aligned}

插值过程可以写成：

\begin{aligned} \begin{bmatrix}a \\ b \\ c \\ d \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}

受求值结构的启发，我们可以将 $\frac{f(1)}{4}, \frac{f(\omega)}{4}, \frac{f(\omega^2)}{4}$ 和 $\frac{f(\omega^3)}{4}$ 视为一个新多项式 $\tilde{f}(x)$ 的系数，定义为：

\tilde{f}(x) = \frac{1}{4}\big(f(1) + f(\omega)x + f(\omega^2) x^2 + f(\omega^3) x^3\big).

按照这种说法，系数 $a,b,c$ 和 $d$ 即是 $\tilde{f}(x)$ 在以下点的求值：

\begin{aligned} a &= \tilde{f}(1) \\ b &= \tilde{f}(\omega^{-1}) \\ c &= \tilde{f}(\omega^{-2}) \\ d &= \tilde{f}(\omega^{-3}) \\ \end{aligned}

因此，我们可以将插值解释为另一个多项式的求值。关键的观察在于，逆 NTT 并不需要一种本质上不同的算法。

一旦将点值表示重新解释为一个新多项式的系数向量，插值就变成了在一组经过排列的单位根上的求值。从这个意义上说，求值和插值是相同的操作。

避免处理单位根的逆元

正如在以下变换中所见：

\begin{aligned} \begin{bmatrix}a \\ b \\ c \\ d \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}

插值涉及在单位根的逆元处进行求值。然而，我们可以避免直接处理这些逆元。

考虑 $\omega^{-1}$ 。在 $4$ 次单位根中，它是与 $\omega$ 相乘结果为 1 的元素。由于：

\omega \cdot \omega^3 = \omega^4 \equiv 1,

我们有 $\omega^{-1} = \omega^3$ 。

同理，

\begin{aligned} \omega^{-2} &= \omega^2, \\ \omega^{-3} &= \omega. \end{aligned}

因此，系数 $a,b,c$ 和 $d$ 也就是：

\tilde{f}(x) = \frac{1}{4}\big(f(1) + f(\omega)x + f(\omega^2) x^2 + f(\omega^3) x^3\big)

在以下各点的求值：

\begin{aligned} a &= \tilde{f}(1), \\ b &= \tilde{f}(\omega^{-1}) = \tilde{f}(\omega^{3}), \\ c &= \tilde{f}(\omega^{-2}) = \tilde{f}(\omega^{2}), \\ d &= \tilde{f}(\omega^{-3}) = f(\omega). \\ \end{aligned}

利用 $\omega^2 = -1$ 这一性质，我们可以将它们重写为：

\begin{aligned} a &= \tilde{f}(1), \\ b &= \tilde{f}(\omega^{3}) = \tilde{f}(-\omega), \\ c &= \tilde{f}(\omega^{2}) = \tilde{f}(-1), \\ d &= \tilde{f}(\omega^{}). \\ \end{aligned}

手动推导 INTT

对于最高次数为 $k-1$ 的多项式（其中 $k$ 是 2 的幂），可以使用在 NTT Algorithm by Hand. 一章中解释的快速方法，在 $k$ 次单位根处对其进行求值。

关于

\tilde{f}(x) = \frac{1}{4}\big(f(1) + f(\omega)x + f(\omega^2) x^2 + f(\omega^3) x^3\big)

在 $\tilde{f}(1), \tilde{f}(-1), \tilde{f}(\omega)$ 和 $\tilde{f}(-\omega)$ 处的求值过程如下图所示。

核心思路是将偶数次幂和奇数次幂进行分组，如下所示：

\tilde{f}(x) = \frac{1}{4}\big(f(1) + f(\omega^2) x^2) + x(f(\omega) + f(\omega^3) x^2)\big),

并在 $\sqrt{\sqrt{1}}$ 处对 $\tilde{f}(x)$ 进行求值。在每一次计算最内层平方根时，表达式都会分支成两个，分别对应平方根的两个值。这一过程会持续进行，直到没有剩余的平方根为止，此时该过程结束。

我们得到：

\begin{aligned} a&= \tilde{f}(1) = \frac{1}{4}\big( f(1)+f(\omega)+ f(\omega^2)+f(\omega^3)\big), \\ b&= \tilde{f}(-\omega) = \frac{1}{4}\big( f(1)-f(\omega^2) - \omega( f(\omega)-f(\omega^3))\big), \\ c&= \tilde{f}(-1) = \frac{1}{4}\big( f(1)+f(\omega^2) - ( f(\omega)+f(\omega^3))\big), \\ d&= \tilde{f}(\omega) = \frac{1}{4}\big( f(1)-f(\omega^2) + \omega( f(\omega)-f(\omega^3))\big). \\\end{aligned}

让我们确认这是否与从 Vandermonde 矩阵获得的结果一致：

\begin{aligned} \begin{bmatrix}a \\ b \\ c \\ d \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}

利用：

\begin{aligned} \omega^{-1} &= \omega^3 = - \omega, \\ \omega^{-2} &= \omega^2 = -1, \\ \omega^{-3} &= \omega, \end{aligned}

我们将其重写为：

\begin{aligned} \begin{bmatrix}a \\ b \\ c \\ d \end{bmatrix}= \frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\1 & - \omega & -1 & \omega \\1 & -1 & 1 & -1 \\1 & \omega & -1 & -\omega\end{bmatrix}\begin{bmatrix}f(1) \\f(\omega) \\ f(\omega^2) \\f(\omega^3)\end{bmatrix}. \end{aligned}

进而得出：

\begin{alignat*}{3} a &= \tilde{f}(1) &\;=\;& \frac{1}{4}\big( f(1)+f(\omega)+ f(\omega^2)+f(\omega^3)\big), \\ b &= \tilde{f}(-\omega) &\;=\;& \frac{1}{4}\big( f(1)-f(\omega^2) - \omega( f(\omega)-f(\omega^3))\big), \\ c &= \tilde{f}(-1) &\;=\;& \frac{1}{4}\big( f(1)+f(\omega^2) - ( f(\omega)+f(\omega^3))\big), \\ d &= \tilde{f}(\omega) &\;=\;& \frac{1}{4}\big( f(1)-f(\omega^2) + \omega( f(\omega)-f(\omega^3))\big). \end{alignat*}

这与快速算法所得出的表达式完全相同。

关键的区别在于，快速算法在 $\mathcal{O}(k \log k)$ 的时间内运行，而直接进行矩阵乘法需要 $\mathcal{O}(k^2)$ 的时间。

$k-1$ 次多项式

我们在上一节中针对 $3$ 次多项式所做的推导，可以推广到任意次数的多项式。

假设我们有一个在 $k$ 次单位根处求值的多项式 $f(x)$ ，其中 $k$ 是 $2$ 的幂：

f(\omega^0), f(\omega^1), f(\omega^2), ..., f(\omega^{k-1})

为了恢复经过这些点且最高次数为 $k-1$ 的多项式 $f(x)$ 的系数，我们定义一个新多项式 $\tilde{f}(x)$ 如下：

\tilde{f}(x) = \frac{1}{k}\big(f(1) + f(\omega)x + f(\omega^2) x^2 + ...+ f(\omega^{k-1}) x^{k-1}\big)

那么 $f(x)$ 的系数就可以表示为：

\begin{aligned} a_0 &= \tilde{f}(\omega^0) \\ a_1 &= \tilde{f}(\omega^{-1}) = \tilde{f}(\omega^{k-1}) \\ a_2 &= \tilde{f}(\omega^{-2}) = \tilde{f}(\omega^{k-2}) \\ ... \\ a_{k-1} &= \tilde{f}(\omega^{-(k-1)}) = \tilde{f}(\omega^{1}) \\ \end{aligned}

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

Last updated on May 5, 2026

NTT 的快速方法已在“NTT Algorithm by Hand.”一章中介绍过。在本章中，我们将研究 INTT 的快速方法。

其思想很简单：将多项式插值解释为一种求值过程，从而允许使用与 NTT 相同的方法。

求值与插值

简而言之，NTT 允许我们将一个最高次数为 $k-1$ 的多项式从其系数形式（coefficient form）：

\begin{bmatrix}a_0 \\ a_1 \\ ... \\ a_{k-1} \end{bmatrix}

转换为点值形式（point-value form）：

\begin{bmatrix} f(\omega^0) \\ f(\omega^1) \\ ... \\ f(\omega^{k-1}) \end{bmatrix}

这是通过在 $k$ 次单位根处对多项式进行求值来实现的。这被称为求值（evaluation）。

插值（Interpolation）是求值的逆过程：它是将多项式从其点值形式转换为系数形式的过程。

将插值视为求值

在 $k$ 次单位根处的求值和插值是相似的操作，因为它们都是使用 Vandermonde 矩阵执行的。

为了更直观地理解，考虑一个最高次数为 3 的多项式，

f(x) = a + bx + cx^2 + dx^3,

在 $4$ 次单位根处进行求值：

f(1), f(\omega), f(\omega^{2}),f(\omega^{3}).

求值过程可以写成：

\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 \\b \\c \\d\end{bmatrix}.\end{aligned}

插值过程可以写成：

\begin{aligned} \begin{bmatrix}a \\ b \\ c \\ d \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}

受求值结构的启发，我们可以将 $\frac{f(1)}{4}, \frac{f(\omega)}{4}, \frac{f(\omega^2)}{4}$ 和 $\frac{f(\omega^3)}{4}$ 视为一个新多项式 $\tilde{f}(x)$ 的系数，定义为：

\tilde{f}(x) = \frac{1}{4}\big(f(1) + f(\omega)x + f(\omega^2) x^2 + f(\omega^3) x^3\big).

按照这种说法，系数 $a,b,c$ 和 $d$ 即是 $\tilde{f}(x)$ 在以下点的求值：

\begin{aligned} a &= \tilde{f}(1) \\ b &= \tilde{f}(\omega^{-1}) \\ c &= \tilde{f}(\omega^{-2}) \\ d &= \tilde{f}(\omega^{-3}) \\ \end{aligned}

因此，我们可以将插值解释为另一个多项式的求值。关键的观察在于，逆 NTT 并不需要一种本质上不同的算法。

一旦将点值表示重新解释为一个新多项式的系数向量，插值就变成了在一组经过排列的单位根上的求值。从这个意义上说，求值和插值是相同的操作。

避免处理单位根的逆元

正如在以下变换中所见：

\begin{aligned} \begin{bmatrix}a \\ b \\ c \\ d \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}

插值涉及在单位根的逆元处进行求值。然而，我们可以避免直接处理这些逆元。

考虑 $\omega^{-1}$ 。在 $4$ 次单位根中，它是与 $\omega$ 相乘结果为 1 的元素。由于：

\omega \cdot \omega^3 = \omega^4 \equiv 1,

我们有 $\omega^{-1} = \omega^3$ 。

同理，

\begin{aligned} \omega^{-2} &= \omega^2, \\ \omega^{-3} &= \omega. \end{aligned}

因此，系数 $a,b,c$ 和 $d$ 也就是：

\tilde{f}(x) = \frac{1}{4}\big(f(1) + f(\omega)x + f(\omega^2) x^2 + f(\omega^3) x^3\big)

在以下各点的求值：

\begin{aligned} a &= \tilde{f}(1), \\ b &= \tilde{f}(\omega^{-1}) = \tilde{f}(\omega^{3}), \\ c &= \tilde{f}(\omega^{-2}) = \tilde{f}(\omega^{2}), \\ d &= \tilde{f}(\omega^{-3}) = f(\omega). \\ \end{aligned}

利用 $\omega^2 = -1$ 这一性质，我们可以将它们重写为：

\begin{aligned} a &= \tilde{f}(1), \\ b &= \tilde{f}(\omega^{3}) = \tilde{f}(-\omega), \\ c &= \tilde{f}(\omega^{2}) = \tilde{f}(-1), \\ d &= \tilde{f}(\omega^{}). \\ \end{aligned}

手动推导 INTT

对于最高次数为 $k-1$ 的多项式（其中 $k$ 是 2 的幂），可以使用在 NTT Algorithm by Hand. 一章中解释的快速方法，在 $k$ 次单位根处对其进行求值。

关于

\tilde{f}(x) = \frac{1}{4}\big(f(1) + f(\omega)x + f(\omega^2) x^2 + f(\omega^3) x^3\big)

在 $\tilde{f}(1), \tilde{f}(-1), \tilde{f}(\omega)$ 和 $\tilde{f}(-\omega)$ 处的求值过程如下图所示。

核心思路是将偶数次幂和奇数次幂进行分组，如下所示：

\tilde{f}(x) = \frac{1}{4}\big(f(1) + f(\omega^2) x^2) + x(f(\omega) + f(\omega^3) x^2)\big),

我们得到：

\begin{aligned} a&= \tilde{f}(1) = \frac{1}{4}\big( f(1)+f(\omega)+ f(\omega^2)+f(\omega^3)\big), \\ b&= \tilde{f}(-\omega) = \frac{1}{4}\big( f(1)-f(\omega^2) - \omega( f(\omega)-f(\omega^3))\big), \\ c&= \tilde{f}(-1) = \frac{1}{4}\big( f(1)+f(\omega^2) - ( f(\omega)+f(\omega^3))\big), \\ d&= \tilde{f}(\omega) = \frac{1}{4}\big( f(1)-f(\omega^2) + \omega( f(\omega)-f(\omega^3))\big). \\\end{aligned}

让我们确认这是否与从 Vandermonde 矩阵获得的结果一致：

\begin{aligned} \begin{bmatrix}a \\ b \\ c \\ d \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}

利用：

\begin{aligned} \omega^{-1} &= \omega^3 = - \omega, \\ \omega^{-2} &= \omega^2 = -1, \\ \omega^{-3} &= \omega, \end{aligned}

我们将其重写为：

\begin{aligned} \begin{bmatrix}a \\ b \\ c \\ d \end{bmatrix}= \frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\1 & - \omega & -1 & \omega \\1 & -1 & 1 & -1 \\1 & \omega & -1 & -\omega\end{bmatrix}\begin{bmatrix}f(1) \\f(\omega) \\ f(\omega^2) \\f(\omega^3)\end{bmatrix}. \end{aligned}

进而得出：

\begin{alignat*}{3} a &= \tilde{f}(1) &\;=\;& \frac{1}{4}\big( f(1)+f(\omega)+ f(\omega^2)+f(\omega^3)\big), \\ b &= \tilde{f}(-\omega) &\;=\;& \frac{1}{4}\big( f(1)-f(\omega^2) - \omega( f(\omega)-f(\omega^3))\big), \\ c &= \tilde{f}(-1) &\;=\;& \frac{1}{4}\big( f(1)+f(\omega^2) - ( f(\omega)+f(\omega^3))\big), \\ d &= \tilde{f}(\omega) &\;=\;& \frac{1}{4}\big( f(1)-f(\omega^2) + \omega( f(\omega)-f(\omega^3))\big). \end{alignat*}

这与快速算法所得出的表达式完全相同。

关键的区别在于，快速算法在 $\mathcal{O}(k \log k)$ 的时间内运行，而直接进行矩阵乘法需要 $\mathcal{O}(k^2)$ 的时间。

$k-1$ 次多项式

我们在上一节中针对 $3$ 次多项式所做的推导，可以推广到任意次数的多项式。

假设我们有一个在 $k$ 次单位根处求值的多项式 $f(x)$ ，其中 $k$ 是 $2$ 的幂：

f(\omega^0), f(\omega^1), f(\omega^2), ..., f(\omega^{k-1})

为了恢复经过这些点且最高次数为 $k-1$ 的多项式 $f(x)$ 的系数，我们定义一个新多项式 $\tilde{f}(x)$ 如下：

\tilde{f}(x) = \frac{1}{k}\big(f(1) + f(\omega)x + f(\omega^2) x^2 + ...+ f(\omega^{k-1}) x^{k-1}\big)

那么 $f(x)$ 的系数就可以表示为：

\begin{aligned} a_0 &= \tilde{f}(\omega^0) \\ a_1 &= \tilde{f}(\omega^{-1}) = \tilde{f}(\omega^{k-1}) \\ a_2 &= \tilde{f}(\omega^{-2}) = \tilde{f}(\omega^{k-2}) \\ ... \\ a_{k-1} &= \tilde{f}(\omega^{-(k-1)}) = \tilde{f}(\omega^{1}) \\ \end{aligned}

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

求值与插值

将插值视为求值

避免处理单位根的逆元

手动推导 INTT

k−1k-1k−1 次多项式