基于Rollup定理的多项式乘法等价性证明

在本系列的开篇，我们论证了若两个多项式均为点值形式，则次数不超过 (n) 的多项式乘法可以在 (\mathcal{O}(n)) 复杂度时间内完成。

实际困难在于，多项式通常以系数形式给出，而乘法的结果也要求是系数形式。

幸运的是，通过使用快速版本的 NTT 和 INTT，这些问题可以得到解决。

为了在 (\mathcal{O}(n \log n)) 时间内相乘两个系数形式的多项式，步骤如下：

• 使用 NTT 将多项式从系数形式转换为点值形式。
• 对点值形式的多项式进行逐点相乘。该步骤可在时间复杂度 (\mathcal{O}(n)) 内完成，结果得到点值形式。
• 使用 INTT 将结果多项式转换回系数形式。

利用 (n) 次单位根（其中 (n) 是 2 的幂），步骤 1 和步骤 3 可以在 (\mathcal{O}(n \log n)) 时间内完成。

唯一的限制是，我们需对结果多项式施加最大次数为 (n-1)。因此，待乘两个多项式的次数之和不能超过 (n-1)。

在实践中这通常不成问题，因为我们通常可以使用包含足够大 (n) 次单位根的域，使得多项式次数保持在允许范围内。

次数小于 (n-1) 的多项式不会带来问题，因为它们可以通过在高次项补零扩充到次数 (n-1)。

若不使用快速 NTT 和 INTT，多项式乘法的时间复杂度将是 (\mathcal{O}(n^2))。

本章的目的在于证明我们的论断。我们将展示，将两个系数形式的多项式相乘等价于：对每个多项式应用 NTT，进行逐点相乘，然后对由此运算得到的多项式应用 INTT。

这一结果在多项式乘法中被称为Rollup定理。在更一般的语境下，Rollup定理表述为：

“原始域中的Rollup等价于变换域中的逐点相乘。”

为了正确理解这一定理，我们需要从Rollup的定义开始。

对数学不太感兴趣的读者可以跳过本章，这不会影响后续阅读。在接下来的内容中，我们将证明Rollup定理，但若读者只关心其应用，则只需接受它能够用于在 (\mathcal{O}(n \log n)) 时间复杂度内完成多项式乘法（而非 (\mathcal{O}(n^2))）即可。

Rollup

两个系数形式多项式的乘法是Rollup操作的一个实例。

考虑两个二次多项式，

$$f(x) = a_0 + a_1x + a_2 x^2$$

和

$$g(x) = b_0 + b_1 x + b_2 x^2.$$

在系数形式下相乘得到多项式

$$ \begin{aligned} h(x) = f(x)g(x) &= a_0b_0 + a_0b_1 x+a_0b_2x^2 + \ &\quad + a_1b_0x + a_1b_1x^2 + a_1b_2x^3 \ &\quad + a_2 b_0 x^2 + a_2 b_1 x^3 + a_2b_2x^4. \end{aligned} $$

重新整理后得到

$$ \begin{aligned} h(x) = f(x)g(x) &= a_0b_0 \ &\quad + (a_0 b_1 + a_1b_0)x \ &\quad + (a_0 b_2 + a_1 b_1 + a_2 b_0) x^2 \ &\quad + (a_1 b_2 + a_2 b_1) x^3 \ &\quad + a_2 b_2 x^4. \end{aligned} $$

因此，(f(x)) 和 (g(x)) 相乘所得多项式的系数为

$$ \begin{aligned} c_0 &= a_0b_0, \ c_1 &= a_0 b_1 + a_1b_0, \ c_2 &= a_0 b_2 + a_1 b_1 + a_2 b_0, \ c_3 &= a_1 b_2 + a_2 b_1, \ c_4 &= a_2 b_2. \end{aligned} $$

这些系数可以简洁地表示为公式

$$c_k = \sum_{i=0}^{k} a_i b_{k-i}$$

其中 (k=0,1,2,3,4) 对应多项式 (h(x)) 的次数。让我们考察其中一个系数 (c_3)。对于该系数，我们有

$$c_3 = \sum_{i=0}^{3} a_i b_{3-i} = a_0 b_3 + a_1 b_2 + a_2 b_1 + a_3 b_0.$$

由于 (a_3) 和 (b_3) 均为零（因为多项式 (f(x)) 和 (g(x)) 是二次的），上式化简为

$$c_3 = a_1 b_2 + a_2 b_1,$$

与预期一致。

由

$$c_k = \sum_{i=0}^{k} a_i b_{k-i}$$

定义的操作称为Rollup，通常写作

$$c_k = (a \ast b)_k,$$

其中 (\ast) 表示Rollup算子。

Rollup定理

我们的目标是证明：将 (f(x)) 和 (g(x)) 转换为点值形式、对应点相乘、再将结果转换回系数形式，等价于对 (f(x)) 和 (g(x)) 的系数执行Rollup。

考虑多项式

$$f(x)=a_0 + a_1x+a_2x^2 + \ldots +a_px^p$$

和

$$g(x)=b_0 + b_1x+b_2x^2 + \ldots +b_qx^q$$

其次数分别为 (p) 和 (q)。

将 (f(x)) 和 (g(x)) 相乘得到一个新多项式 (h(x))，其次数为 (f(x)) 和 (g(x)) 的次数 (p) 与 (q) 的和。

假设 (h(x)) 的次数为 (n-1)。

因此，我们要计算

$$h(x) = f(x)g(x) = c_0 + c_1 x + c_2 x^2 + \ldots + c_{n-1} x^{n-1}$$

若次数小于 (n-1)，我们可以用零补齐高次项的系数。

将多项式 (f(x)) 和 (g(x)) 的系数表示为

$$ \begin{aligned} [a_0, a_1, a_2, \ldots, a_{n-1}], \ [b_0, b_1, b_2, \ldots, b_{n-1}]. \end{aligned} $$

上述表示中部分高次系数为零，因为 (f(x)) 和 (g(x)) 的次数之和最多为 (n-1)。这不成问题。我们唯一的限制是

$$\deg(f)+\deg(g)=\deg(h) \le n-1.$$

第一步是将多项式 (f(x)) 和 (g(x)) 从系数形式转换为点值形式。

第一步：将多项式转换为点值形式。

为了将这些多项式转换为点值形式，我们使用 NTT。通过选择 (n) 为 2 的幂，我们可以应用快速变换。然而，由于最终结果等价于乘以范德蒙矩阵，我们将给出矩阵表述。

例如，对于多项式 (f(x))，其在 (n) 次单位根处的取值为

$$ \begin{bmatrix} f(1) \ f(\omega) \ f(\omega^2) \ \vdots \ f(\omega^{n-1}) \end{bmatrix} = \begin{bmatrix}1 & 1 & 1 & \cdots & 1 \1 & \omega & \omega^{2} & \cdots & \omega^{n-1} \1 & \omega^{2} & \omega^{4} & \cdots & \omega^{2(n-1)} \\vdots & \vdots & \vdots & \ddots & \vdots \1 & \omega^{n-1} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)(n-1)}\end{bmatrix} \begin{bmatrix} a_0 \ a_1 \ a_2\ \vdots \ a_{n-1} \end{bmatrix}. $$

类似地，对于 (g(x))，

$$ \begin{bmatrix} g(1) \ g(\omega) \ g(\omega^2) \ \vdots \ g(\omega^{n-1}) \end{bmatrix} = \begin{bmatrix}1 & 1 & 1 & \cdots & 1 \1 & \omega & \omega^{2} & \cdots & \omega^{n-1} \1 & \omega^{2} & \omega^{4} & \cdots & \omega^{2(n-1)} \\vdots & \vdots & \vdots & \ddots & \vdots \1 & \omega^{n-1} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)(n-1)}\end{bmatrix} \begin{bmatrix} b_0 \ b_1 \ b_2\ \vdots \ b_{n-1} \end{bmatrix}. $$

这些矩阵运算可以以分量形式写作

$$f(\omega^i) = \sum_{r=0}^{n-1} a_r \omega^{ri}$$

和

$$g(\omega^i) = \sum_{s=0}^{n-1} b_s \omega^{si}.$$

例如，(f(\omega^2)) 的求值为

$$f(\omega^2) = \sum_{r=0}^{n-1} a_r \omega^{r2} = a_0 \omega^{0 \cdot 2} + a_1 \omega^{1 \cdot 2} + a_2 \omega^{2 \cdot 2} + \ldots + a_{n-1} \omega^{(n-1) \cdot 2}$$

第二步：对点值形式的多项式进行逐点相乘。

现在我们逐点相乘 (f(x)) 和 (g(x)) 的求值结果，得到乘积多项式 (h(x)) 的求值结果：

$$ \begin{aligned} h(\omega^0)&= f(\omega^0)g(\omega^0) \ h(\omega^1)&= f(\omega^1)g(\omega^1) \ &\vdots \ h(\omega^{n-1})&= f(\omega^{n-1})g(\omega^{n-1}) \end{aligned} $$

用下标表示，即为

$$h(\omega^i) = f(\omega^i) g(\omega^i).$$

利用上一步得到的 (f(\omega^i)) 和 (g(\omega^i)) 表达式，我们得到

$$h(\omega^i) = \left(\sum_{r=0}^{n-1} a_r \omega^{ri} \right) \left( \sum_{s=0}^{n-1} b_s \omega^{si}\right).$$

回顾一下，我们想要证明的是：如果对点值形式的多项式 (h(x))（即上述形式）执行 INTT，结果与对 (f(x)) 和 (g(x)) 执行Rollup相同。

最后一步：对点值形式的 (h(x)) 应用 INTT

在 (n) 次单位根上执行的逆数论变换使用范德蒙矩阵 (V(\omega^{-1})) 乘以因子 (\frac{1}{n})。

因此，对点集 (h(\omega^i)) 应用 INTT，我们得到系数形式的多项式 (h(x))：

$$ \begin{bmatrix} c_0 \ c_1 \ c_2\ \vdots \ c_{n-1} \end{bmatrix} = \frac{1}{n}\begin{bmatrix}1 & 1 & 1 & \cdots & 1 \1 & \omega^{-1} & \omega^{-2} & \cdots & \omega^{-(n-1)} \1 & \omega^{-2} & \omega^{-4} & \cdots & \omega^{-2(n-1)} \\vdots & \vdots & \vdots & \ddots & \vdots \1 & \omega^{-(n-1)} & \omega^{-2(n-1)} & \cdots & \omega^{-(n-1)(n-1)}\end{bmatrix} \begin{bmatrix} h(\omega^0) \ h(\omega^1) \ h(\omega^2) \ \vdots \ h(\omega^{n-1}) \end{bmatrix} $$

这可以以分量形式写作

$$c_p = \frac{1}{n} \sum_{i=0}^{n-1} h(\omega^i) \omega^{-ip}.$$

利用 (h(\omega^i)) 由

$$h(\omega^i) = \left(\sum_{r=0}^{n-1} a_r \omega^{ri} \right) \left( \sum_{s=0}^{n-1} b_s \omega^{si} \right)$$

给出，我们有

$$c_p = \frac{1}{n} \sum_{i=0}^{n-1} \underbrace{\left(\sum_{r=0}^{n-1} a_r \omega^{ri} \right) \left( \sum_{s=0}^{n-1} b_s \omega^{si} \right)}_{h(\omega^i)} \omega^{-ip}.$$

这个表达式看起来很庞大，但可以利用单位根的正交性来简化。

首先，我们将所有 (\omega) 的幂次合并：

$$ \begin{aligned} c_p &= \frac{1}{n} \sum_{i=0}^{n-1} \left(\sum_{r=0}^{n-1} a_r \omega^{ri} \right) \left( \sum_{s=0}^{n-1} b_s \omega^{si} \right) \omega^{-ip} && \text{\small 上述得到的表达式} \ &= \frac{1}{n} \sum_{i=0}^{n-1} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s),\omega^{ri},\omega^{si},\omega^{-ip} && \text{\small 合并求和与项} \ &= \frac{1}{n} \sum_{i=0}^{n-1} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s),\omega^{i(r+s-p)} && \text{\small 合并 }\omega^i\text{ 的指数} \ &= \frac{1}{n} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s) \left( \sum_{i=0}^{n-1} \omega^{i(r+s-p)} \right) && \text{\small 分离单位根求和}. \end{aligned} $$

上述表达式表明我们可以利用单位根的正交性来简化它。

回忆单位根的正交性公式：

$$\sum_{i=0}^{n-1} (\omega^{i})^{r-s}=\begin{cases}n, & \text{如果 } r\equiv s \pmod{n},\[6pt]0, & \text{否则}.\end{cases}$$

将上述公式应用于 (c_p) 中分离出的单位根求和，我们注意到

$$\sum_{i=0}^{n-1} \omega^{i(r+s-p)}$$

当 (s = p-r \pmod{n})（或等价地 (r = p-s \pmod{n})）时等于 (n)，否则为零。

这可以表示为 (n) 乘以克罗内克 delta：

$$\sum_{i=0}^{n-1} \omega^{i(r+s-p)} = n \delta_{s,p-r}$$

将

$$\sum_{i=0}^{n-1} \omega^{i(r+s-p)}$$

代入 (c_p) 的表达式，我们有

$$c_p = \frac{1}{n} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s)(n \delta_{s, p-r})$$

常数 (\frac{1}{n}) 和 (n) 相互抵消：

$$c_p = \frac{1}{\cancel{n}} \sum_{r=0}^{n-1} \sum_{s=0}^{n-1} (a_r b_s)(\cancel{n} \delta_{s, p-r})$$

更重要的是，在对索引 (s) 求和时，除了 (s = p-r) 的情况外，所有项都为零。这是由单位根的正交性所致。

因此，对 (s) 的求和坍缩了，我们可以将对 (b_s) 的求和替换为单一元素 (b_{p-r})。我们得到

$$c_p = \sum_{r=0}^{n-1} a_r b_{p-r}$$

这正是Rollup公式！

让我们回顾一下我们所做的：

1. 我们对多项式 (f(x)) 和 (g(x)) 应用了 NTT，将它们的系数表示转换为点值表示，即包含它们在 (n) 次单位根处的求值的向量：

$$\big(f(1), f(\omega), \ldots, f(\omega^{n-1})\big)\quad \text{和} \quad\big(g(1), g(\omega), \ldots, g(\omega^{n-1})\big)$$

2. 我们对这些求值结果进行了逐点相乘，即对于每个单位根 (\omega^i) 计算

$$h(\omega^i)=f(\omega^i)g(\omega^i)$$

得到了乘积多项式 (h(x)) 的点值表示。

3. 我们对此向量

$$\big(h(1), h(\omega), \ldots, h(\omega^{n-1})\big)$$

应用了 INTT，以恢复 (h(x)) 的系数表示。

我们证明了这三个步骤产生的结果与直接相乘多项式 (f(x)) 和 (g(x)) 完全相同，即对 (f(x)) 和 (g(x)) 的系数进行Rollup。

然而，直接Rollup的时间复杂度为 (\mathcal{O}(n^2))，而上述过程可以在 (\mathcal{O}(n \log n)) 时间内执行，并得到相同的最终多项式。

这正是Rollup定理所阐述的内容。更正式地，我们可以将其写作如下形式：

设 (f) 和 (g) 为两个系数形式的多项式。设 (*) 表示Rollup运算，(\cdot) 表示乘法。

设 (\mathcal{F}(f)) 表示对 (f) 应用 NTT——即 (f) 是系数向量，(\mathcal{F}(f)) 是求值向量；(\mathcal{F}^{-1}(\mathcal{F}(f))) 表示对 (\mathcal{F}(f)) 应用 INTT。那么，

$$f*g =\mathcal{F}^{-1}(\mathcal{F}(f)\cdot\mathcal{F}(g)).$$

Rollup定理的另一种表述是

$$\mathcal{F}(f*g) =\mathcal{F}(f)\cdot\mathcal{F}(g).$$

这是一个线性变换，可以理解如下：系数域中的Rollup等价于点值域中的逐点相乘。

本文是我们在零知识书中关于数论变换的系列文章之一

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