24.多项式基础

文档摘要

title: 24. 多项式基础 tags: zk abstract algebra polynomials WTF zk 教程第 24 讲：多项式基础这一讲，我们将学习多项式基础，为学习多项式环做铺垫。在密码学和零知识证明中，多项式数学是一个重要而强大的工具。多项式基础在代数学中，一个多项式是由变量和系数通过有限次加法、乘法以及自然数幂次的乘方运算得到的代数表达式。一个 $n$ 次多项式 $P(x)$ 可以表示为： $$ P(x) = \sum{j=0}^{n}{ajx^j} = anx^n + a{n-1}x^{n-1} + ... + a1x + a0 $$ 其中， $an, a{n-1}, \ldots, a1, a0$ 是多项式的系数， $x$ 是变量，而指数为非负整数。


title: 24. 多项式基础
tags:
  - 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 是变量，而指数为非负整数。系数可以是整数、实数、复数或其他数域中的元素。但是为了简单起见，我们先把系数限制为整数。

一些多项式的常用概念：

次数（degree）：一个多项式的次数是指最高次幂的指数，也就是 n（其中 a_n \neq 0）。比如，P(x) = 3x^4 - 2x^2 + 5 的次数是4。我们常用 \deg(P) 表示多项式 P(x) 的次数。
首项系数（leading coefficient）：具有最高次幂的项的系数 a_n 被称为首项系数，记为 Lc(P) = a_n
零多项式：所有系数都为零的多项式。它的表示形式为 P(x) = 0。
一多项式： a_0 = 1，剩下系数都为零的多项式。它的表示形式为 P(x) = 1。
零次多项式（非零常数）：除了常数项以外所有系数都为零的多项式。它的表示形式为 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. 总结

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