多项式乘法

本文深入探讨了多项式乘法，特别是在零知识证明和密码学中的应用。文章首先回顾了传统的多项式乘法方法，然后研究了多项式的不同表示形式（系数形式和点值形式），比较了在不同形式下的多项式算术，并探讨了如何利用这些形式加速多项式乘法，最终引出了数论变换(NTT)算法。NTT通过在(\mathcal{O}(n \log n))时间内进行求值和插值，从而加速多项式乘法。

介绍

多项式乘法广泛应用于零知识证明和数学密码学中。但是，用于多项式乘法的蛮力或传统方法以 \(\mathcal{O}(n^2)\) 运行，这对于小输入来说很好，但随着多项式次数的增加，它变得非常昂贵。本文将详细探讨多项式乘法，以探索使其更快的方法。

  • 我们首先回顾一下教科书/传统的多项式运算

  • 接下来研究多项式的不同表示形式

  • 我们检查并比较不同形式的多项式运算

  • 最后，我们将研究这些形式如何潜在地加速多项式乘法，以及它们如何构成称为数论变换 (NTT) 算法的基础

    • *

多项式乘法——传统方法

考虑两个多项式 \(p_1(x)\) 和 \(p_2(x)\)，每个多项式的次数都为 \(n\)：

\(p_1(x) = a_0 + a_1x + a_2x^2 + \dots + a_nx^n\)

\(p_2(x) = b_0 + b_1x + b_2x^2 + \dots + b_nx^n\)

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

\begin{aligned} p_1(x) \cdot p_2(x) &= p_1(x)\cdot (b_0 + b_1x + \dots + b_nx^n) \\ &= (a_0 + a_1x + \dots + a_nx^n)\cdot (b_0 + b_1x + \dots + b_nx^n) \\ &= a_0\cdot (b_0 + b_1x + \dots + b_nx^n) \\ &+ a_1x\cdot (b_0 + b_1x + \dots + b_nx^n) \\ & \vdots\\ &+ a_nx^n\cdot (b_0 + b_1x + \dots + b_nx^n) \end{aligned}

例如，

设 \(p_1(x) = 1 + 2x\)，

和 \(p_2(x) = 3 + 4x\)

那么，

image

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

## 设 A 为表示 p1(x) 系数的数组
A = [a0, a1, ..., an]
## 设 B 为表示 p2(x) 系数的数组
B = [b0, b1, ..., bn]
## 设 C 为存储 p1(x).p2(x) 系数的数组

function multiply_polynomials(A, B):
    n = len(A)
    m = len(B)
    C = array of zeros of length (n + m - 1) # 长度为 (n + m - 1) 的零数组

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

你会得到如下结果：

\[\ \begin{array}{c|cc}\ \times & 3 & 4x \\ \hline\ 1 & 3 & 4x \\ 2x & 6x & 8x^2\ \end{array}\ \]

对于外循环的每次 n 次迭代，内循环执行 n 次（假设相同的次数 \(m=n\)），因此给出 n 乘以 n，即 \(\mathcal{O}(n^2)\) 的运行时间。

我们现在想看看是否可以优化它并做得更好。或者简单地说，有没有办法使多项式乘法更快？

表示多项式的方法

我们可以用两种方式表示一个多项式——系数形式和点形式。在我们研究如何使多项式乘法更快之前，我们需要了解多项式可以用计算表示的两种重要方式。

系数形式

多项式以单项式基表示，这意味着它被写成变量的幂的线性组合。该表示是其系数的向量或数组，按变量（这里 \(x\)）的幂的递增顺序排列。例如，对于一个次数为 \(n\) 的多项式 \(p(x)\)：

\(p(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n\)

\(p(x)\) 的系数形式很简单：

\([a_0, a_1, a_2 \dots ,a_n]\)

其中第一个元素对应于常数项或 \(x^0\) 的系数，而最后一个元素对应于 \(x^n\) 的系数。

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

点（或值）形式

这种表示形式基于这样一个事实，即每个 \(n\) 次多项式都可以用位于其上的 \(n+1\) 个不同点的集合来表示。

例如，考虑一个二次多项式（\(2\) 次）：\[2x^2-3x+1\] 现在取位于该曲线上的任意 \(3\) 个（因为 \(n=2\)）点，例如 \((0,1)\)、\((1,0)\) 和 \((2,3)\)。我们可以说这 \(3\) 个点代表给定的多项式。或者，如果我们只是被赋予这些点，就有可能从这些信息中找到多项式 \(2x^2 -3x+1\)。为什么这样可行？或者我们如何能够用 \(n+1\) 个点等价地表示一个 \(n\) 次多项式？

这是因为：

对于每组 \(n+1\) 个不同的点，存在一个唯一的最低次数多项式，其次数最多为 \(n\)，并且通过所有这些点。

这个最低次数多项式被称为拉格朗日多项式。

例如，

给定两个点 \((1, 2)\) 和 \((3, 4)\)，存在一个唯一的 \(1\) 次多项式（一条线），通过这些点：\[p(x) = 1 + x\]

类似地，

给定三个点 \((0, 1)\)、\((1, 4)\) 和 \((2, 9)\)，通过这些点的 \(2\) 次拉格朗日多项式是：\[p(x) = 1 +2x+ x^2\]

给定一组点，如何计算这个特殊多项式是这篇关于 拉格朗日插值 的文章中讨论的内容。

拉格朗日多项式的唯一性

在我们尝试证明拉格朗日多项式的唯一性之前，你必须注意，对于一组点，存在多个给定次数的多项式通过所有这些点。但只有最低次数的多项式是唯一的。

例如，在上面的 \((1, 2)\) 和 \((3, 4)\) 的例子中，存在大量通过这两个点的多项式：

\(x^2 -3x +4\) 和 \(2x^2 -7x +7\) 是许多 \(2\) 次（二次）多项式中的两个，它们通过这两个点。

image

类似地，如果你考虑 \(3\) 次，通过 \((1,2)\) 和 \((3,4)\) 的两个示例多项式是 \(x^3 -5x^2 +8x-2\) 和 \(-x^{3}+4x^{2}-2x+1\)。 还有更多。image

但是对于最低次数，这里是 \(1\)，只存在一个最低次数的多项式，即 \(p(x) = 1 + x\)。 它是唯一的，并且没有第二个 \(1\) 次多项式可以通过 \(2\) 个给定的点。

image

如何确定这个最低次数？

对于每组 \(n+1\) 个不同的点，存在一个次数最多为 \(n\) 的唯一多项式通过它们。如果某些点是共线的或位于较低次数的多项式上，则唯一多项式的次数小于 \(n\)。 因此，我们使用术语“最多 \(n\)”来覆盖次数正好为 n 的情况，以及次数较低的情况。

例如，

给定 \((1,2),(2,4),\) 和 \((3,6)\)，我们发现通过这些点的最低次数多项式是 \(y=2x\)。 这是因为这些点是共线的，即它们位于一条线上。 这是因为它们之间任意一对的斜率是相同的：

\[\ \frac{4-2}{2-1} = \frac{6-4}{3-2} = 2\ \] 因此，最低次数是 \(1\)，并且 \(y=2x\) 是唯一的拉格朗日多项式。

类似地，

给定 5 个点，\((-2,1), (-1,0), (0,1), (1,4), (2,9)\)，我们发现它们都位于一个具有以下等式的抛物线上：

\[\ y = x^2 + 2x + 1\ \] 这是一种所有给定点都位于较低次数多项式上的情况，此处为 \(2\) 次，因此拉格朗日多项式的次数为 \(2\)，小于 \(n\)（此处，\(n=4\)）。

我们如何证明这个最低次数多项式实际上是唯一的？

拉格朗日多项式的唯一性可以用一个简洁而直观的数学矛盾来证明。

让我们假设最低次数的拉格朗日多项式不是唯一的。 那么，至少有两个不同的最低次数多项式通过所有给定的 \(n+1\) 个点。 设这两个多项式为 \(p(x)\) 和 \(q(x)\)。 现在，将多项式 \(r(x)\) 定义为 \(p(x)\) 和 \(q(x)\) 之间的差。 \[r(x) = p(x) - q(x)\]

由于 \(p(x)\) 和 \(q(x)\) 的次数最多为 \(n\)，因此从简单的代数减法可以得出，\(r(x)\) 的次数也必须最多为 \(n\)。

此外，由于 \(p(x)\) 和 \(q(x)\) 都通过相同的 \(n+1\) 个点，因此对于每个 \(x\) 值，它们的值都相同。

注意：从图形上看，当两个不同的多项式对于给定的 \(x\) 值具有相同的 \(y\) 值时，这意味着它们在该点相交。 例如：

\[\ p(x) = x^2 \quad \text{和} \quad q(x) = 2x.\ \]

image

在 \(x=2\) 处，两者都给出 \(y=4\)，因此它们在点 \((2,4)\) 处相交。 但我们很快将证明 \(p(x)\) 和 \(q(x)\) 实际上是相同的多项式，因为它们在比它们的次数更多的点处相交。 这只是为了帮助你可视化两个不同的多项式如何对于给定的 \(x\) 值具有相同的 \(y\) 值。

这里我们有：

\[p(x_i)=q(x_i) \space\space\forall i \in \{0,1,\dots, n\}\ \] 因此，\(p(x)\) 和 \(q(x)\) 在所有 \(n+1\) 个点处的差将为零。 也就是说，

\[r(x_i) =p(x_i)- q(x_i) = 0 \space\space\forall i \in \{0,1,\dots, n\}\] 因此 \(r(x)\) 在 \(n+1\) 个点处的值为零，这意味着它是一个零多项式。 让我们更清楚地看看为什么。

零多项式是在所有 \(x\) 值处的值均为零的多项式。 零多项式最简单的例子是：

\[\ p(x) = 0\ \]

另一种看待这个问题的方式是，如果我们的多项式评估域是，例如，\(S=\{x_0, x_1 \cdots, x_{n-1}\}\)，那么这个域的零多项式可以是： \[p(x)=(x-x_0)(x-x_1)\cdots (x-x_{n-1})\]

因为，\[p(x) = 0 \quad \forall \quad x\in \{x_0,x_1,\cdots x_{n-1}\}\]

我们可以为域 \(S\) 提供更多的零多项式，可以通过将其他多项式乘以 \(p(x)\) 获得。 一些例子是：\[f_1(x)=x^2\cdot p(x)\]\[f_2(x)=p(x)\]\[f_3(x)=(x-u)^3(x-v)\cdot p(x)\]\[f_4(x)=0\cdot p(x)\]

其中 \(u\) 和 \(v\) 只是不在集合 \(S\) 中的实数。

请注意，对于域 \(S\)，每个 \(f_1(x), f_2(x), f_3(x)\) 和 \(f_4(x)\) 的值都为零，因此是一个零多项式。 我们可以有更多。 最原始的是 \(f_4(x)=0\)，即常数零本身。

注意：如果域 \(S\) 被视为所有实数的集合，那么我们可以拥有的唯一零多项式是 \(f(x)=0\)，因为没有其他多项式对于所有实数的值都为零。

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

多项式的根是域中多项式的值为零的值。 众所周知，多项式的次数是变量的最高幂。

  • \(f_1(x):\) 根- \(n\)，次数- \(n+2\)
  • \(f_2(x):\) 根- \(n\)，次数- \(n\)
  • \(f_3(x):\) 根- \(n\)，次数- \(n+4\)
  • \(f_4(x):\) 根- \(n\)，次数- \(0\)

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

另请注意，\(f_4(x)=0\) 的根数大于其次数。 这仅在零多项式的情况下才有可能，特别是原始多项式 \(f_4(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)=r(x)=0\] 这意味着 \(p(x)=q(x)\)，意味着它们是相同的多项式。 因此，内插一组 \(n+1\) 个不同点的最低次数多项式是唯一的。

系数形式和点形式之间的转换

多项式的点形式和系数形式是等价的，即以两种形式中的任何一种形式相乘和相加多项式将得到相同的结果。 因此，可以从一种形式转换为另一种形式，正如我们现在将看到的那样。

插值（点形式 → 系数形式）

从点形式到系数形式的转换称为插值，基本上是计算通过所有给定点的最低次数的多项式。 最著名的做法之一是使用我们之前提到的拉格朗日插值。 如果你不熟悉它，你可以阅读这篇文章。

简而言之，如果给定一组 \((n+1)\) 个不同的点 \[\{(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)\}\] 我们使用拉格朗日插值公式找到次数最多为 \(n\) 的唯一最低次数多项式 \(p(x)\)，使得：

\[\ p(x_i) = y_i \quad \text{对于所有 } i = 0, 1, \dots, n\ \]

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

求值（系数形式 → 点形式）

从系数形式到点形式的转换称为求值，本质上是在 \(x\) 值处求多项式的值，以获得 \(y\) 的对应值，从而获得一组表示多项式的 \((x_i, y_i)\) 点。 一种常见的做法是使用霍纳规则（将在以后的文章中详细讨论）。

简而言之，给定多项式 \(p(x)\) 的系数 \([a_0, a_1, \dots, a_n]\) 和一个值 \(x_i\)，霍纳规则使用以下方法计算 \(p(x_i)\)：

\[\ p(x_i) = a_0 + x_i(a_1 + x_i(a_2 + \dots + x_i a_n) \dots)\ \]

这本质上是提取 \(x\) 的公共幂，一次一个，直到它耗尽。 让我们看一个例子来更好地理解它。

给定一个多项式：\(p(x) = 2 + 3x + 5x^2 + x^3\)，和一个值 \(x = 2\)，我们将回顾霍纳规则如何计算 \(p(2)\)。

我们以下列方式重写 \(p(x)\)（如上面的广义表达式所示）：

\[\ p(x) = 2 + x(3 + x(5 + x(1)))\ \]

代入 \(x = 2\)：

image

观察这些步骤如何涉及交替的乘法和加法。 上述计算的步骤 1、3 和 5 是乘法，而步骤 2、4 和 6 是加法。 总共有 \(n\) 次乘法和 \(n\) 次加法（这里 \(n=3\)），总运行时间为 \(\mathcal{O}(n)\)。 这就是霍纳规则如何以 \(\mathcal{O}(n).\) 计算 \(n\) 次多项式在某个 \(x\) 值处的值。

因此，使用此规则在 \(n+1\) 个不同的 \(x\) 值处评估多项式，即从系数形式转换为点形式，需要 \(n\) 乘以 \(n+1\)，即 \(\mathcal{O}(n^2)\)。

系数形式 VS 点形式

我们说多项式的系数形式和点形式是等价的，并且可以相互转换。 也就是说，以任何一种形式进行加法和乘法时，最终结果没有区别。 让我们检查一下，首先从加法示例开始。

系数形式的加法

考虑以系数形式给出的两个多项式，\[\ p_1(x) = 1 + 2x + 3x^2 \]\[p_2(x) = 4 + 0x + 1x^2 \] 或它们各自的系数数组-

\(p_1\)：\([1,\ 2,\ 3]\) 和 \(p_2\)：\([4,\ 0,\ 1]\)

现在，添加这两个多项式只是按元素方式添加这两个数组。 并且结果系数数组表示最终多项式。 让我们验证一下：

\[\ p_{\text{sum}}(x) = (1+4) + (2+0)x + (3+1)x^2 = 5 + 2x + 4x^2\ \]

或者简单地说，\([(1+4), (2+0),(3+1)] = [5,\ 2,\ 4]\)

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

点形式的加法

考虑相同的两个多项式，\[\ p_1(x) = 1 + 2x + 3x^2 \]\[p_2(x) = 4 + 0x + 1x^2 \] 首先我们需要将它们从系数形式转换为点形式。 由于两个多项式的次数均为 \(2\)，因此和的次数也最多为 \(2\)。 因此，我们需要 \(3\) 个点来表示和，即（次数加 1：\(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\)

这 \(3\) 个点 \((0, 5), (1, 11)\) 和 \((2, 25)\) 为我们提供了和的点表示。 让我们验证它们是否满足我们之前计算的方程式：\[p_{\text{sum}}(x) = 5 + 2x + 4x^2\]

  • \(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)\)。

现在让我们也仔细看看乘法。

系数形式的乘法

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

\[\ p_1(x) = 1 + 2x\]\[p_2(x) = 3 + 4x\ \]

或它们各自的系数数组：

\(p_1 = [1,\ 2]\) 和 \(p_2 = [3,\ 4]\)

使用之前讨论的分配律方式将它们相乘，得到：

\[\ \begin{aligned}\ p_{\text{prod}}(x) &= (1)(3+4x) + (2x)(3 + 4x) \\ &= 3 + 4x + 6x + 8x^2 \\&= 3 + 10x + 8x^2\ \end{aligned}\ \]

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

点形式的乘法

我们现在考虑相同的多项式并将它们转换为它们的点形式。 \[p_1(x) = 1 + 2x\]\[p_2(x) = 3 + 4x\ \] 由于它们都具有次数 \(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}}(x) = 3 + 10x + 8x^2\ \]

  • \(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\) 次求值，以将它们转换为点形式： \[p_1(x_0), p_1(x_1), p_1(x_2), \dots p_1(x_{2n})\] \[p_2(x_0), p_2(x_1), p_2(x_2), \dots p_2(x_{2n})\] 然后，我们通过对这两个集合逐元素相乘来执行点形式乘法，这需要 \(2n+1\) 次乘法，即 \(\mathcal{O}(n)\) 的运行时间。

\[ p_1(x_0) \cdot p_2(x_0), \; p_1(x_1) \cdot p_2(x_1), \dots, \; p_1(x_{2n}) \cdot p_2(x_{2n}) \] 最后，我们得到 \(2n+1\) 个点，这些点表示乘积 \(p_1(x).p_2(x)\)：

\[ \{(x_0,p_1(x_0) \cdot p_2(x_0)), \; (x_1, p_1(x_1) \cdot p_2(x_1)), \dots, \; (x_{2n}, p_1(x_{2n}) \cdot p_2(x_{2n}))\} \]

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

但仍然存在一个小问题——我们还没有考虑转换为点形式和反之的开销。

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

  1. 将系数形式转换为点形式

我们将要相乘的 \(n\) 次的两个多项式在 \((2n+1)\) 个 \(x\) 值处求值，以获得每个包含 \((2n+1)\) 个求值的集合。使用霍纳法则，这需要 \(\mathcal{O}(n^2)\)。

  1. 点形式表示中的逐元素乘法

我们将这两个集合逐元素相乘，得到 \((2n+1)\) 个求值，从而给出乘积的点形式表示。这需要 \(\mathcal{O}(n)\)。

  1. 将点形式转换为系数形式

我们找到通过所有结果 \((2n+1)\) 个点的唯一最低次数多项式（系数形式）。

使用拉格朗日插值法，这需要 \(\mathcal{O}(n^2)\)。

因此，上述步骤的总体运行时间为： \[\mathcal{O}(n^2) + \mathcal{O}(n) + \mathcal{O}(n^2) \approx \mathcal{O}(n^2)\] 这并不比我们开始时的情况更好。因此，我们需要看看是否可以进行任何优化以使此过程更快。

优化转换

要记住的关键是系数形式的乘法需要 \(\mathcal{O}(n^2)\)，而点形式的乘法（逐元素）需要 \(\mathcal{O}(n)\)。因此，如果我们能找到一种方法来比 \(\mathcal{O}(n^2)\) 更快地将系数形式转换为点形式，反之亦然（上述步骤 1 和 3），那么我们可以优化乘法以在亚多项式时间内运行。

重要的是要注意，我们无法优化多项式加法，因为系数形式和点形式的加法都以 \(\mathcal{O}(n)\) 运行，如此处所述。

所以现在让我们集思广益，看看我们有哪些方法可以使乘法下从系数形式到点形式的转换更快。

如果我们知道一个点，对其求值可以给我们更多相关点的求值结果，该怎么办？或者节省我们一些重复计算？

例如，如果我们有一个具有对称图的多项式，则评估一个点也会告诉我们其对应对称点的评估值。

考虑多项式 \(p(x)= x^2\)，

观察一下， \[p(-2) = 4\space\space\space \text{and} \space\space\space p(2) =4\]

image

或者更简单地说，看看对于所有 \(x_i\)，

\[p(-x_i)=p(x_i)\] 这不仅适用于 \(p(x)=x^2\)，而且推广到所有仅包含偶数次幂系数的多项式，也称为偶多项式。

例如，考虑偶多项式（项仅具有 \(x\) 的偶数次幂）：

\[q(x) =x^{10}+3x^{8}-2x^{6}+3x^{4}-2x^{2}-x^{0} \] image

在这里也很容易观察到， \[q(x) =q(-x)\]

从视觉上看，偶多项式的图是关于 \(y\) 轴对称的，并且对于某个 \(x\) 的正值和负值，它们求出的 \(y\) 值相同。

那么仅包含奇数次幂系数的奇多项式呢？

考虑 \(p(x) = x^3\)，

观察一下，

\[p(-2) = -8 =-p(2)\] image

看看对于所有 \(x_i\)，

\[p(-x_i) = -p(x_i)\]

同样，这不仅适用于 \(p(x)=x^3\)，而且推广到所有奇多项式，即仅具有 \(x\) 的奇数次幂项的多项式。例如， \[q(x)=-x^{7}+3x^{5}+x^{3}-x\] image

从图表中观察一下， \[q(x) = -q(-x)\] 从视觉上看，所有奇多项式的图都关于原点对称，这使得上述等式对它们都成立。

现在你可以看到，在评估某些点之后，我们也可以获得其他点的评估值，而无需任何额外的计算。例如，在上面的示例中，对于偶多项式和奇多项式，知道 \(p(x)\) 的评估值也会给我们 \(p(-x)\) 的评估值。

我们可以利用这个事实来使多项式乘法更快。这正是一个名为 数论变换 (NTT) 的漂亮算法所允许我们做的。通过递归地利用我们刚刚看到的某些点的这一特性，NTT 使得在 \(\mathcal{O}(n \log n)\) 中进行评估和插值成为可能——从而使转换变为亚二次的。

但是由于 NTT 在有限域上运行，因此我们无法使用 \(x\) 的负值。这就是乘法子群、循环性和单位根概念的用武之地。总之，它们允许你利用我们在有限域上下文中谈到的重复评估属性，从而使多项式乘法更快！我们将在接下来的文章中详细介绍 NTT 的工作原理。

  • 原文链接： hackmd.io/_9-URR4GTpKqHi...
  • 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～
点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ，好文好收益，欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
_9-URR4GTpKqHij6eH5NIg
_9-URR4GTpKqHij6eH5NIg
江湖只有他的大名，没有他的介绍。

_9-URR4GTpKqHij6eH5NIg

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！