ZK101 - 零知识学习零知识

多项式是什么？

多项式其实在写法上和方程非常相似

他们之间微弱的差别在于，多项式是一个函数，而方程是一个等式。

说白了：

多项式的根（也叫零点）是让多项式等于0的那些x值。比如：

对于多项式 $f(x) = x^2 - 1$ ，它的根是 1 和 -1，因为：

💡

在ZK证明中，多项式的根具有特殊意义：

在ZK中，我们经常需要为一个给定的点集寻找多项式，这个多项式经过点集中的所有点。

一般来说，我们会使用拉格朗日插值法来构建多项式。这是一种非常简单的方法。构建过程分为两步：

l_i(x) = \prod_{j \neq i} \frac{x - x_j}{x_i - x_j}

f(x) = \sum_{i} y_i \cdot l_i(x)

如果你没看懂，或者不想看上面的公式，没关系，我们通过一些简单的例子来学习。

假设点集为：

\begin{align*} l_1(x) &= \frac{(x-2)(x-3)(x-4)}{(1-2)(1-3)(1-4)} \\ l_2(x) &= \frac{(x-1)(x-3)(x-4)}{(2-1)(2-3)(2-4)} \\ l_3(x) &= \frac{(x-1)(x-2)(x-4)}{(3-1)(3-2)(3-4)} \\ l_4(x) &= \frac{(x-1)(x-2)(x-3)}{(4-1)(4-2)(4-3)} \end{align*}

f(x) = 2l_1(x) + 3l_2(x) + 8l_3(x) + 4l_4(x)

我们仔细端详一下这几个基底多项式，我们可以很容易的发现，他们的目的都是在于构建一个在 $x_i$ 处值为1，在其他点处值为0的多项式。
可以看看下面的示例图，尝试看一下每个点的值。（你可以点击标签🏷️名称来隐藏当前多项式曲线）

基底多项式

很明显，上面的多项式在 $x_i$ 处值为1，在其他点处值为0。此时，我们获得了多个基底多项式。

那么如何获得一个能通过所有点的多项式呢？

我们只需要将每个基底多项式乘以对应的y值，然后相加（只看结果就行）：

\begin{align*} f(x) &= 2l_1(x) + 3l_2(x) + 8l_3(x) + 4l_4(x) \\ &= 2 \cdot \frac{(x-2)(x-3)(x-4)}{(1-2)(1-3)(1-4)} + 3 \cdot \frac{(x-1)(x-3)(x-4)}{(2-1)(2-3)(2-4)} + 8 \cdot \frac{(x-1)(x-2)(x-4)}{(3-1)(3-2)(3-4)} + 4 \cdot \frac{(x-1)(x-2)(x-3)}{(4-1)(4-2)(4-3)} \\ &= \frac{13}{6}x^3 + 15x^2 - \frac{173}{6}x + 18 \end{align*}

最终多项式

是不是很简单？总结一下来说就是两个步骤：

注意，以上取值范围为自然数，所以可以绘制一个曲线，当我们取值范围在一个有限域或者乘法子群中时，无法绘制曲线，只能绘制离散的点。因为有限域中取值数量是固定的。并不是和自然数中一样，可以在小数点之间取值。

多项式的因式分解是将多项式表示为多个因式的乘积。比如：

x^2 - 1 = (x+1)(x-1)

多项式的因式分解有一个重要特点：如果一个数是多项式的根，那么这个多项式一定可以被 $(x-a)$ 整除。

比如对于多项式 $f(x) = x^2 - 1$ ：

根：当 $f(a) = 0$ 时， $a$ 是多项式 $f(x)$ 的根

💡

在ZK证明中，这个性质经常被用来检查某个值是否为多项式的根：