多项式乘法广泛应用于零知识证明和数学密码学中。但是，多项式乘法的暴力破解或传统方法的运行时间为 $\mathcal{O}(n^2)$，这对于小规模输入来说尚可接受，但随着多项式次数的增加，计算成本会变得相当高昂。本文将详细探讨多项式乘法，以探索提高其速度的方法。

• 首先，我们将回顾教科书上的/传统的多项式算术
• 接着，研究多项式的不同表示形式
• 探讨并比较这些不同形式下的多项式算术
• 最后，我们来看看这些形式如何潜在地加速多项式乘法——以及它们如何构成一种名为数论变换 (Number Theoretic Transform, NTT) 算法的基础

Polynomial Multiplication - Traditional approach

考虑两个次数均为 $n$ 的多项式 $p_1(x)$ 和 $p_2(x)$：

使用简单的乘法对加法分配律的方法来乘以这两个多项式，需要花费 $\mathcal{O}(n^2)$ 的时间。在这里，$p_1(x)$ 的每一项都要与 $p_2(x)$ 的每一项相乘：

例如，
设 $p_1(x) = 1 + 2x$，
且 $p_2(x) = 3 + 4x$。

那么，

在编程时，这是通过嵌套循环的形式实现的。

Copy
# Let A be array representing the coefficients of p1(x)
A = [a0, a1, ..., an]
# Let B be array representing the coefficients of p2(x)
B = [b0, b1, ..., bn]
# Let C be the array storing coefficients of p1(x).p2(x)

function multiply_polynomials(A, B):
    n = len(A)
    m = len(B)
    C = array of zeros of length (n + m - 1)

    for i from 0 to n - 1:
        for j from 0 to m - 1:
            C[i + j] += A[i] * B[j]
    return C

你将得到如下结果：

对于外层循环的 $n$ 次迭代，内层循环会执行 n 次（假设次数相等 $m=n$），即 n 乘 n，因此运行时间为 $\mathcal{O}(n^2)$。

我们现在想看看是否可以对此进行优化并做得更好。或者简而言之，有没有办法让多项式乘法变得更快？

Ways to represent a Polynomial

我们可以通过两种方式来表示多项式：系数形式 (coefficient form) 和 点值形式 (point form)。

Coefficient Form

多项式通常以所谓的单项式基或系数形式表达，这意味着它被写成变量幂的线性组合。

例如，一个次数为 $n$ 的多项式，当表示为

时，是以单项式基表示的，因为它使用 $[1, x, x^2, …, x^n]$ 作为其系数的基础，其系数为 $a_0, a_1, a_2, .., a_x.$

在这种表示法中，$p(x)$ 的系数可以写成一个向量或数组，如 $[a_0, a_1, …, a_n]$，其中第一个元素对应于常数项或 $x^0$ 的系数，而最后一个元素对应于 $x^n$ 的系数。

你应该注意到，我们前面看到的使用分配律进行乘法计算的方法（运行时间 $\mathcal{O}(n^2)$）是应用于多项式的系数形式的。

Point (or Value) Form

点值形式（或值形式）的表示法基于这样一个事实：每个次数为 $n$ 的多项式都可以由位于其上的 $n+1$ 个不同点的集合来表示。

例如，考虑一个二次多项式（次数为 $2$）：

现在取出位于该曲线上的任意 $3$ 个点（因为 $n=2$），比如 $(0,1)$、$(1,0)$ 和 $(2,3)$。我们可以说这 $3$ 个点代表了给定的多项式。或者，如果仅仅给出这些点，我们也可以从这些信息中恢复出多项式 $2x^2 -3x+1$。为什么这样可行呢？或者说，我们为何能够用 $n+1$ 个点等价地表示一个次数为 $n$ 的多项式？

这是因为：

对于任意一组 $n+1$ 个不同的点，存在一个唯一的、次数最多为 $n$ 的最低次多项式，它穿过所有这些点。

这个最低次多项式被称为 Lagrange Polynomial。

例如，
给定两个点 $(1, 2)$ 和 $(3, 4)$，存在一个唯一的次数为 $1$ 的多项式（一条直线）穿过这些点：

类似地，
给定三个点 $(0, 1)$、$(1, 4)$ 和 $(2, 9)$，穿过这些点的次数为 $2$ 的 Lagrange Polynomial 为：

关于在给定一组点的情况下如何计算这个特殊多项式，这在有关Lagrange interpolation的这篇文章中有所讨论。

Uniqueness of the Lagrange Polynomial

你必须注意的是，对于一组点来说，存在多个给定次数的多项式可以穿过所有这些点。但只有最低次多项式是唯一的。

例如，在上述点 $(1, 2)$ 和 $(3, 4)$ 的例子中，存在许多穿过这两个点的多项式：$x^2 -3x +4$ 和 $2x^2 -7x +7$ 是穿过这两个点的众多 $2$ 次（二次）多项式中的两个。

同样地，如果考虑 $3$ 次多项式，穿过点 $(1,2)$ 和 $(3,4)$ 的两个示例如 $x^3 -5x^2 +8x-2$ 和 $-x^{3}+4x^{2}-2x+1$。

但对于最低次数，在这里是 $1$，只存在一个最低次多项式，即 $p(x) = 1 + x$。它是唯一的，没有其他 $1$ 次多项式能够穿过这两个给定的点。

How is this lowest degree determined?

对于每一组 $n+1$ 个不同的点，存在一个唯一的次数最多为 $n$ 的多项式穿过它们。如果其中有些点是共线的，或者位于更低次的多项式上，那么这个唯一多项式的次数将小于 $n$。因此，我们使用“最多为 $n$”这一术语来涵盖次数恰好为 $n$ 的情况，以及次数较低的情况。

例如，
给定点 $(1,2),(2,4),$ 和 $(3,6)$，穿过它们的最低次多项式是 $y=2x$。这是因为这些点是共线的，即它们位于同一条直线上。我们可以检查它们之间任意两点的斜率都是相同的：

因此，最低次数为 $1$，$y=2x$ 即是唯一的 Lagrange Polynomial。

类似地，
给定五个点 $(-2,1), (-1,0), (0,1), (1,4), (2,9)$，我们发现它们都位于一条抛物线上，其方程为

这种情况中所有给定点都位于一个较低次数的多项式上，这里是 $2$ 次多项式，因此 Lagrange Polynomial 的次数为 $2$，小于 $n$（在这里，$n=4$）。

有关最低次多项式唯一性的证明，请参考文末的附录。

Conversion Between Coefficient Form and Point Form

因为系数形式和点值形式是等价的，所以我们可以方便地在它们之间进行转换，如下所示。

Interpolation (Point Form → Coefficient Form)

从点值形式转换为系数形式的过程称为插值，即计算穿过所有给定点的最低次多项式。完成这项工作最著名的方法之一就是使用我们前面提到的Lagrange Interpolation。如果你对此不熟悉，可以阅读这篇文章。

简而言之，给定一组 $(n+1)$ 个不同的点

我们可以使用拉格朗日插值公式找到唯一一个次数最多为 $n$ 的最低次多项式 $p(x)$，使得：

你应该记住，拉格朗日插值的运行时间是 $\mathcal{O}(n^2)$。

Evaluation (Coefficient Form → Point Form)

从系数形式转换为点值形式的过程称为求值，即在特定的 $x$ 值处计算多项式的值以获得相应的 $y$ 值，从而得到一组代表该多项式的 $(x_i, y_i)$ 点。实现这一转换的一种常见方法是使用Horner’s rule（我们将在未来的文章中详细讨论）。

简而言之，给定多项式 $p(x)$ 的系数 $[a_0, a_1, \dots, a_n]$ 以及一个值 $x_i$，Horner’s Method 按如下方式计算 $p(x_i)$ 的值：

该方法逐个提取出 $x$ 的公次幂，直到处理完所有的项。让我们看一个例子以便更好地理解。

给定多项式 $p(x) = 2 + 3x + 5x^2 + x^3$ 和值 $x = 2$，我们将复习 Horner’s rule 是如何计算 $p(2)$ 的值的。

我们可以将 $p(x)$ 改写如下（如上文的一般表达式所示）：

代入 $x = 2$：

观察这些步骤是如何交替进行乘法和加法运算的。上述计算的步骤 1、3 和 5 是乘法，而步骤 2、4 和 6 是加法。总共有 $n$ 次乘法和 $n$ 次加法（这里 $n=3$），使得总运行时间为 $\mathcal{O}(n)$。这就是 Horner’s rule 如何在 $\mathcal{O}(n)$ 的时间内计算一个 $n$ 次多项式在给定 $x$ 值时的值。

因此，在 $n+1$ 个不同的 $x$ 值处对多项式进行求值（即使用此法则从系数形式转换为点值形式）需要进行 $n$ 乘 $n+1$ 次运算，也就是 $\mathcal{O}(n^2)$。

Coefficient form VS Point form

我们说过，多项式的系数形式和点值形式是等价的，并且两者可以相互转换。也就是说，在任一形式下进行加法和乘法运算，其最终结果是没有区别的。让我们先通过一个加法的例子来验证这一点。

Addition in coefficient form

考虑以系数形式给出的两个多项式，

或者它们各自的系数数组：

现在，将这两个多项式相加只需将这两个数组逐个元素相加即可，得到的系数数组就代表了最终的多项式。让我们验证一下：

或者简单地写成 $[(1+4), (2+0),(3+1)] = [5,\ 2,\ 4]$

对于两个次数为 $n$ 的多项式，我们执行 $n+1$ 次加法就能得到总和的表示。因此，在系数形式下加法的运行时间为 $\mathcal{O}(n)$。

Addition in point form

考虑相同的两个多项式，

首先，我们需要将它们从系数形式转换为点值形式。由于这两个多项式的次数都是 $2$，它们的和的次数也最多为 $2$。因此，我们需要三个点来表示该总和（次数加一：$n + 1$），这就要求对 $p_1(x)$ 和 $p_2(x)$ 各进行 $3$ 次求值。

让我们在 $x = 0, 1, 2$ 处对 $p_1(x)$ 和 $p_2(x)$ 进行求值以获得所需的点。

注：为了简单起见，我们只是选择了 $x=0,1,2$。你可以选择任何其他 $3$ 个点进行求值。

• $p_1(0) = 1, \quad p_1(1)= 6, \quad p_1(2)=17$
• $p_2(0) = 4, \quad p_2(1)= 5, \quad p_2(2)=8$

现在，相加这两个多项式要求将相应的求值结果逐个元素相加，即：

• $p_{\text{sum}}(0) = (1+4) =5$
• $p_{\text{sum}}(1) = (6+5) =11$
• $p_{\text{sum}}(2) = (17+8) =25$

这三个点 $(0, 5), (1, 11)$ 和 $(2, 25)$ 给出了总和的点值形式表示。让我们验证一下它们是否满足我们之前计算出的多项式：

• $p_{\text{sum}}(0) = 5$
• $p_{\text{sum}}(1) = 5 + 2 + 4 = 11$
• $p_{\text{sum}}(2) = 5 + 4 + 16 = 25$

因此，你可以看到两种形式的加法都会得到相同的结果，或者是相同的多项式，只是用不同的方式表示而已。

在点值形式的加法中，对于两个次数为 $n$ 的多项式，各自由 $n+1$ 个点代表，因此我们需要执行 $n+1$ 次逐个元素的加法操作来获得总和的代表点。因此，点值形式加法的运行时间为 $\mathcal{O}(n)$。

现在，让我们再来仔细看看乘法。

Multiplication in coefficient form

考虑以系数形式给出的两个多项式：

或者它们各自的系数数组：
$p_1 = [1,\ 2]$ 和 $p_2 = [3,\ 4]$

使用前面讨论过的分配律方法将它们相乘，得到：

结果多项式为 $p_{\text{prod}}(x) = 3 + 10x + 8x^2$，由系数数组 $[3,\ 10,\ 8]$ 表示。正如我们在本文开头所看到的，系数形式乘法的分配律方法需要 $\mathcal{O}(n^2)$ 的时间。

Multiplication in point form

我们现在考虑相同的多项式，并将它们转换为其点值形式。

因为两个多项式的次数均为 $1$，它们的乘积的次数最多为 $2$，这意味着我们需要 $3$ 个点来表示它，这就要求对 $p_1(x)$ 和 $p_2(x)$ 各进行 3 次求值。

因此，让我们在 $x = 0, 1, 2$ 处对 $p_1(x)$ 和 $p_2(x)$ 进行求值。

• $p_1(0) = 1,\quad p_1(1) = 3,\quad p_1(2) = 5$
• $p_2(0) = 3,\quad p_2(1) = 7,\quad p_2(2) = 11$

现在，为了得到代表它们乘积的点，我们将这些求值结果逐个元素相乘：

• $p_{\text{prod}}(0) = 1 \cdot 3 = 3$
• $p_{\text{prod}}(1) = 3 \cdot 7 = 21$
• $p_{\text{prod}}(2) = 5 \cdot 11 = 55$

所以这三个点 $(0, 3), (1, 21)$ 和 $(2, 55)$ 给出了所得乘积的点值表示。

让我们验证一下它们是否满足我们之前得到的多项式乘积：

• $p_{\text{prod}}(0) = 3$
• $p_{\text{prod}}(1) = 3 + 10 + 8 = 21$
• $p_{\text{prod}}(2) = 3 + 20 + 32 = 55$

因此，你可以看到这两种形式的乘法都会得到相同的多项式，只是表示方式不同而已。

总而言之，对于两个次数为 $n$ 的多项式 $p_1(x)$ 和 $p_2(x)$，它们的乘积次数最多为 $2n$，意味着我们需要 $2n+1$ 个点来表示它。因此，我们在公共的 $x$ 值处对每个多项式执行 $2n+1$ 次求值，以将它们转换为点值形式：

接着，我们通过将这两个集合逐个元素相乘来执行点值形式的乘法，这需要 $2n+1$ 次乘法，即运行时间为 $\mathcal{O}(n)$。

这样我们就能得到表示乘积 $p_1(x).p_2(x)$ 的 $2n+1$ 个点：

这里值得注意的是，虽然在系数形式和点值形式中，加法所花费的时间都是 $\mathcal{O}(n)$，但点值形式中的乘法要比系数形式快得多。在点值形式中，我们执行 $2n+1$ 次逐元素的乘法，得出 $\mathcal{O}(n)$ 的运行时间，这远好于系数形式乘法所需的 $\mathcal{O}(n^2)$！

然而，这里还有一个问题——我们尚未考虑转换到点值形式以及反向转换所带来的开销。

因此，让我们来看看点值形式乘法的完整过程，它包含三个步骤：

1. 从系数形式转换为点值形式
   我们在 $(2n+1)$ 个 $x$ 值处对两个要相乘的 $n$ 次多项式进行求值，以各自获得包含 $(2n+1)$ 个求值结果的集合。使用 Horner’s Method 需要花费 $\mathcal{O}(n^2)$ 的时间。
2. 在点值形式表示下进行逐元素乘法
   我们将这两个集合逐个元素相乘，得到 $(2n+1)$ 个求值结果，这就是其乘积的点值形式表示。这需要花费 $\mathcal{O}(n)$ 的时间。
3. 从点值形式转换为系数形式
   我们计算穿过所有生成的 $(2n+1)$ 个点的唯一最低次多项式（系数形式）。使用 Lagrange interpolation 需要花费 $\mathcal{O}(n^2)$ 的时间。

因此，上述步骤的整体运行时间为：

这并没有比我们一开始的起点更好。因此，我们需要探索是否有任何优化手段能让这个过程变得更快。

Optimizing conversion

需要记住的关键点是，系数形式的乘法需要 $\mathcal{O}(n^2)$，而点值形式（逐个元素）的乘法需要 $\mathcal{O}(n)$。因此，如果我们能找到一种快于 $\mathcal{O}(n^2)$ 的方法来实现系数形式与点值形式之间的相互转换（上述的步骤 1 和 3），我们就可以将乘法优化到在亚二次时间内运行。

重要的是要注意，我们不能优化多项式加法，因为系数形式和点值形式中的加法运行时间各为 $\mathcal{O}(n)$。

所以现在让我们进行头脑风暴，想出一些可能加快从系数形式转换为点值形式的方法。

如果我们知道有一个点，对其求值就能得到其他几个相关点的值，从而省去重复计算，那会怎样？

例如，如果我们有一个图形对称的多项式，那么计算一个点就能告诉我们其对应的对称点的求值结果。

考虑多项式 $p(x)= x^2$。
观察一下，

或者，更简单地说，观察对于所有的 $x_i$，

这不仅对 $p(x)=x^2$ 成立，而且可以推广到所有只包含偶数次幂系数的多项式，这些多项式也被称为偶多项式。

例如，考虑以下偶多项式（只包含带有 $x$ 的偶数次幂项）：

在上面的图表中，很容易观察到

从视觉上来说，偶多项式的图形是关于 $y$ 轴对称的，并且对于任何给定 $x$ 的正负值，它们都会计算出相同的 $y$ 值。

那么只包含奇数次幂系数的奇多项式又如何呢？
考虑 $p(x) = x^3$。
观察一下

在上面的图表中，观察对于所有的 $x_i$，

同样，这不仅适用于 $p(x)=x^3$，而且可以推广到所有奇多项式，即只包含 $x$ 的奇数次幂项的多项式。例如，考虑多项式

在上面的图表中，观察到

从视觉上看，所有奇多项式的图形都是关于原点对称的，这使得上述等式对它们都成立。

现在你可以看到，在计算了某些点的值之后，我们可以不用进行任何额外的计算就能得到其他点的值。例如，在上面的例子中，对于偶多项式和奇多项式，知道了 $p(x)$ 的求值结果也就得出了 $p(-x)$ 的求值结果。

我们可以利用这一事实来加快多项式乘法的速度，这正是通过一种名为数论变换 (Number Theoretic Transform, NTT) 的精美算法得以实现的。NTT 通过递归地利用某些点的对称性特性，能够在 $\mathcal{O}(n \log n)$ 内实现求值和插值，从而使转换时间变为亚二次方。

但由于 NTT 是在有限域上运行的，因此我们无法处理负数形式的 $x$ 值。这时，乘法子群 (multiplicative subgroups)、循环性 (cyclicity) 和单位根 (roots of unity) 的概念就派上用场了。这些概念将允许我们利用有限域中存在的对称性来更高效地执行多项式乘法。我们将在未来的文章中详细探讨 NTT 的工作原理。

Appendix

Uniqueness of lowest degree polynomial proof

我们将证明，如果存在两个次数相等的多项式 $p(x)$ 和 $q(x)$ 插值穿过同一组点，那么必定存在一个多项式 $r(x)$，使得 $r(x) = p(x)-q(x)$。

然后我们将证明 $r(x)$ 唯一可能的解是 $r(x) = 0$，否则我们最终会得到一个根的数量多于其次式的多项式，我们将证明这是不可能的。现在让我们详细来看看这些步骤。

我们先假设最低次的 Lagrange polynomial 不是唯一的。 那么至少存在两个不同的最低次多项式穿过给定的所有 $n+1$ 个点。假设这两个多项式为 $p(x)$ 和 $q(x)$。现在，将多项式 $r(x)$ 定义为 $p(x)$ 和 $q(x)$ 之间的差值。

现在，如果我们可以证明对于所有的 $x$ 值 $r(x)$ 都为 $0$，那么我们就证明了 $p(x)$ 等于 $q(x)$，因此 Lagrange polynomial 是唯一的。

因为 $p(x)$ 和 $q(x)$ 的次数都最多为 $n$，由简单的代数减法可知 $r(x)$ 的次数也最多为 $n$。
此外，由于 $p(x)$ 和 $q(x)$ 都穿过相同的 $n+1$ 个点，对于每一个 $x$ 值，它们的求值结果都会得到相同的 $y$ 值。

注：从图形上看，当两个不同的多项式对于一个给定的 $x$ 计算出相同的 $y$ 值时，意味着它们在该点相交。例如：

在 $x=2$ 时，两者的结果均为 $y=4$，因此它们在点 $(2,4)$ 处相交。在这种情况下，我们处理的是不同的多项式。对于给定的 $x$ 具有相同 $y$ 值的另一种可能性是，它们实际上是同一个多项式！在那种情况下，它们对所有 $x$ 的值都将具有相同的 $y$ 值，而不仅仅是在某些特定的 $x$ 值处。

在 $p(x)$ 和 $q(x)$ 的情况中，它们至少对于 n + 1 个不同的 $x$ 值是相等的。这可以在数学上表达为：

因此，$p(x)$ 和 $q(x)$ 在所有 $n+1$ 个点上的差值将为零。即，

因此，$r(x)$ 在 $n+1$ 个点上求值为零，这意味着它是一个零多项式。让我们来看看这具体是为什么。

零多项式是指对所有 $x$ 的值求值都为零的多项式。零多项式最简单的例子是：

另一种看待这个问题的方式是，如果我们求值多项式的域（即能够对其求值的一组点的集合），假定为 $S=\{x_0, x_1 \cdots, x_{n-1}\}$，那么该域上的零多项式可以为：

因为，

对于域 $S$，我们还可以有更多的零多项式，比如：

请注意，$f_1(x)$、$f_2(x)$ 和 $f_3(x)$ 对于域 $S$ 的求值均为零，因此它们都是零多项式。我们还能写出更多。最原始的一个就是 $f_3(x)=0$，即常数零本身。

注：如果域 $S$ 被定为所有实数的集合，那么我们能拥有的唯一零多项式就是 $f(x)=0$，因为没有其他多项式能够对所有实数求值都为零。

现在，观察我们看过的每个示例零多项式的根的数量和次数。

多项式的根是指定义域中使得该多项式求值为零的值，而大家都知道，多项式的次数就是变量的最高次幂。

• $f_1(x):$ 根- $n$，次数- $n$
• $f_2(x):$ 根- $n$，次数- $2n$
• $f_3(x):$ 根- $n$，次数- $0$

它们都在 $S$ 上求值为零；因此根的数量是 $n$，而次数可以通过修改 $p(x)$ 来改变，其最初的次数是 $n$。

还要注意的是，$f_3(x)=0$ 的根的数量多于其次式。这只有在零多项式的情况下才可能发生，特别是最原始的 $f_3(x)=0$。否则，根的数量总是小于或等于次数。

考虑一个次数为 $n$ 的非零多项式；它最多可以有 $n$ 个根（或与 $x$ 轴的交点）。原始的零多项式是唯一的例外，因为它的根的数量大于其次式。

例如，
一个次数为 $2$ 的二次方程，比如 $q(x)=x^2-3x+2$，有两个根，即 $x=1$ 和 $x=2$。

要想一个二次方程具有两个以上的根，它必须等于零，即 $q(x)=0$。

现在，回到我们的论点：既然 $r(x)$ 在 $n+1$ 个点上求值为零，它必然至少拥有 $n+1$ 个根，这大于它的次数 $n$。因此 $r(x)$ 必须等于零。

这就意味着 $p(x)=q(x)$，表示它们是同一个多项式。因此，插值穿过一组 $n+1$ 个不同点的最低次多项式是唯一的。