MoonMath SNARK 手册

多项式是由变量(variables)和系数(coefficients)组成的，但仅包含加法、减法和乘法运算的表达式。多项式内的所有系数必须具有相同的类型，比如系数均为整数或均为有理数等。¹

更加准确的说，单变量多项式(univariate polynomial)是以下表达式:

\[ P(x) := \sum _{j = 0} ^{m}{a} _{j}{x} ^{j} ={a} _{m}x^m +{a} _{m-1} x^{m-1} + \dots + a_1 x + a_0 \]

在上式中， \(x\) 被称为变量，而 \(a\) 则被称为系数。如果 \(R\) 是系数的类型，则 \(R\) 中所有单变量多项式的集合记为 \(R[x]\) 。单变量多项式通常简称为多项式，记为 \(P(x) \in R[x]\)。常数项 \(a_0\) 也可记为 \(P(0)\)

如果多项式内所有系数均为 0，则该多项式被称为零多项式(zero polynomial)。如果多项式的常数项为 \(1\) 且其他系数均为零，则该对象是被称为单多项式(one polynomial)

给定一个非零多项式 \(P(x)=\sum_{j=0}^m a_jx^j\)，我们乘非负整数 \(deg(p) := m\) 为多项式的次数(degree)。同时，我们将零多项式的次数记为 \(-\infty\)，其中 \(-\infty\) 为一个符号，其性质为 \(-\infty + m = -\infty\) 且对于所有非负整数 \(m \in \Bbb{N}_0\)，都存在 \(-\infty < m\)。

此外，我们将多项式中具有最高次数项的系数记为首项系数(leading coefficient)，记为：

\[Lc(P):=a_m\]

译者翻译到此才发现全国科学技术名词审定委员会管理的 术语在线 网站，后文名词会尽可能选择此网站翻译。前文名词将会在将来在进行审定。

我们可以将通过指定多项式最高次数来限制多项式集合 \(R[x]\) 的范围。如果 \(m\) 是指定的最高次数，所有低于或等于 \(m\) 的多项式集合记为 \(R_{\leq m}[x]\)

示例 18

正如上文所述，多项式的系数必须具有相同的类型。以整数为系数的多项式集合记为 \(\Bbb{Z}[x]\) 。其中的一些多项式如下：

\[ \begin{align*} P_1(x) &= 2x^2 -4x +17 & \text{ \# with } deg(P_1)=2 \text{ and } Lc(P_1)=2\\ P_2(x) &= x^{23} & \text{ \# with } deg(P_2)=23 \text{ and } Lc(P_2)=1\\ P_3(x) &= x & \text{ \# with } deg(P_3)=1 \text{ and } Lc(P_3)=1\\ P_4(x) &= 174 & \text{ \# with } deg(P_4)=0 \text{ and } Lc(P_4)=174\\ P_5(x) &= 1 & \text{ \# with } deg(P_5)=0 \text{ and } Lc(P_5)=1\\ P_6(x) &= 0 & \text{ \# with } deg(P_6)=-\infty \text{ and } Lc(P_6)=0\\ P_7(x) &= (x-2)(x+3)(x-5) \end{align*} \]

每个整数都可以视为零次整数多项式。\(P_7\) 也是多项式，因为我们可以将其拆成 \(P_7(x)=x^3 - 4 x^2 - 11 x + 30\)，该多项式的次数为 \(3\) 且首项系数为 \(1\)

以下表达式不是整数多项式：

\[ \begin{align*} Q_1(x) &= 2x^2 + 4 + 3x^{-2}\\ Q_2(x) &= 0.5x^4 -2x\\ Q_3(x) &=2^x \end{align*} \]

\(Q_1\) 不是整数多项式，因为 \(x^{-2}\) 具有负指数。\(Q_2\) 是因为系数 \(0.5\) 不属于整数。\(Q_3\) 则因为变量出现在系数的指数位上。

我们可以使用 Sage 进行多项式的运算。为此，我们必须指定变量的符号和整数的类型

sage: Zx = ZZ['x'] # 使用 x 表示变量的整数多项式
sage: Zt.<t> = ZZ[] # 使用 t 表示变量的整数多项式
sage: Zx
Univariate Polynomial Ring in x over Integer Ring
sage: Zt
Univariate Polynomial Ring in t over Integer Ring
sage: p1 = Zx([17, -4, 2])
sage: p1
2*x^2 - 4*x + 17
sage: p1.degree()
2
sage: p1.leading_coefficient()
2
sage: p2=Zt(t^23)
sage: p2
t^23
sage: p6 = Zx([0])
sage: p6.degree()
-1

示例 19

回想在 示例 11 中定义到模 6 算术体系 \(\Bbb{Z}_6\)。使用 \(x\) 表示变量且系数均位于 \(\Bbb{Z}_6\) 中的多项式集合记为 \(\Bbb{Z}_6[x]\)。一些属于 \(\Bbb{Z}_6[x]\) 的多项式如下：

\[ \begin{align*} P_1(x) &= 2x^2 -4x +5 & \text{ \# with } deg(P_1)=2 \text{ and } Lc(P_1)=2\\ P_2(x) &= x^{23} & \text{ \# with } deg(P_2)=23 \text{ and } Lc(P_2)=1\\ P_3(x) &= x & \text{ \# with } deg(P_3)=1 \text{ and } Lc(P_3)=1\\ P_4(x) &= 3 & \text{ \# with } deg(P_4)=0 \text{ and } Lc(P_4)=3\\ P_5(x) &= 1 & \text{ \# with } deg(P_5)=0 \text{ and } Lc(P_5)=1\\ P_6(x) &= 0 & \text{ \# with } deg(P_5)=-\infty \text{ and } Lc(P_6)=0\\ P_7(x) &= (x-2)(x+3)(x-5) \end{align*} \]

与上一个例子相同， \(P_7\) 是一个多项式。但是，因为我们将系数定义在 \(\Bbb{Z}_6[x]\) 中，表达式 \(P_7\) 的运算有所不同，因为我们需要使用 \(\Bbb{Z}_6[x]\) 中的加法和乘法：

\[ \begin{align*} (x-2)(x+3)(x-5) &= (x+4)(x+3)(x+1) & \text{\# additive inverses in } \Z_6 \\ &= (x^2+4x+3x+3\cdot 4)(x+1) & \text{\# bracket expansion} \\ &= (x^2+1x+0)(x+1) & \text{\# computation in } \Z_6 \\ &= x^3+x^2+x^2+x & \text{\# bracket expansion}\\ &= x^3+2x^2+x \end{align*} \]

同样，我们可以使用 Sage 进行系数定义在 \(\Z_6\) 的多项式进行运算。如下：

sage: Z6 = Integers(6)
sage: Z6x = Z6['x']
sage: Z6x
Univariate Polynomial Ring in x over Ring of integers modulo 6
sage: p1 = Z6x([5, -4, 2])
sage: p1
2*x^2 + 2*x + 5
sage: p1 = Z6x([17, -4, 2])
sage: p1
2*x^2 + 2*x + 5
sage: Z6x(x-2) * Z6x(x+3) * Z6x(x-5) == Z6x(x^3 + 2*x^2 + x)
True

给定一些相同类型的元素作为多项式的系数，我们可以计算得到对应的多项式。更准确的说，设 \(P \in R[x]\) 且 \(P(x)=\sum_{j=0}^m a_j x^j\) 是一个系数属于 \(R\) 的多项式，另设 \(b \in R\) 。我们可以计算对应的多项式如下：

\[ P(b) = \sum_{j=0}^m a_j b^j \]

简单来说，就是代入求值，原文使用了 the evaluation of P at b 的表述，即将 \(b\) 代入 \(x\) 进行求值。

示例 20

再次考虑 示例 18 中的整数多项式。我们可以代入计算给定数值的结果，代入计算如下：

\[ \begin{align*} &P_1(2) = 2\cdot 2^2 -4\cdot 2 +17 = 17 \\ &P_2(3) = 3^{23}=94143178827 \\ &P_3(-4) = -4 = -4\\ &P_4(15) = 174 \\ &P_5(0) = 1 \\ &P_6(1274) =0 \\ &P_7(-6) = (-6-2)(-6+3)(-6-5) = -264 \\ \end{align*} \]

注意，不是所有的数都可以代入多项式求值，比如 \(P_1(0.5)\) 不是严格正确的，因为 \(0.5\) 不是整数。我们可以使用Sage验证代入计算的结果：

sage: Zx = ZZ['x']
sage: p1 = Zx([17,-4,2])
sage: p7 = Zx(x-2)*Zx(x+3)*Zx(x-5)
sage: p1(ZZ(2))
17
sage: p7(ZZ(-6)) == ZZ(-264)
True

示例 21

再次考虑 示例 19 给出的 \(\Z_6\) 系数多项式。我们也可以代入计算多项式的值，如下：

\[ \begin{align*} & P_1(2)= 2\cdot 2^2 -4\cdot 2 +5 = 2 - 2 + 5 = 5\\ &P_2(3)= 3^{23}=3\\ &P_3(-4)= P_3(2) = 2\\ &P_5(0)= 1\\ &P_6(4)=0 \end{align*} \]

使用sage验算如下：

sage: Z6 = Integers(6)
sage: Z6x = Z6['x']
sage: p1 = Z6x([5,-4,2])
sage: p1(Z6(2)) == Z6(5)
True