readme.md

title	tags
24. 多项式基础	zk abstract algebra polynomials

WTF zk 教程第 24 讲：多项式基础

这一讲，我们将学习多项式基础，为学习多项式环做铺垫。在密码学和零知识证明中，多项式数学是一个重要而强大的工具。

1. 多项式基础

在代数学中，一个多项式是由变量和系数通过有限次加法、乘法以及自然数幂次的乘方运算得到的代数表达式。一个 $n$ 次多项式 $P(x)$ 可以表示为：

$$ P(x) = \sum_{j=0}^{n}{a_jx^j} = a_nx^n + a_{n-1}x^{n-1} + ... + a_1x + a_0 $$

其中， $a_n, a_{n-1}, \ldots, a_1, a_0$ 是多项式的系数， $x$ 是变量，而指数为非负整数。系数可以是整数、实数、复数或其他数域中的元素。但是为了简单起见，我们先把系数限制为整数。

一些多项式的常用概念：

1. 次数（degree）：一个多项式的次数是指最高次幂的指数，也就是 $n$（其中 $a_n \neq 0$）。比如，$P(x) = 3x^4 - 2x^2 + 5$ 的次数是4。我们常用 $\deg(P)$ 表示多项式 $P(x)$ 的次数。

2. 首项系数（leading coefficient）：具有最高次幂的项的系数 $a_n$ 被称为首项系数，记为 $Lc(P) = a_n$

3. 零多项式：所有系数都为零的多项式。它的表示形式为 $P(x) = 0$。

4. 一多项式： $a_0 = 1$，剩下系数都为零的多项式。它的表示形式为 $P(x) = 1$。

5. 零次多项式（非零常数）：除了常数项以外所有系数都为零的多项式。它的表示形式为 $P(x) = a_0$，其中 $a_0 \neq 0$。零多项式，一多项式，和零次多项式都是常数多项数。

2. 多项式运算

多项式的加法和乘法遵循常见的代数规则。

1. 多项式加法： 两个多项式相加，只需将对应项的系数相加。对于两个多项式

$$ P(x) = \sum_{j=0}^{n}{a_jx^j} $$

和

$$ Q(x) = \sum_{j=0}^{m}{b_jx^j} $$

，有

$$ P(x) + Q(x) = \sum_{j=0}^{n}{a_jx^j} + \sum_{j=0}^{m}{b_jx^j} = \sum_{j=0}^{\max{(n,m)}}{(a_j+b_j)x^j} $$

例如 $(3x^4 - 2x^2 + 5) + (3x^2 + x) = 3x^4 + x^2 + x + 5$。

2. 多项式乘法： 两个多项式相乘，可以使用分配律展开，然后合并同类项。对于两个多项式 $P(x)$ 和 $Q(x)$，有

$$ P(x) \cdot Q(x) = (\sum_{j=0}^{n}{a_jx^j}) \cdot (\sum_{j=0}^{m}{b_jx^j}) = \sum_{i=0}^{n+m}\sum_{j=0}^{i}{(a_jb_{i-j})x^i} $$

例如 $(3x^4 - 2x^2 + 5) \cdot (3x^2 + x) = 9x^6 + 3x^5 -6x^4 -2x^3 +15x^2 +5x$。

3. 多项式减法： 多项式加法的逆运算：

$$ P(x) - Q(x) = \sum_{j=0}^{n}{a_jx^j} - \sum_{j=0}^{m}{b_jx^j} = \sum_{j=0}^{\max{(n,m)}}{(a_j-b_j)x^j} $$

例如 $(3x^4 - 2x^2 + 5) - (3x^2 + x) = 3x^4 -5 x^2 - x + 5$。

加法和乘法中，多项式的次数满足以下关系：

• 乘积的次数： 乘积的次数等于次数的和，即 $\text{deg}(P \cdot Q) = \text{deg}(P) + \text{deg}(Q)$。

• 和的次数： 和的次数小于或等于两个多项式之中最大的次数 $\text{deg}(P + Q) \leq \max(\text{deg}(P), \text{deg}(Q))$。

3. 多项式的欧几里得除法

与整数类似，欧几里得除法是一种用来找到两个多项式的商和余数的方法。给定两个多项式 $A(x)$ 和 $B(x)$ ，其中 $B(x)$ 不是零多项式，欧几里得除法可以表示为：

$$ A(x) = Q(x) \cdot B(x) + R(x) $$

其中 $Q(x)$ 是商多项式， $R(x)$ 是余数多项式，且 $R(x)$ 的次数小于 $B(x)$ 的次数。

若 $R(x) = 0$，那么我们称多项式 $B(x)$ 整除 $A(x)$，记为 $B|A$。此时， $B$ 也称为 $A$ 的因式，类似于整数中因子的概念。

计算多项式的欧几里得除法时，最常用的方法是多项式长除法，它类似整数的长除法。下面是计算 $x^3 -12x -42$ 除 $x-3$ 的过程，结果为 $x^2 -9x -27$ 余 $-123$：

最大公因式（Greatest Common Divisor，GCD）是两个多项式共有的最高次数的因式。通过欧几里得除法，我们可以找到两个多项式的最大公因式。

4. 质因式分解

多项式可以分解成多个多项式乘积的形式，这个过程被称为因式分解，它类似于整数的因子分解。因式分解有助于理解多项式的性质，比如根的分布等等。

举个例子， $3x^4 - 2x^2 - 5$ 可以被分解为 $(x^2+1)(3x^2-5)$。

如果（在给定的系数域上）一个多项式不能被表示为次数比它低的非零次多项式的乘积，就称它为不可约多项式，类似整数中素数的概念。质因式分解的目的就是将一个多项式 $P$ 分解为多个不可约多项式 $F_1, F_2, ..., F_k$：

$$ P = F_1 \cdot F_2 \cdot ... \cdot F_k $$

其中 $F_1, F_2, ..., F_k$ 也被称为多项式 $P$ 的质因式。

我们可以利用python中sympy包来进行质因式分解：

from sympy import symbols, factor

x = symbols('x')
polynomial = x**3 -4*x**2 - 11*x + 30

factored_polynomial = factor(polynomial)

print("原多项式:", polynomial)
print("质因式分解:", factored_polynomial)

# 输出
# 原多项式: x**3 - 10*x**2 + 31*x - 30
# 质因式分解: (x - 5)*(x - 3)*(x - 2)

在这个程序中，我们将 $x^3 -10x^2 + 31x - 30$ 分解为 $(x - 5)(x - 3)(x - 2)$。

5. 多项式的根

多项式 $P(x)$ 在 $x=b$ 处的取值为 $P(b) = \sum_{j=0}^{n}{a_jb^j}$。举个例子 $P(X) = x^3 -10x^2 + 31x - 30$，那么 $P(1) = 1 - 10 + 31 - 30 = -8$。

若 $P(b) = 0$，则我们称 $b$ 为多项式 $P$ 的根，也就是说，根就是使 $P(b) = 0$ 的 $b$ 的取值。一个 $n$ 阶多项式最多有 $n$ 个根。

我们常用因式分解来求多项式的根。例如 $P(x) = \sum_{j=0}^{n}{a_jx^j}$ 可以分解为 $(x - 5)(x - 3)(x - 2)$，那么 $x = 5, 3, 2$ 就是多项式 $P(x)$ 的根。这通常是一个计算困难的问题，没有有效的算法。

6. 拉格朗日插值法

拉格朗日插值是一种通过已知点构造插值多项式的方法。对于给定的 $n+1$ 个点 $(x_0, y_0), (x_1, y_1), \ldots, (x_n, y_n)$，拉格朗日插值多项式可以表示为：

$$ P(x) = \sum_{i=0}^{n} y_i \cdot \prod_{j=0, j\neq i}^{n} \frac{x - x_j}{x_i - x_j} $$

这个多项式被称为拉格朗日多项式，满足 $P(x_i) = y_i$ ，即通过已知点。给定 $n+1$ 个点，对应于它们的次数不超过n的拉格朗日多项式只有一个。

其中 $l(x) = \prod_{j=0, j\neq i}^{n} \frac{x - x_j}{x_i - x_j}$ 被称为基函数，它的特点是在 $x = x_i$ 的值为 $1$，而在 $x = x_j$（ $j \neq i$）的值为 $0$。容易验证拉格朗日多项式在 $x = x_i$ 的取值为 $y_j$，其中 $0 \leq j \leq n$。

我们可以利用python中sympy包来进行拉格朗日插值：

# 拉格朗日插值
from sympy import symbols
from sympy.abc import x
from sympy.polys.polyfuncs import interpolating_poly

# 给定的插值点和相应的函数值
data = [(1, 2), (2, 3), (3, 8)]

if isinstance(data, dict):
    X, Y = list(zip(*data.items()))
else:
    if isinstance(data[0], tuple):
        X, Y = list(zip(*data))
    else:
        X = list(range(1, n + 1))
        Y = list(data)

# 使用 lagrange 函数构造拉格朗日插值多项式
interpolation_polynomial = interpolating_poly(len(data_points), x, X, Y)

# 输出插值多项式
print("拉格朗日多项式:", interpolation_polynomial)
print("化简后的多项式:", interpolation_polynomial.expand())
# 通过插值多项式计算 x=4 的值
result = interpolation_polynomial.subs(x, 3)
print("在 x=4 的值:", result)

# 示例输出
# 拉格朗日多项式: (x - 3)*(x - 2) - 3*(x - 3)*(x - 1) + 4*(x - 2)*(x - 1)
# 化简后的多项式: 2*x**2 - 5*x + 5
# 在 x=4 的值: 8

在上面的程序中，我们给了3个点 $(1,2), (2,3), (3,8)$，拉格朗日插值得到的多项式为 $2x^2 - 5x + 5$。你可以验证一下它是否满足这3个点。

7. 总结

多项式数学是密码学和零知识证明中的重要工具。本讲介绍了多项式的基本定义、运算、质因式分解、和拉格朗日插值，为进一步学习多项式环打基础。