点值形式下的多项式乘法

多项式乘法广泛应用于零知识证明和数学密码学。但是，多项式乘法的暴力或传统方法的时间复杂度为 O(n2)，对于小输入来说还可以，但随着多项式次数的增加，成本会变得非常高。本文将详细探讨多项式乘法，以寻找使其更快的方法。

• 我们首先回顾一下教科书/传统多项式运算
• 接着研究多项式的不同表示形式
• 我们检查并比较这些不同形式的多项式运算
• 最后，我们研究这些形式如何潜在地加速多项式乘法——以及它们如何构成一种称为 数论变换 (NTT) 的算法的基础

多项式乘法 - 传统方法

考虑两个次数均为 n 的多项式 p1(x) 和 p2(x)：

p1(x)=a0+a1x+a2x2+⋯+anxnp2(x)=b0+b1x+b2x2+⋯+bnxn

使用简单的乘法对加法的分配律来乘这两个多项式的时间复杂度为 O(n2)。这里，p1(x) 的每一项都与 p2(x) 的每一项相乘：

p1(x)⋅p2(x)=p1(x)⋅(b0+b1x+⋯+bnxn)=(a0+a1x+⋯+anxn)⋅(b0+b1x+⋯+bnxn)=a0⋅(b0+b1x+⋯+bnxn)+a1x⋅(b0+b1x+⋯+bnxn)⋮+anxn⋅(b0+b1x+⋯+bnxn)

例如， 设 p1(x)=1+2x, 且 p2(x)=3+4x。

那么，

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

## 设 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)

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

你会得到如下结果：

×34x134x2x6x8x2

对于外层循环的每次 n 次迭代，内层循环执行 n 次（假设度数相等 m=n），因此得到 n 乘以 n，即时间复杂度为 O(n2)。

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

表示多项式的方法

我们可以用两种方式表示多项式：系数形式和点形式。

系数形式

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

例如，一个 n 次多项式，当表示成

p(x)=a0+a1x+a2x2+⋯+anxn

时，是以单项式基表示的，因为它使用 [1,x,x2,…,xn] 作为其系数 a0,a1,a2,..,ax 的基。

在这种表示中，p(x) 的系数可以写成向量或数组，如 [a0,a1,…,an]，其中第一个元素对应于常数项或 x0 的系数，而最后一个元素对应于 xn 的系数。

你应该注意到，我们之前看到的分配律乘法方法（时间复杂度 O(n2) ）是在多项式的系数形式上应用的。

点（或值）形式

点（或值）形式表示是基于这样一个事实：每个 n 次多项式都可以用一组位于其上的 n+1 个不同的点来表示。

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

2x2−3x+1

现在取位于该曲线上的任意 3 个点（因为 n=2），例如 (0,1)、(1,0) 和 (2,3)。我们可以说这 3 个点代表给定的多项式。或者，如果我们只给出这些点，就可以从这些信息中恢复多项式 2x2−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+x21+2(0)+(0)2=11+2(1)+(1)2=41+2(2)+(2)2=9

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

拉格朗日多项式的唯一性

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

例如，在上面 (1,2) 和 (3,4) 的例子中，存在许多通过这两个点的多项式： x2−3x+4 和 2x2−7x+7 是通过这两个点的许多 2 次多项式（二次多项式）中的两个。

类似地，如果你考虑 3 次多项式，通过点 (1,2) 和 (3,4) 的两个例子多项式是 x3−5x2+8x−2 和 −x3+4x2−2x+1。

但对于最低次数，这里是 1，只存在一个最低次数的多项式，那就是 p(x)=1+x。它是唯一的，没有其他 1 次多项式可以通过这两个给定的点。

如何确定这个最低次数？

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

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

4−22−1=6−43−2=2

因此，最低次数为 1，且 y=2x 是唯一的拉格朗日多项式。

类似地， 给定五个点 (−2,1),(−1,0),(0,1),(1,4),(2,9)，我们发现所有这些点都位于一个抛物线上，其方程为

y=x2+2x+1

这是一个所有给定点都位于较低次数多项式上的情况，这里是 2 次，因此拉格朗日多项式的次数为 2，小于 n（这里，n=4）。

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

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

由于系数形式和点形式是等价的，我们可以很容易地在它们之间进行转换，我们现在展示一下。

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

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

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

{(x0,y0),(x1,y1),…,(xn,yn)}

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

p(xi)=yifor all i=0,1,…,n

你应该记住，拉格朗日插值的时间复杂度为 O(n2)。

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

从系数形式到点形式的转换称为求值，是在 x 的值处对多项式进行求值，以获得...