Polynomial

In this article, I will show two common ways to program polynomial

coefficient and point-value representation

对于 degree = n-1 多项式 A(x)，

  1. Coefficient representation: 所有项的系数组成的系数向量 \((a_0, a_1,a_2,...,a_{n-1})\) 唯一确定多项式:\(A(x) = \sum_{i=0}^{n-1}a_ix^i\)
1
2
3
4
# f(x) = x*4 + 3*x**2 + 4*x + 9
coefficient = [1, 0, 3, 4, 9] # [a4, a3, a2, a1, a0]
# or
coefficient = [9，4，3，0，1] # [a0, a1, a2, a3, a4]

Evalute polynomial at \(x=2\)

1
2
3
4
5
6
coeff = [1, 0, 3, 4, 9]
# evalute at x=2
x,p = 2, 17
sum([coeff[i] *pow(x, (len(coeff)-i), p) for i in range(len(coeff))])  % p
# or
sum([coeff[i]*pow(x, i,p) for i in range(len(coeff))]) % p

Note:

  1. the order of the coefficient should be checked carefully.

    For example, numpy.poly expresses the sequence of the coefficient from highest to lowest degree, [a4, a3, a2, a1, a0].

    numpy.poly — NumPy v1.24 Manual

    But Ethereum research repository is from lowest to highest degree, [a0, a1, a2, a3, a4], which we will use.

  2. When evaluating the coefficient form polynomial at x under Prime field, the Python built-in function pow(base, exp, mod=None) is very useful.

  3. Point-value representation: 一组互不相同的 \((x_0, x_1,x_2, \cdots,x_{n})\) 代入 \(A(x)\), 得到 n 个取值 \((y_0,y_1, \cdots, y_n)\), 其中 \(y_i = \sum_{j=0}^{n}a_j x_i\)，可以通过拉格朗日插值方法唯一确定多项式。

Schwartz-Zippel lemma

Schwartz-Zippel lemma 是关于有限域中的多变量多项式零点个数的紧致上界，具体表述如下：

对于域 \(\mathbb{F}\) 上的每个阶最多为 d 的 n 变元非零多项式，对于任意有限集合 \(S \in \mathbb{F}\),

\[ \begin{equation} Pr_{r_1,\cdots,r_n \leftarrow S}[f(r_1, \cdots, r_n) = 0] \le \frac{d}{|S|} \end{equation} \]

等价地， f 在 \(S^n\) 中最多有 \(d|S|^{n-1}\) 个根, (\(Z(f)\) 是 f 的零点集)：\(|Z(f) \cap S^n| \le d*|S|^{n-1}\)

symbolic representation

In math scenarios, the symbolic representation is used for polynomials by utilizing Matlab or the sympy library of Python. Although I prefer the Python library, it turns out the sympy library is truly not as good as Matlab in practice. So prefer Matlab.

Note: The interpolation method for polynomials in the finite field is not fully implemented in sympy. Therefore, it is not recommended to use it for polynomials in the finite field.

Example code in Jupyter Notebook:

1
2
from IPython.display import Math
Math("f(x) = \sum_{i=0}^{n-1} a_i x^i")

\[f(x) = \sum_{i=0}^{n-1} a_i x^i\]

将信息编码成 coefficient form 多项式的系数，还是编码成多项式的 point-value representation 的值

Reference

Schwartz-Zippel 引理的证明 - HackMD