手动计算INTT算法

RareSkills 零知识入门书

手工进行 INTT 算法

模块 5：数论变换（NTT）—— 有限域中的快速傅里叶变换

如前一篇文章所述，逆数论变换（INTT） 与 NTT 一样，使用范德蒙矩阵进行计算。这表明通过 NTT 进行求值以及通过 INTT 进行插值是类似的操作。

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

NTT 的快速方法在“手工进行 NTT 算法”一章中介绍。本章我们研究 INTT 的快速方法。

思路很简单：将多项式插值解释为求值，从而可以使用与 NTT 相同的方法。

求值与插值

回顾一下，NTT 允许我们将一个最高次数为 $k-1$ 的多项式从其系数形式

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

转换为其点值形式

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

通过在 $k$ 次单位根处求值。这称为求值。

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

插值即求值

在 $k$ 次单位根处的求值和插值是类似的操作，因为两者都使用范德蒙矩阵进行。

为了更好地说明，考虑一个最高次数为 $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)$ 在以下点处的求值结果：

$$ \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}) = \tilde{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 算法一章中解释的快速方法在 $k$ 次单位根处求值。

$\tilde{f}(x)$ 在点 $\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} $$

让我们确认一下这与从范德蒙矩阵得到的结果一致：

$$ \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$ 的多项式所做的可以推广到任意次数的多项式。

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

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

为了恢复经过这些点的多项式 $f(x)$（最高次数为 $k-1$）的系数，我们定义一个新多项式 $\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} $$

本文是我们在零知识入门书中关于数论变换系列文章的一部分。

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