二次算术程序

RareSkills
发布于 2023-08-25 16:13
阅读 178

文章详细介绍了二次算术程序（QAP）的概念及其在零知识证明中的应用，特别是如何通过拉格朗日插值将Rank 1约束系统（R1CS）转换为QAP，并通过Schwartz-Zippel引理在O(1)时间内验证QAP的等式。

二次算术程序是一个 [算术电路](https://learnblockchain.cn/article/11317)，具体来说是一个 [等级 1 约束系统](https://learnblockchain.cn/article/11313) (R1CS)，表示为一组多项式。它是通过在等级 1 约束系统上使用拉格朗日插值法得出的。与 R1CS 不同，二次算术程序 (QAP) 可以通过施瓦茨-齐佩尔引理在 $\mathcal{O}(1)$ 时间内测试相等性。

### 关键思想

在施瓦茨-齐佩尔引理的章节中，我们看到我们可以通过将两个向量转换为多项式来测试它们是否相等，然后在多项式上运行施瓦茨-齐佩尔引理测试，测试是在 $\mathcal{O}(1)$ 时间内（需要说明的是，_测试_ 是 $\mathcal{O}(1)$ 时间，将向量转换为多项式会产生开销）。

由于等级 1 约束系统完全由向量运算组成，因此我们旨在测试

$$\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}\stackrel{?}{=}\mathbf{O}\mathbf{a}$$

是否在 $\mathcal{O}(1)$ 时间内成立，而不是在 $\mathcal{O}(n)$ 时间内（其中 $n$ 是 $\mathbf{L}$、$\mathbf{R}$ 和 $\mathbf{O}$ 中的行数）。

但在这之前，我们需要理解一些与表示它们的向量和多项式之间关系的关键属性。

在这里的所有数学中，我们假设工作在 [有限域](https://learnblockchain.cn/article/11315) 中，但为了简洁性，我们省略 $\mod p$ 符号。

### 向量加法与多项式加法之间的同态

#### 向量加法同态于多项式加法

如果我们取两个向量，用多项式对它们进行插值，然后将多项式相加，我们得到的多项式与我们先加向量再插值和向量所得到的多项式是相同的。

更数学地说，设 $\mathcal{L}(\mathbf{v})$ 是使用 $(1, 2, …, n)$ 作为 $x$ 值对向量 $\mathbf{v}$ 进行拉格朗日插值所得到的多项式，其中 $n$ 是向量 $\mathbf{v}$ 的长度。以下关系成立：

$$\mathcal{L}(\mathbf{v} + \mathbf{w}) = \mathcal{L}(\mathbf{v}) + \mathcal{L}(\mathbf{w})$$

换句话说，对向量 $\mathbf{v}$ 和 $\mathbf{w}$ 进行插值得到的多项式与对向量 $\mathbf{v} + \mathbf{w}$ 进行插值得到的多项式是相同的。

##### 实例示范

设 $f_1(x) = x^2$ 和 $f_2(x) = x^3$。$f_1$ 插值 $(1, 1), (2, 4), (3, 9)$ 或向量 $[1,4,9]$，而 $f_2$ 插值 $[1,8,27]$。

向量的和是 $[2,12,36]$，明显 $x^3 + x^2$ 插值该向量。设 $f_3(x) = f_1(x) + f_2(x) = x^3 + x^2$。

$$
\begin{align*} f_3(1) &= 1 + 1 = 2\\\ f_3(2) &= 8 + 4 = 12\\\ f_3(3) &= 27 + 9 = 36 \end{align*} 
$$

##### 用 Python 测试数学

对提出的数学恒等式进行单元测试并不会使其正确，但它确实阐明了正在发生的事情。鼓励读者尝试几个不同的向量以验证恒等式的成立。

```python
import galois
import numpy as np

p = 17
GF = galois.GF(p)

xs = GF(np.array([1,2,3]))

## 两个任意向量
v1 =  GF(np.array([4,8,2])) 
v2 =  GF(np.array([1,6,12]))

def L(v):
    return galois.lagrange_poly(xs, v)

assert L(v1 + v2) == L(v1) + L(v2)
```

#### 标量乘法

设 $\lambda$ 是一个标量（具体来说，是有限域中的一个域元素）。那么

$$\mathcal{L}(\lambda \mathbf{v}) = \lambda \mathcal{L}(\mathbf{v})$$

##### 实例示范

假设我们的 3 个点是 $[3, 6, 11]$。插值这个点的多项式是 $f(x) = x^2 + 2$。如果我们将向量乘以 3，我们得到 $[9, 18, 33]$。插值该向量的多项式是

```python
from scipy.interpolate import lagrange

x_values = [1, 2, 3]
y_values = [9, 18, 33]

print(lagrange(x_values, y_values))

##    2
## 3 x + 6
```

$3x^2 + 6$，与 $3 \cdot (x^2 + 2)$ 相等。

##### 代码中的实例示范

```python
import galois
import numpy as np

p = 17
GF = galois.GF(p)

xs = GF(np.array([1,2,3]))

## 任意向量
v =  GF(np.array([4,8,2]))

## 任意常数
lambda_ =  GF(15)

def L(v):
    return galois.lagrange_poly(xs, v)

assert L(lambda_ * v) == lambda_ * L(v)
```

#### 标量乘法实际上是向量加法

当我们说“向量乘以 3”时，我们实际上是说“将向量自身加三次”。由于我们只在有限域中工作，我们不担心标量例如“0.5”的解释。

我们可以将元素加法（在有限域中）下的两个向量看作与多项式下的加法（同样在有限域中）作为 [群](https://learnblockchain.cn/article/11320)。

这一章最重要的收获是：

**在有限域中，向量的加法群与多项式的加法群是同态的。**

这很重要，因为 **向量相等性测试需要 $\mathcal{O}(n)$ 时间，而多项式相等性测试需要 $\mathcal{O}(1)$ 时间。**

因此，在测试 R1CS 相等性时需要 $\mathcal{O}(n)$ 时间，我们可以利用这个同态在 $\mathcal{O}(1)$ 时间内测试 R1CS 的相等性。

这就是 _二次算术程序_。

### 一种多项式中的 Rank 1 约束系统

考虑到将矩阵与向量之间的乘法写成向量加法和标量乘法的形式。

例如，如果我们有一个 $3 \times 4$ 的矩阵 $A$ 和一个 4 维向量 $v$，那么我们可以将矩阵乘法写为：

$$ \mathbf{A} \cdot \mathbf{v} = \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14}\\\ a_{21} & a_{22} & a_{23} & a_{24}\\\ a_{31} & a_{32} & a_{33} & a_{34} \end{bmatrix} \begin{bmatrix} v_1\\\ v_2\\\ v_3\\\ v_4 \end{bmatrix} $$

我们通常认为向量 $v$ “翻转”并与每一行进行内积（广义点积），即：

$$ \mathbf{A}\cdot \mathbf{v} = \begin{bmatrix} a_{11}\cdot v_1 + a_{12}\cdot v_2 + a_{13}\cdot v_3 + a_{14}\cdot v_4\\\ a_{21}\cdot v_1 + a_{22}\cdot v_2 + a_{23}\cdot v_3 + a_{24}\cdot v_4\\\ a_{31}\cdot v_1 + a_{32}\cdot v_2 + a_{33}\cdot v_3 + a_{34}\cdot v_4 \end{bmatrix} $$

然而，我们可以考虑将矩阵 $A$ 拆分为一堆向量，如下所示：

$$ \mathbf{A} = \begin{bmatrix} a_{11} \\\ a_{21} \\\ a_{31} \end{bmatrix} , \begin{bmatrix} a_{12} \\\ a_{22} \\\ a_{32} \end{bmatrix} , \begin{bmatrix} a_{13} \\\ a_{23} \\\ a_{33} \end{bmatrix} , \begin{bmatrix} a_{14} \\\ a_{24} \\\ a_{34} \end{bmatrix} $$

并将每个向量乘以向量 $\mathbf{v}$ 中的一个标量：

$$ \mathbf{A}\cdot \mathbf{v} = \begin{bmatrix} a_{11} \\\ a_{21} \\\ a_{31} \end{bmatrix}\cdot v_1 + \begin{bmatrix} a_{12} \\\ a_{22} \\\ a_{32} \end{bmatrix}\cdot v_2 + \begin{bmatrix} a_{13} \\\ a_{23} \\\ a_{33} \end{bmatrix}\cdot v_3 + \begin{bmatrix} a_{14} \\\ a_{24} \\\ a_{34} \end{bmatrix}\cdot v_4 $$

我们已经将 $\mathbf{A}$ 与 $\mathbf{v}$ 之间的矩阵乘法完全用向量加法和标量乘法表示。

因为我们之前建立的在有限域中，向量的加法群与多项式的加法群是同态的，所以可以使用表示向量的多项式来表达上述计算。

### 简洁测试 $\mathbf{A}\mathbf{v}_1 = \mathbf{B}\mathbf{v}_2$

假设我们有矩阵 $\mathbf{A}$ 和 $\mathbf{B}$，那么

$$
\begin{align*} \mathbf{A} = \begin{bmatrix} 6 & 3\\\ 4 & 7\\\ \end{bmatrix}\\\ \mathbf{B} = \begin{bmatrix} 3 & 9 \\\ 12 & 6\\\ \end{bmatrix} \end{align*} 
$$

和向量 $\mathbf{v}_1$ 和 $\mathbf{v}_2$

$$
\begin{align*} \mathbf{v}_1 = \begin{bmatrix} 2 \\\ 4 \\\ \end{bmatrix}\\\ \mathbf{v}_2 = \begin{bmatrix} 2 \\\ 2 \\\ \end{bmatrix} \end{align*} 
$$

我们想要测试

$$
\mathbf{A}\mathbf{v}_1 = \mathbf{B}\mathbf{v}_2 
$$

是否为真。

显然我们可以进行矩阵运算，但最后的检查将需要 $n$ 次比较，其中 $n$ 是 $\mathbf{A}$ 和 $\mathbf{B}$ 中的行数。我们希望在 $\mathcal{O}(1)$ 时间内完成。

首先，我们将矩阵乘法 $\mathbf{A}\mathbf{v}_1$ 和 $\mathbf{B}\mathbf{v}_2$ 转换到向量加法群中：

$$
\begin{align*} \mathbf{A} &= \begin{bmatrix} 6 \\\ 4 \\\ \end{bmatrix} , \begin{bmatrix} 3 \\\ 7 \\\ \end{bmatrix}\\\ \mathbf{B} &= \begin{bmatrix} 3 \\\ 12 \\\ \end{bmatrix} , \begin{bmatrix} 9 \\\ 6 \\\ \end{bmatrix} \end{align*} 
$$

我们现在想找到以下同态等价：

$$
\begin{bmatrix} 6 \\\ 4 \\\ \end{bmatrix}\cdot 2 + \begin{bmatrix} 3 \\\ 7 \\\ \end{bmatrix}\cdot 4\stackrel{?}{=} \begin{bmatrix} 3 \\\ 12 \\\ \end{bmatrix}\cdot 2 + \begin{bmatrix} 9 \\\ 6 \\\ \end{bmatrix}\cdot 2 
$$

在多项式群中。

我们将每个向量转换为多项式，$x$ 值为 $[1,2]$：

$$
\underbrace{ \begin{bmatrix} 6 \\\ 4 \\\ \end{bmatrix}}_{p_1(x)}\cdot 2 + \underbrace{ \begin{bmatrix} 3 \\\ 7 \\\ \end{bmatrix}}_{p_2(x)}\cdot 4 \stackrel{?}{=} \underbrace{ \begin{bmatrix} 3 \\\ 12 \\\ \end{bmatrix}}_{q_1(x)}\cdot 2= \underbrace{ \begin{bmatrix} 9 \\\ 6 \\\ \end{bmatrix}}_{q_2(x)}\cdot 2 
$$

我们将调用一些 Python 来计算拉格朗日插值：

```python
import galois
import numpy as np

p = 17
GF = galois.GF(p)

x_values = GF(np.array([1, 2]))

def L(v):
    return galois.lagrange_poly(x_values, v)

p1 = L(GF(np.array([6, 4])))
p2 = L(GF(np.array([3, 7])))
q1 = L(GF(np.array([3, 12])))
q2 = L(GF(np.array([9, 6])))

print(p1)
## 15x + 8 (mod 17)
print(p2)
## 4x + 16 (mod 17)
print(q1)
## 9x + 11 (mod 17)
print(q2)
## 14x + 12 (mod 17)
```

最后，我们可以检查

$$p_1(x) \cdot 2+ p_2(x) \cdot 4 \stackrel{?}= q_1(x) \cdot 2 + q_2(x) \cdot 2$$

是否为真，通过调用施瓦茨-齐佩尔引理：

```python
import random
u = random.randint(0, p)
tau = GF(u) # 随机点

left_hand_side = p1(tau) * GF(2) + p2(tau) * GF(4)
right_hand_side = q1(tau) * GF(2) + q2(tau) * GF(2)

assert left_hand_side == right_hand_side
```

**最后的断言语句能够通过一次比较来测试 $\mathbf{A}\mathbf{v}_1 = \mathbf{B}\mathbf{v}_2$。**

### R1CS 到 QAP：简洁地测试 
$\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}=\mathbf{O}\mathbf{a}$

既然我们知道如何简洁地测试 $\mathbf{A}\mathbf{v}_1 = \mathbf{B}\mathbf{v}_2$，那么我们也可以简洁地测试 $\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}=\mathbf{O}\mathbf{a}$ 吗？

矩阵有 $m$ 列，因此让我们将每个矩阵拆成 $m...

二次算术程序是一个算术电路，具体来说是一个等级 1 约束系统 (R1CS)，表示为一组多项式。它是通过在等级 1 约束系统上使用拉格朗日插值法得出的。与 R1CS 不同，二次算术程序 (QAP) 可以通过施瓦茨-齐佩尔引理在 $\mathcal{O}(1)$ 时间内测试相等性。

关键思想

在施瓦茨-齐佩尔引理的章节中，我们看到我们可以通过将两个向量转换为多项式来测试它们是否相等，然后在多项式上运行施瓦茨-齐佩尔引理测试，测试是在 $\mathcal{O}(1)$ 时间内（需要说明的是，测试是 $\mathcal{O}(1)$ 时间，将向量转换为多项式会产生开销）。

由于等级 1 约束系统完全由向量运算组成，因此我们旨在测试

$$\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}\stackrel{?}{=}\mathbf{O}\mathbf{a}$$

是否在 $\mathcal{O}(1)$ 时间内成立，而不是在 $\mathcal{O}(n)$ 时间内（其中 $n$ 是 $\mathbf{L}$、$\mathbf{R}$ 和 $\mathbf{O}$ 中的行数）。

但在这之前，我们需要理解一些与表示它们的向量和多项式之间关系的关键属性。

在这里的所有数学中，我们假设工作在有限域中，但为了简洁性，我们省略 $\mod p$ 符号。

向量加法与多项式加法之间的同态

向量加法同态于多项式加法

如果我们取两个向量，用多项式对它们进行插值，然后将多项式相加，我们得到的多项式与我们先加向量再插值和向量所得到的多项式是相同的。

$$\mathcal{L}(\mathbf{v} + \mathbf{w}) = \mathcal{L}(\mathbf{v}) + \mathcal{L}(\mathbf{w})$$

换句话说，对向量 $\mathbf{v}$ 和 $\mathbf{w}$ 进行插值得到的多项式与对向量 $\mathbf{v} + \mathbf{w}$ 进行插值得到的多项式是相同的。

实例示范

设 $f_1(x) = x^2$ 和 $f_2(x) = x^3$。$f_1$ 插值 $(1, 1), (2, 4), (3, 9)$ 或向量 $[1,4,9]$，而 $f_2$ 插值 $[1,8,27]$。

向量的和是 $[2,12,36]$，明显 $x^3 + x^2$ 插值该向量。设 $f_3(x) = f_1(x) + f_2(x) = x^3 + x^2$。

$$ \begin{align} f_3(1) &= 1 + 1 = 2\\ f_3(2) &= 8 + 4 = 12\\ f_3(3) &= 27 + 9 = 36 \end{align} $$

用 Python 测试数学

对提出的数学恒等式进行单元测试并不会使其正确，但它确实阐明了正在发生的事情。鼓励读者尝试几个不同的向量以验证恒等式的成立。

import galois
import numpy as np

p = 17
GF = galois.GF(p)

xs = GF(np.array([1,2,3]))

## 两个任意向量
v1 =  GF(np.array([4,8,2])) 
v2 =  GF(np.array([1,6,12]))

def L(v):
    return galois.lagrange_poly(xs, v)

assert L(v1 + v2) == L(v1) + L(v2)

标量乘法

设 $\lambda$ 是一个标量（具体来说，是有限域中的一个域元素）。那么

$$\mathcal{L}(\lambda \mathbf{v}) = \lambda \mathcal{L}(\mathbf{v})$$

实例示范

假设我们的 3 个点是 $[3, 6, 11]$。插值这个点的多项式是 $f(x) = x^2 + 2$。如果我们将向量乘以 3，我们得到 $[9, 18, 33]$。插值该向量的多项式是

from scipy.interpolate import lagrange

x_values = [1, 2, 3]
y_values = [9, 18, 33]

print(lagrange(x_values, y_values))

##    2
## 3 x + 6

$3x^2 + 6$，与 $3 \cdot (x^2 + 2)$ 相等。

代码中的实例示范

import galois
import numpy as np

p = 17
GF = galois.GF(p)

xs = GF(np.array([1,2,3]))

## 任意向量
v =  GF(np.array([4,8,2]))

## 任意常数
lambda_ =  GF(15)

def L(v):
    return galois.lagrange_poly(xs, v)

assert L(lambda_ * v) == lambda_ * L(v)

标量乘法实际上是向量加法

当我们说“向量乘以 3”时，我们实际上是说“将向量自身加三次”。由于我们只在有限域中工作，我们不担心标量例如“0.5”的解释。

我们可以将元素加法（在有限域中）下的两个向量看作与多项式下的加法（同样在有限域中）作为群。

这一章最重要的收获是：

在有限域中，向量的加法群与多项式的加法群是同态的。

这很重要，因为 向量相等性测试需要 $\mathcal{O}(n)$ 时间，而多项式相等性测试需要 $\mathcal{O}(1)$ 时间。

因此，在测试 R1CS 相等性时需要 $\mathcal{O}(n)$ 时间，我们可以利用这个同态在 $\mathcal{O}(1)$ 时间内测试 R1CS 的相等性。

这就是 二次算术程序。

一种多项式中的 Rank 1 约束系统

考虑到将矩阵与向量之间的乘法写成向量加法和标量乘法的形式。

例如，如果我们有一个 $3 \times 4$ 的矩阵 $A$ 和一个 4 维向量 $v$，那么我们可以将矩阵乘法写为：

$$ \mathbf{A} \cdot \mathbf{v} = \begin{bmatrix} a{11} & a{12} & a{13} & a{14}\\ a{21} & a{22} & a{23} & a{24}\\ a{31} & a{32} & a{33} & a{34} \end{bmatrix} \begin{bmatrix} v_1\\ v_2\\ v_3\\ v_4 \end{bmatrix} $$

我们通常认为向量 $v$ “翻转”并与每一行进行内积（广义点积），即：

$$ \mathbf{A}\cdot \mathbf{v} = \begin{bmatrix} a_{11}\cdot v1 + a{12}\cdot v2 + a{13}\cdot v3 + a{14}\cdot v4\\ a{21}\cdot v1 + a{22}\cdot v2 + a{23}\cdot v3 + a{24}\cdot v4\\ a{31}\cdot v1 + a{32}\cdot v2 + a{33}\cdot v3 + a{34}\cdot v_4 \end{bmatrix} $$

然而，我们可以考虑将矩阵 $A$ 拆分为一堆向量，如下所示：

$$ \mathbf{A} = \begin{bmatrix} a{11} \\ a{21} \\ a{31} \end{bmatrix} , \begin{bmatrix} a{12} \\ a{22} \\ a{32} \end{bmatrix} , \begin{bmatrix} a{13} \\ a{23} \\ a{33} \end{bmatrix} , \begin{bmatrix} a{14} \\ a{24} \\ a{34} \end{bmatrix} $$

并将每个向量乘以向量 $\mathbf{v}$ 中的一个标量：

$$ \mathbf{A}\cdot \mathbf{v} = \begin{bmatrix} a{11} \\ a{21} \\ a_{31} \end{bmatrix}\cdot v1 + \begin{bmatrix} a{12} \\ a{22} \\ a{32} \end{bmatrix}\cdot v2 + \begin{bmatrix} a{13} \\ a{23} \\ a{33} \end{bmatrix}\cdot v3 + \begin{bmatrix} a{14} \\ a{24} \\ a{34} \end{bmatrix}\cdot v_4 $$

我们已经将 $\mathbf{A}$ 与 $\mathbf{v}$ 之间的矩阵乘法完全用向量加法和标量乘法表示。

因为我们之前建立的在有限域中，向量的加法群与多项式的加法群是同态的，所以可以使用表示向量的多项式来表达上述计算。

简洁测试 $\mathbf{A}\mathbf{v}_1 = \mathbf{B}\mathbf{v}_2$

假设我们有矩阵 $\mathbf{A}$ 和 $\mathbf{B}$，那么

$$ \begin{align} \mathbf{A} = \begin{bmatrix} 6 & 3\\ 4 & 7\\ \end{bmatrix}\\ \mathbf{B} = \begin{bmatrix} 3 & 9 \\ 12 & 6\\ \end{bmatrix} \end{align} $$

和向量 $\mathbf{v}_1$ 和 $\mathbf{v}_2$

$$ \begin{align} \mathbf{v}_1 = \begin{bmatrix} 2 \\ 4 \\ \end{bmatrix}\\ \mathbf{v}_2 = \begin{bmatrix} 2 \\ 2 \\ \end{bmatrix} \end{align} $$

我们想要测试

$$ \mathbf{A}\mathbf{v}_1 = \mathbf{B}\mathbf{v}_2 $$

是否为真。

显然我们可以进行矩阵运算，但最后的检查将需要 $n$ 次比较，其中 $n$ 是 $\mathbf{A}$ 和 $\mathbf{B}$ 中的行数。我们希望在 $\mathcal{O}(1)$ 时间内完成。

首先，我们将矩阵乘法 $\mathbf{A}\mathbf{v}_1$ 和 $\mathbf{B}\mathbf{v}_2$ 转换到向量加法群中：

$$ \begin{align} \mathbf{A} &= \begin{bmatrix} 6 \\ 4 \\ \end{bmatrix} , \begin{bmatrix} 3 \\ 7 \\ \end{bmatrix}\\ \mathbf{B} &= \begin{bmatrix} 3 \\ 12 \\ \end{bmatrix} , \begin{bmatrix} 9 \\ 6 \\ \end{bmatrix} \end{align} $$

我们现在想找到以下同态等价：

$$ \begin{bmatrix} 6 \\ 4 \\ \end{bmatrix}\cdot 2 + \begin{bmatrix} 3 \\ 7 \\ \end{bmatrix}\cdot 4\stackrel{?}{=} \begin{bmatrix} 3 \\ 12 \\ \end{bmatrix}\cdot 2 + \begin{bmatrix} 9 \\ 6 \\ \end{bmatrix}\cdot 2 $$

在多项式群中。

我们将每个向量转换为多项式，$x$ 值为 $[1,2]$：

$$ \underbrace{ \begin{bmatrix} 6 \\ 4 \\ \end{bmatrix}}_{p1(x)}\cdot 2 + \underbrace{ \begin{bmatrix} 3 \\ 7 \\ \end{bmatrix}}{p2(x)}\cdot 4 \stackrel{?}{=} \underbrace{ \begin{bmatrix} 3 \\ 12 \\ \end{bmatrix}}{q1(x)}\cdot 2= \underbrace{ \begin{bmatrix} 9 \\ 6 \\ \end{bmatrix}}{q_2(x)}\cdot 2 $$

我们将调用一些 Python 来计算拉格朗日插值：

import galois
import numpy as np

p = 17
GF = galois.GF(p)

x_values = GF(np.array([1, 2]))

def L(v):
    return galois.lagrange_poly(x_values, v)

p1 = L(GF(np.array([6, 4])))
p2 = L(GF(np.array([3, 7])))
q1 = L(GF(np.array([3, 12])))
q2 = L(GF(np.array([9, 6])))

print(p1)
## 15x + 8 (mod 17)
print(p2)
## 4x + 16 (mod 17)
print(q1)
## 9x + 11 (mod 17)
print(q2)
## 14x + 12 (mod 17)

最后，我们可以检查

$$p_1(x) \cdot 2+ p_2(x) \cdot 4 \stackrel{?}= q_1(x) \cdot 2 + q_2(x) \cdot 2$$

是否为真，通过调用施瓦茨-齐佩尔引理：

import random
u = random.randint(0, p)
tau = GF(u) # 随机点

left_hand_side = p1(tau) * GF(2) + p2(tau) * GF(4)
right_hand_side = q1(tau) * GF(2) + q2(tau) * GF(2)

assert left_hand_side == right_hand_side

最后的断言语句能够通过一次比较来测试 $\mathbf{A}\mathbf{v}_1 = \mathbf{B}\mathbf{v}_2$。