多项式一个极其有用的特性是 m 次多项式可以使用 \(m+1\) 个数值点推导出来。这意味着我们可以从集合 \(S\) 中唯一地导出 m 次多项式：
\[S= \{(x_0,y_0), (x_1,y_1),\ldots,(x_m,y_m) | x_i\neq x_j\text{ for all indices i and j}\}\]
因此，多项式具有这样的性质：\(m+1\) 个满足 \(x_i \neq x_j\) 条件的 \((x_i,y_i)\) 点可以确定所有 \(x \in R\) 的 \((x, P(x))\) 的集合。这种 少决定多 的性质在多项式内广泛的使用，包括在 SNARKs 中。因此，我们需要知道使用一组点计算多项式的方法。
如果我们想要计算得到的多项式的系数存在乘法逆元，则可以使用拉格朗日插值(Lagrange Interpolation)法进行求解。给定一个点集 \(S\) ，使用以下算法可以求解出 \(m\) 次多项式 \(P\)：
示例 29
给定集合 \(S=\{(0,4),(-2,1),(2,3)\}\) 。我们的任务是求出一个位于 \(\Bbb{Q}[x]\) 内的二次多项式，即系数均属于有理数的二次多项式。因为 \(\Bbb{Q}\) 内的元素均具有乘法逆元，我们可以使用拉格朗日插值算法，计算如下：
\[ \begin{align*} l_0(x) & = \frac{x-x_1}{x_0-x_1}\cdot\frac{x-x_2}{x_0-x_2} = \frac{x+2}{0+2}\cdot\frac{x-2}{0-2} = -\frac{(x+2)(x-2)}{4}\\ & = -\frac{1}{4}(x^2-4)\\ l_1(x) & = \frac{x-x_0}{x_1-x_0}\cdot\frac{x-x_2}{x_1-x_2} = \frac{x-0}{-2-0}\cdot \frac{x-2}{-2-2} = \frac{x(x-2)}{8}\\ & = \frac{1}{8}(x^2-2x)\\ l_2(x) & = \frac{x-x_0}{x_2-x_0}\cdot\frac{x-x_1}{x_2-x_1} = \frac{x-0}{2-0}\cdot\frac{x+2}{2+2} = \frac{x(x+2)}{8}\\ & = \frac{1}{8}(x^2+2x)\\ P(x) & = 4\cdot (-\frac{1}{4}(x^2-4)) + 1\cdot \frac{1}{8}(x^2-2x) + 3\cdot \frac{1}{8}(x^2+2x)\\ & = -x^2+4 + \frac{1}{8}x^2-\frac{1}{4} x + \frac{3}{8}x^2+\frac{3}{4} x \\ & = -\frac{1}{2} x^2 +\frac{1}{2} x + 4 \end{align*} \]
事实上，通过 \(P(0)=4, P(-2)=1, P(2)=3\) ，可以使用 Sage 进行求解，如下：
sage: Qx = QQ['x']
sage: S = [(0, 4), (-2, 1), (2, 3)]
sage: Qx.lagrange_polynomial(S)
-1/2*x^2 + 1/2*x + 4
示例 30
为给出与本书主题更加相关的另一个示例，让我们重新考虑集合 \(S=\{(0,4),(-2,1),(2,3)\}\) 。这一次，我们使用这些点计算多项式 \(P \in \Bbb{Z}_5[x]\) 。因为我们在 示例 16 已经知道 \(\Bbb{Z}_5\) 内的元素均存在逆元，所以我们可以使用拉格朗日插值法求解出属于 \(\Bbb{Z}_5\) 的二次多项式。计算过程如下：
\[ \begin{align*} l_0(x) & = \frac{x-x_1}{x_0-x_1}\cdot\frac{x-x_2}{x_0-x_2} = \frac{x+2}{0+2}\cdot\frac{x-2}{0-2} = \frac{(x+2)(x-2)}{-4} = \frac{(x+2)(x+3)}{1}\\ & = x^2+1\\ l_1(x) & = \frac{x-x_0}{x_1-x_0}\cdot\frac{x-x_2}{x_1-x_2} = \frac{x-0}{-2-0}\cdot \frac{x-2}{-2-2} = \frac{x}{3}\cdot \frac{x+3}{1} = 2(x^2+3x)\\ & = 2x^2+x\\ l_2(x) & = \frac{x-x_0}{x_2-x_0}\cdot\frac{x-x_1}{x_2-x_1} = \frac{x-0}{2-0}\cdot\frac{x+2}{2+2} = \frac{x(x+2)}{3} = 2(x^2+2x)\\ & = 2x^2+4x\\ P(x) & = 4\cdot (x^2+1) + 1\cdot (2x^2+x) + 3\cdot (2x^2+4x) \\ & = 4x^2+4 + 2x^2 +x + x^2+2x\\ & = 2x^2 +3x +4 \end{align*} \]
使用 Sage 计算如下：
sage: F5 = GF(5)
sage: F5x = F5['x']
sage: S = [(0, 4), (-2, 1), (2, 3)]
sage: F5x.lagrange_polynomial(S)
2*x^2 + 3*x + 4
练习 31. 已知 示例 16 中给出的模 5 算术体系，给定集合 \(S=\{(0,0),(1,1),(2,2),(3,2)\}\) ，求解符合上述点集的多项式 \(P \in \Bbb{Z}_5[x]\)
练习 32. 已知上一个例子中给出的集合 \(S\)。为什么我们不能使用拉格朗日插值算法在 \(\Bbb{Z}_6\) 内求解符合 \(S\) 的多项式？