用于 ZK 证明的有限域与模运算

Last updated on Mar 10, 2026

本文是系列文章的第三篇。我们将在零知识证明电路的背景下介绍有限域。前两章分别是 P vs NP 及其在零知识证明中的应用和算术电路。

在关于算术电路的上一章中，我们指出过一个局限性：我们无法对数字 $2/3$ 进行编码，因为它无法用二进制精确表示。我们还指出过，我们没有明确的方法来处理溢出（overflow）。

这两个问题都可以通过一种在一般密码学中很流行的算术变体来无缝处理，它被称为有限域（finite fields）。

有限域

给定一个素数 p，我们可以通过取整数集合 $\set{0, 1, 2, …, p-1}$ 并定义加法和乘法在模 $p$ 的情况下进行，来构建一个包含 p 个元素的有限域。我们将首先将自己限制在元素个数为素数的域中。

例如，如果素数 $p$ 是 $7$ ，那么有限域中的元素就是 $\set{0, 1, 2, 3, 4, 5, 6}$ 。任何超出此范围的数字（ $≥ p$ 或 $< 0$ ）总是通过模运算映射到该范围内的一个“等价”数字。“等价”的专业术语是同余（congruent）。

模运算计算的是数字除以素数时的余数。例如，如果我们的模是 7，数字 12 同余于 5，即 $12 \pmod 7 = 5$ ，数字 14 同余于 0。同样地，当我们把两个数字相加时，比如 3 + 5，得到的和 8 同余于 1（8 mod 7 = 1）。下面的动画说明了这一点：

在 Python 中，上述计算可以通过以下方式计算：

p = 7
result = (3 + 5) % p
print(result) # prints 1

在本章中，无论何时执行计算，我们都将结果表示为 $0…(p-1)$ 范围内的数字，即我们的有限域 p 中的元素集合。例如，2 * 5 = 10，我们将其“化简”为 3（模 7）。

注意 3 + 5 是如何“溢出” 6 这个限制的。在有限域中，溢出并不是一件坏事，我们将溢出行为定义为计算的一部分。 在模 7 的有限域中，5 + 3 被定义为 1。

下溢（Underflows）的处理方式也类似。例如， $3 - 5 = - 2$ ，但在模 7 中我们得到 $5$ ，因为 $7 - 2 = 5$ 。

模算术的工作原理

在典型的编程语言中，我们将有限域中的加法写为 (6 + 1) % 7 == 0，但在数学符号中，我们通常表示为

0 = 6 + 1 \pmod 7

或者更一般地说，

c = a + b \pmod p

其中 $a$ 和 $b$ 是有限域中的数字， $c$ 是将任何 $≥ p$ 且 $< 0$ 的数字映射回集合 $\set{0, 1, …, p - 1}$ 的余数。

符号 $\pmod p$ 意味着所有算术运算都在模 $p$ 下进行。例如，

a + b = c + d \pmod p

等价于（在 Python 或 C 中）(a + b) % p == (c + d) % p。

乘法的工作原理类似，先将数字相乘，然后取模：

3 = 4 × 6 \pmod 7 = 24 \pmod 7 = 3

上面的乘法运算可以通过两种方式进行可视化：

或者：

我们将有限域中的数字称为“元素（element）”。

$p$ 与域的阶

我们用来取模的数字称为 $p$ 。在我们所有的例子中，它都是一个素数。在更广泛的数学领域中， $p$ 不一定是素数，但我们只关注 $p$ 为素数的情况。

由于这个限制，域的阶（order）总是等于 $p$ 。阶是域中元素的数量。我们用来取模的数字的通用术语是域的特征（characteristic）。

例如，如果我们有 $p = 5$ ，元素就是 $\set{0, 1, 2, 3, 4}$ 。有 5 个元素，所以该域的阶是 5。

$p$ 的加法恒等式

任何元素加上 $p$ 等于该元素本身。例如， $(3 + 7) \pmod 7 = 3$ 。请考虑以下动画中的示例：

加法逆元

考虑 $5 + (-5) = 0$ 。

在数学中， $a$ 的加法逆元是一个数字 $b$ ，使得 $a + b = 0$ 。通常，我们通过在数字前面加一个负号来表示它的加法逆元。根据定义， $-a$ 就是与 $a$ 相加得到 0 的数字。

加法逆元的一般规则

零的加法逆元是它自己。
每个数字都有且仅有一个加法逆元。

这些加法逆元规则同样适用于有限域。虽然我们没有带有负号的元素（比如 $-5$ ），但在使用模运算符时，某些元素相互之间可以“表现得”像负数。

在常规算术中， $-5$ 是与 $5$ 相加结果为 $0$ 的数字。如果我们的有限域是 $p = 7$ ，那么 $2$ 可以被认为是 $-5$ ，因为 $(5 + 2) \pmod 7 = 0$ 。类似地， $5$ 也可以被认为是 $-2$ ，因为它们互为加法逆元。准确地说， $-2$ 同余于 $5$ ，或者 $-2 \equiv 5 \pmod 7$ 。

要计算一个元素的加法逆元，只需计算 $p - a$ ，其中 $a$ 是我们试图求其加法逆元的元素。例如，要找到 14 模 23 的加法逆元，我们计算 $23 - 14 = 9$ 。我们可以看到 $14 + 9 \pmod {23} = 0$ 。 $p$ 同余于零，所以这等价于将 $-5$ 计算为 $0 - 5$ 。

就像实数一样：

有限域中的每个元素都有且仅有一个加法逆元
零的加法逆元是它自己。

在有限域中，加法逆元的一般规律是，有限域前半部分的元素是后半部分元素的加法逆元，如下图所示。零是例外，因为它的加法逆元是它本身。在 $p = 7$ 的域中，由绿线连接的数字互为加法逆元：

练习： 假设我们选择一个 $p \geq 3$ 。哪些非零值（如果有的话）的加法逆元是它们自己？

乘法逆元

考虑 $5 × (1/5) = 1$ 。

$a$ 的乘法逆元是一个数字 $b$ ，使得 $ab = 1$ 。除了零以外，每个元素都有一个乘法逆元。在“常规数字”中，乘法逆元是 $1 / \text{num}$ 。例如， $5$ 的乘法逆元是 $1/5$ ， $19$ 的乘法逆元是 $1/19$ 。

虽然在有限域中我们没有分数，但我们仍然可以找到一对数字，当它们相加或相乘时，“表现得像”分数。

例如，在有限域 $p = 7$ 中， $4$ 的乘法逆元是 $2$ ，因为 $4 * 2 = 8$ ，并且 $8 \pmod 7 = 1$ 。因此，在有限域中， $2$ “表现得像” $1/4$ ，准确地说， $1/4$ 同余于 $2 \pmod 7$ 。

有限域算术中乘法逆元的一般规则：

0 没有乘法逆元
1 的乘法逆元是它自己
每个数字（除 0 以外）都有且仅有一个乘法逆元（可能是它自己）
值为 $(p - 1)$ 的元素的乘法逆元是它自己。例如在 $p = 103$ 的有限域中， $1$ 和 $102$ 的乘法逆元是它们自己。在 $p = 23$ 的有限域中， $1$ 和 $22$ 的乘法逆元是它们自己（原因将在下一节解释）。另一个例子：在模 5 的有限域中，1 的逆元是它自己，4 的逆元也是它自己。 $4 \times 4 = 16$ ，而 $16 \pmod 5 = 1$ 。

为什么值为 $p - 1$ 的元素的乘法逆元是它自己

当我们将 $-1$ 乘以它本身时，我们得到 $1$ 。因此，对于实数， $-1$ 的乘法逆元是它自己。值为 $(p - 1)$ 的元素同余于 $-1$ 。因此，我们预期 $(p - 1)$ 的乘法逆元是它自己，事实也的确如此。

另一种理解为什么 $p - 1$ 的乘法逆元是它自己的方法是，考虑 $(p - 1)(p - 1) = p² - 2p + 1$ 。由于 $p$ 同余于 $0$ ，所以 $p² - 2p + 1$ 可以简化为 $0^2 - 2*0 + 1 = 1$ 。

有限域上算术电路的解

如果我们考虑以下常规数字上的算术电路，我们预期 x = -1 是唯一的满足赋值（satisfying assignment）。

x * x === 1
x + 1 === 0

在有限域中，满足赋值是同余于 $-1$ 的元素，即 $p - 1$ 。

用费马小定理计算乘法逆元

费马小定理指出

a^{p}=a\pmod p, a\neq0

换句话说，如果将一个非零元素的 $p$ 次方，你会重新得到该元素。一些例子：

$3⁵ \pmod 5 = 3$
$4⁷ \pmod 7 = 4$
$14⁵³ \pmod {53} = 14$

现在考虑如果我们将 $aᵖ = a \pmod p$ 的两边都除以 $a$ （记住， $a ≠ 0$ ）：

a^p=a

\frac{a^p}{a}=\frac{a}{a}

a^{p-1}=1

我们可以将结果写成

a(a^{p-2}) = 1

这意味着 $aᵖ⁻² \pmod p$ 是 $a$ 的乘法逆元，因为 $a$ 乘以 $aᵖ⁻²$ 等于 1。

一些例子：

在有限域 $p = 7$ 中， $3$ 的乘法逆元是 $5$ 。 $3⁷⁻² = 5 \pmod 7$
在有限域 $p = 11$ 中，8 的乘法逆元是 $7$ 。 $8¹¹⁻² = 7 \pmod {11}$

这种方法的优点是我们可以使用 Ethereum 中的预编译合约（precompile） expmod 来在智能合约中计算模逆。

在实践中，这并不是计算乘法逆元的理想方法，因为将一个数进行大幂次运算在计算上非常昂贵。计算乘法逆元的底层库使用了更高效的算法。然而，当没有这样的库可用，并且你需要一个快速简单的解决方案，而且计算大指数不会过于昂贵时，就可以使用费马小定理。

用 Python 计算乘法逆元

使用 Python 3.8 或更高版本，我们可以通过执行 pow(a, -1, p) 来计算有限域 p 中 a 的乘法逆元。pow 的第一个参数是底数，第二个是指数，第三个是模数。

示例：

p = 17
print(pow(5, -1, p))
# 7
assert (5 * 7) % p == 1

练习： 求 3 模 5 的乘法逆元。一共只有 5 种可能性，试着遍历所有可能性，看看哪一个有效。

练习： 在有限域 $p = 51$ 中，50 的乘法逆元是什么？你不需要使用 Python 来计算，请参考“乘法逆元的一般规则”中描述的原理。

练习： 使用 Python 计算在有限域 p = 311 中 288 的乘法逆元。你可以通过验证 (288 * answer) % 311 == 1 来检查你的结果。

乘法逆元的加法与“常规”分数的加法是一致的

在 p = 7 的有限域中，数字 2 和 4 互为乘法逆元，因为 $(2 \times 4) \pmod 7 = 1$ 。这意味着在有限域 $p = 7$ 中， $4$ 同余于 $1/2$ ，且 $2$ 同余于 $1/4$ 。

我们说在有限域 $p = 7$ 中 $4$ 同余于 $1/2$ ，因为 $2 \times \mathsf{mul\_inv}(2) = 1$ 。在这个有限域中 $2$ 的乘法逆元是 $4$ ，所以我们可以把 $4$ 当作 $1/2$ 来看待。

在实数中，如果我们把 $1/2 + 1/2$ 相加，我们期望得到 $1$ 。同样的事情也发生在有限域中。由于 $4$ “表现得像” $1/2$ ，我们预期 $4 + 4 \pmod 7 = 1$ ，事实也的确如此。

我们可以通过将数字 $5/6$ 视为操作 $5 * (1/6)$ ，或 $5 \times \mathsf{mul\_inv}(6)$ ，将其编码在有限域中。

考虑 $1/2 + 1/3 = 5/6$ 。如果我们的有限域是 $p = 7$ ，那么 $1/2$ 就是 $2$ 的乘法逆元， $1/3$ 是 3 的乘法逆元， $5/6$ 是 $5$ 乘以 6 的乘法逆元：

p = 7
one_half = pow(2, -1, p)
one_third = pow(3, -1, p)
five_over_six = (pow(6, -1, p) * 5) % p

assert (one_half + one_third) % p == five_over_six
# True

在有限域中计算“分数”的通用方法是分子乘以分母的乘法逆元，再对 p 取模：

def compute_field_element_from_fraction(num, den, p):
	inv_den = pow(den, -1, p)
	return (num * inv_den) % p

当分母是 p 的倍数时，就不可能这样做。例如， $1/7$ 无法在有限域 $p = 7$ 中表示，因为 pow(7, -1, 7) 没有解。模运算是取除法后的余数， $7/7$ 的余数是零，或者更一般地说，当 $d$ 是 $7$ 的倍数时， $7/d$ 是零。乘法逆元意味着我们可以将一个数字与其逆元相乘得到 $1$ ，但如果其中一个数字是零，我们就无法用任何东西乘以零来得到 1。

练习： 在 Python 中运行 pow(7, -1, 7)。你应该会看到抛出异常 ValueError: base is not invertible for the given modulus。 $7$ mod $7$ 等于零。我们无法用任何东西乘以零来得到 $1$ 。

有限域“除法”不存在精度损失

如果在大多数编程语言中进行 1 / 3 的除法，我们将遭受精度损失，因为 $0.\overline{3}$ 无法用二进制表示。

然而，在有限域中，1 / 3 就是 3 的乘法逆元。

这意味着在有限域中进行算术电路

x + y + z === 1;
x === y;
y === z;

时会有一个精确的解。如果我们在算术电路中使用定点数或浮点数作为数据类型，这是不可能可靠地做到的（试想将 0.33333 + 0.33333 + 0.33333 相加会导致 0.99999 而不是 1）。

下面的 Python 实现说明了这个电路：

p = 11

# x, y, z have value 1/3
x = pow(3, -1, 11)
y = pow(3, -1, 11)
z = pow(3, -1, 11)

assert x == y;
assert y == z;
assert (x + y + z) % p == 1

有限域元素没有传统的“偶数”或“奇数”概念

如果一个数可以被 2 除尽且没有余数，我们称它为“偶数”。

在有限域中，任何元素都可以被 2 除尽而没有余数。

也就是说，“除以 2”实际上是乘以 2 的乘法逆元，这总是会产生另一个域元素，而不会有“余数”。

然而，如果我们有该域元素的二进制表示，那么如果我们将其转换为整数，我们就可以检查该元素是偶数还是奇数。如果最低有效位（least significant bit）是 1，则该数字为奇数（如果是将其解释为整数，而不是有限域元素）。

Python 中的有限域库

因为在 Python 中不断写 pow 和 % p 会有些繁琐，读者可能希望改用 galois library（有限域有时被称为 Galois 域，发音为“Gal-wah”）。可以通过 python3 -m pip install galois 进行安装。

下面，我们将上一节中分数加法的代码 $(1/2 + 1/3 = 5/6)$ 转换为使用 galois 库。该库重写了数学运算符，使其可以在有限域中工作：

import galois
GF7 = galois.GF(7) # GF7 is a class that wraps 7

one_half = GF7(1) / GF7(2)
one_third = GF7(1) / GF7(3)
five_over_six = GF7(5) / GF7(6)

assert one_half + one_third == five_over_six

运算 1 / GF(a) 会计算 a 的乘法逆元。

galois 库可以通过在前面加上一个负号来计算加法逆元：

negative_two = -GF7(2)
assert negative_two + GF7(2) == 0

分数的乘法也是一致的

让我们在这个例子中使用有限域 p = 11。

在常规数字中，我们知道 $1/3 * 1/2 = 1/6$ 。

让我们在有限域中执行相同的运算：


import galois
GF = galois.GF(11)

one_third = GF(1) / GF(3)
one_half = GF(1) / GF(2)
one_sixth = GF(1) / GF(6)

assert one_third * one_half == one_sixth

练习： 使用 galois 库验证在有限域 $p = 17$ 中， $3/4 * 1/2 = 3/8$ 。

对于所有非零 a, b，a × b ≠ 0

在有限域中，任何两个元素相乘都不会得到零，除非其中一个元素本身就是零。这对于常规数字也是成立的。

为了理解这一点，考虑有限域 $p = 7$ 。为了将两个数字相乘并得到结果为 $0$ ，那么其中一项 $a$ 需要是 7 的倍数，以便 $a \pmod 7$ 为零。然而， $\set{0, 1, 2, 3, 5, 6}$ 中没有一个是 7 的倍数，所以这种情况不可能发生。

当我们设计算术电路时，我们会经常参考这个事实。例如，如果我们知道

x₁ * x₂ * ... * xₙ ≠ 0

那么我们就可以确信所有变量 x₁, x₂, xₙ 都是非零的——即使我们不知道它们的值。

下面说明我们如何将这个技巧用于一个现实的算术电路。假设我们有信号 x₁, x₂, x₃。我们希望约束这些信号中至少有一个值为 8，而不指定具体是哪一个。首先，我们计算我们所在域中 8 的加法逆元 a_inv(8)。然后我们执行：

(x₁ + a_inv(8))(x₂ + a_inv(8))(x₃ + a_inv(8)) === 0

它可以写成

(x₁ - 8)(x₂ - 8)(x₃ - 8) === 0

这里的理解是，-8 是我们有限域中 8 的加法逆元。

只要其中一个信号的值为 8，那么该项就为零，并且整个表达式相乘也会为零。这个技巧依赖于两个事实：

如果所有项都不为零，那么该表达式的值是不可能为零的
8 的加法逆元是唯一的，而且 8 是 8 的加法逆元的唯一加法逆元。换句话说，除了 8 以外，没有任何值可以使得 8 + inv(8) 等于零。

因此，算术电路 (x₁ + a_inv(8))(x₂ + a_inv(8))(x₃ + a_inv(8)) === 0 表明 x₁, x₂, xₙ 中至少有一个的值是 8。

有限域运算满足结合律、交换律和分配律

就像常规数学一样，在模算术中，结合律、交换律和分配律也是成立的，即：

结合律

$(a + b) + c = a + (b + c) \pmod p$

加法交换律

$(a + b) = (b + a) \pmod p$

乘法交换律

$ab = ba \pmod p$

分配律

$a(b + c) = ab + ac \pmod p$

模平方根

在“常规数学”中，完全平方数有整数平方根。例如，25 的平方根是 5，49 的平方根是 7，以此类推。

有限域中的元素不需要是完全平方数也有平方根

考虑 $5 × 5 \pmod {11} = 3$ 。这意味着在模 11 的情况下，3 的平方根是 5。由于有限域的环绕（wrap around）特性，有限域元素不需要是完全平方数也能拥有平方根。

就像常规平方根有两个解（一正一负）一样，有限域中的模平方根也有两个解。例外的是元素 0，它只有 0 作为其平方根。

在模 11 的有限域中，以下元素具有平方根：

元素	第一个平方根	第二个平方根
0	0	n/a
1	1	10
3	5	6
4	2	9
5	4	7
9	3	8

练习：在模 11 的有限域中，验证表中声明的平方根是否正确。

观察发现，第二个平方根总是第一个平方根的加法逆元，就像实数一样。

例如：

在常规数学中， $9$ 的平方根是 $3$ 和 $-3$ ，这两者互为加法逆元。
在 $p = 11$ 的有限域中，9 的平方根是 3 和 8。8 是 3 的加法逆元，因为 $8 + 3 \pmod {11}$ 为 $0$ ，正如 $3$ 是 $-3$ 的加法逆元一样。

元素 2、6、7、8 和 10 在有限域 $p = 11$ 中没有模平方根。这可以通过将 0 到 10 之间的每个元素平方来发现，你会发现 2、6、7、8 和 10 永远不会被生成。

numbers_with_roots = set()
p = 11
for i in range(0, p):
    numbers_with_roots.add(i * i % p)

print("numbers_with_roots:", numbers_with_roots)
# numbers_with_roots: {0, 1, 3, 4, 5, 9}

请注意，3 不是一个完全平方数，但在该有限域中它确实有一个平方根。

计算模平方根

可以使用 Python 中的 libnum library 来计算模平方根。下面，我们计算 5 模 11 的平方根。对于我们的需求，函数 has_sqrtmod_prime_power 和 sqrtmod_prime_power 的第三个参数可以设置为 1。

# install libnum with `python -m pip install libnum`

from libnum import has_sqrtmod_prime_power, sqrtmod_prime_power
has_sqrtmod_prime_power(5, 11, 1) # True
list(sqrtmod_prime_power(5, 11, 1)) # [4, 7]
# square roots generally have two solutions. 4 and 7 are the square roots of 5 (mod 11)

当 p 可以写为 4k + 3（其中 k 为整数）时，模平方根可以通过以下方式计算：

def mod_sqrt(x, p):
	assert (p - 3) % 4 == 0, "prime not 4k + 3"
	exponent = (p + 1) // 4
	return pow(x, exponent, p) # x ^ e % p

上面的函数返回 x 模 p 的其中一个平方根。另一个平方根可以通过计算返回值的加法逆元得出。如果素数不是 4k + 3 的形式，则必须使用 Tonelli-Shanks 算法来计算模平方根（上面的 libnum 库就实现了该算法）。

其含义是算术电路 x * x === y 可能有两个解。 例如，在有限域 p = 11 中，似乎算术电路 x * x === 4 只允许值 2，因为 -2 不是一个有限域元素。然而，这个假设大错特错！赋值 x = 9（同余于 -2）同样满足该电路。

练习： 使用上面的代码片段在有限域 p = 19 中计算 5 的模平方根。代码只会给你其中一个答案。你该如何计算另一个？

有限域中的线性方程组

如上一章所述，算术电路本质上是一个方程组。有限域中的线性方程组与常规数字上的线性方程组共享许多属性。然而，存在一些最初可能会出乎意料的差异。由于算术电路是在有限域上计算的，我们必须了解这些令人惊讶的偏差可能发生在哪里。

线性方程组是一组包含一系列未知数（变量）的直线方程的集合，我们试图同时求解它们。要找到线性方程组的唯一解，我们必须为每个变量找到一个数值，使该数值能够同时满足系统中的所有方程。

实数的线性方程组要么有：

无解： 意味着这两个方程代表二维中平行的直线，或者在三维及更高维度中永远不会相交

一个解： 意味着直线在一个点相交

无数解： 如果两个方程代表同一条直线，那么就有无数个交点，该线性方程组就有无数个解。

有限域方程组同样会有

无解，或
一个解，或
$p$ 个解，即解的数量与域的阶一样多。

然而，仅仅因为实数域上的一个线性方程组有零个、一个或无数个解，它并不意味着在有限域上的同一个线性方程组也会有零个、一个或 p 个解。

我们强调这一点的原因是，我们使用算术电路和信号赋值来对 NP 问题的解进行编码。然而，因为算术电路是用有限域编码的，我们最终的编码方式可能无法捕捉到我们试图建模的方程的行为。

以下三个例子说明了当在一个有限域上执行时，方程组的行为会发生怎样的变化。

示例 1：在常规数字上有一个解的方程组，在有限域中可能有 `p` 个解

例如，我们绘制：

x+2y=1

6x+y=6

在实数中它有一个解： $(1, 0)$ ，但在有限域 $p = 11$ 上，它有 11 个解： $\set{(0, 6), (1, 0), (2, 5), (3, 10), (4, 4), (5, 9), (6, 3), (7, 8), (8, 2), (9, 7), (10, 1)}$ 。

不要假设在实数域中有单一解的方程组（算术电路）在有限域中也会有单一解！

下面我们绘制出这些方程组在有限域上的解，以说明这两个方程“处处相交”，也就是说，具有满足这两个方程的相同点集：

这可能看起来极其违反直觉——让我们看看它是如何发生的。如果我们对原始方程求解：

x+2y=1

6x+y=6

得到 $y$ ：

y = 1/2 - 1/2*x

y=6-6x

$1/2$ 是 $2$ 的乘法逆元。在 $p = 11$ 的有限域中， $6$ 是 $2$ 的乘法逆元，即 $2 * 6 \pmod {11} = 1$ 。因此，在有限域 $p = 11$ 中， $x + 2y = 1$ 和 $6x + y = 6$ 实际上是同一个方程。也就是说，方程 $y = 1/2 - 1/2x$ 在被编码进有限域时，变成了 $y = \mathsf{mul\_inv}(2) - \mathsf{mul\_inv}(2)x$ ，也就是 $y = 6 - 6x$ ，这与方程组中的另一个方程是相同的。

示例 2：在常规数字上有一个解的方程组，在有限域中可能无解

同样反直觉的是，在实数上有单一解的方程组在有限域中可能无解：

x + 2y=1

7x+3y=2

显然，这个方程组有一个交点，但在有限域上它没有解。

下面我们展示这两个方程在有限域中的分布图：

练习： 编写代码暴力破解在 x = 0..10, y = 0..10 上的每一个 (x, y) 组合，以验证上述方程组在 p = 11 的有限域上无解。

为什么这个方程组在有限域 $p = 11$ 中没有解呢？

如果在实数上求解

x + 2y=1

7x+3y=2

我们得到的解是

x = \frac{1}{11},\space y=\frac{5}{11}

上述分数在有限域 p = 11 中没有同余的元素。

回想一下，除以一个数字等价于乘以它的乘法逆元。此外，回想一下，域的阶（在此例中为 11）将没有乘法逆元，因为域的阶同余于 0。

a 的乘法逆元是使得 a * b = 1 的值 b。然而，如果 a = 0（或任何与之同余的值），那么 b 就没有解。因此，我们为实数解写下的表达式无法转化为有限域中的元素。

因此，上述解 (x, y) 并不是有限域的一部分。所以在有限域 p = 11 中，x + 2y = 1 和 7x + 3y = 2 是平行线。

换个角度来看，我们可以通过求解方程中的 y 得到：

y = 1/2 - x/2

y=2/3-7x/3

我们在上一节中看到 6 是 2 的乘法逆元，所以第一个方程的“斜率”为 -1/2，在有限域中即为 -6 或等价的 5。在第二个方程中，我们通过计算 -7 乘以 3 的乘法逆元来计算斜率：(-7 * pow(3, -1, 11)) % 11 = 5。我们现在证明在有限域中它们的斜率是相同的。

斜率是形如 y = c + bx 中 x 的系数。对于上面的两个方程，第一个斜率是 -1/2，第二个斜率是 -7/3。如果我们将这两个分数都转换为有限域 p = 11 中的元素，我们会得到相同的值 5：

import galois
GF11 = galois.GF(11)

negative_1 = -GF11(1)
negative_7 = -GF11(7)

slope1 = GF11(negative_1) / GF11(2)
slope2 = GF11(negative_7) / GF11(3)

assert slope1 == slope2 # 5 == 5

这个事实对于算术电路的含义是：

x + 2 * y === 1
7 * x + 3 * y === 2

在有限域 p = 11 中，该算术电路没有满足赋值。

示例 3：在常规数字上无解的方程组，在有限域中可能有 `p` 个解

以下两个公式绘制出的线是平行的，因此在实数上无解：

x + 2y = 3

4x + 8y = 1

然而，在有限域 p = 11 上，它有 11 个解： $\set{(0, 7), (1, 1), (2, 6), (3, 0), (4, 5), (5, 10), (6, 4), (7, 9), (8, 3), (9, 8), (10, 2)}$ 。这些解被绘制在下方：

练习： 将这两个方程转换为它们的有限域表示，并观察它们是否相同。

假设我们将此方程组编码为一个算术电路：

x + 2y = 3

4x + 8y = 1

x + 2 * y === 3
4 * x + 8 * y === 1

对于我们所使用的有限域，即使我们的约束“看起来不同”，它们也是冗余的。也就是说，两个看起来不同的约束实际上约束了 $x$ 和 $y$ 取相同的值。

有限域中的多项式

在算术电路那一章中，我们使用了多项式 x(x - 1) === 0 来强制约束 x 只能是 0 或 1。这可以写成一个多项式方程。为此，我们将表达式完全展开，直到其表示为单独的 x 的幂次，每一项都乘以一个系数。在本例中即为：x² - x === 0。

假设多项式 x² - x === 0 在有限域（以及实数）中仅有解 0 或 1，在这种情况下是合理的。然而，一般来说，人们不应该假设实数多项式的根与有限域多项式的根相同。我们稍后会展示一些反例。

尽管如此，有限域中的多项式与实数多项式共享许多属性：

阶数（度）为 $d$ 的多项式最多有 $d$ 个根。多项式 $p(x)$ 的根是使得 $p(r) = 0$ 的值 $r$ 。
如果我们将两个多项式 $p_1$ 和 $p_2$ 相加， $p_1 + p_2$ 的阶将最多为 $\max(\deg(p_1), \deg(p_2))$ 。 $p_1 + p_2$ 的阶也有可能小于 $\max(\deg(p_1), \deg(p_2))$ 。例如， $p_1=x³ + 5x + 7$ ，且 $p_2 = -x³$ 。
在有限域中，多项式相加遵循结合律、交换律和分配律。
如果我们将两个多项式 $p_1$ 和 $p_2$ 相乘，乘积的根将是 $p_1$ 和 $p_2$ 的根的并集。

让我们以绘制 $y = x² \pmod {17}$ 为例。

$x$ 的定义域（domain）是有限域的元素，其输出（值域 range）也必须是有限域的成员。请注意，所有的 $x$ 和 $y$ 值都落在 $[0,16]$ 的区间内。有限域上的多项式只能拥有小于 $p$ 的 $x$ 和 $y$ 值。

在有限域 $p = 17$ 中， $y = -x²$ 的等价表示为 $y = 16x² \pmod {17}$ ，因为在该有限域中 16 是 1 的加法逆元。多项式 $y = 16x² \pmod {17}$ 绘制如下：

在实数中没有根的多项式在有限域中可能有根

就像上面我们讨论线性方程组的例子一样，人们不应假设在实数中具有特定根的多项式在有限域中也会有相同的根。

下面，我们在有限域 $p = 17$ 中绘制 $y = x² + 1$ 。在实数中， $y = x² + 1$ 没有实根。但在有限域中，它有两个根，分别为 $4$ 和 $13$ ，如下方红点所示：

现在让我们解释为什么 $y = x² + 1$ 在实数中没有根，但在有限域 $p = 17$ 中却有根。在有限域 $p = 17$ 中，17 同余于零。因此，如果我们为 $x$ 代入一个值，使得 $x² + 1$ 变为 $17$ ，越多项式输出的将是零，而不是 $17$ 。我们可以求解 $x² + 1 = 17$ ，得到 $x² = 17 - 1 = 16$ 。在有限域 $p = 17$ 中， $x² = 16$ 存在解 $4$ 和 $13$ 。因此， $y = x² + 1$ 在有限域 $p = 17$ 中的根为 $4$ 和 $13$ 。

有实根的多项式在有限域中可能无根

考虑多项式 $y = x² − 5$ 。我们可以看到它的根在 $\sqrt{5}$ 和 $-\sqrt{5}$ 。然而，如果我们在模 17 的有限域上绘制它，我们可以看到它从未穿过 x 轴：

没有根是因为 $\sqrt{5}$ 无法在模 17 的有限域中表示。然而，在有限域 $p = 11$ 中，则会有两个根，因为 5 在有限域 $p = 11$ 中有模平方根。

ZK 证明中算术电路的局限性

如果我们希望编写一个算术电路来展示“我知道多项式 $y = x² − 5$ 的根”，且使用有限域上的算术电路，那么我们可能会遇到无法编码 $\sqrt{5}$ 的问题。也就是说，在实数上， $y = x² − 5$ 的根为 $\sqrt{5}$ ，但这在某些有限域中无法表达。根据 $p$ 的不同，算术电路 x² === 5 可能没有满足的见证（satisfying witness）。

在 Python 中使用有限域中的多项式

在对算术电路进行实验时，编写 Python 代码来模拟它们有时会很有帮助。当我们的算术电路呈多项式形式时，我们可以使用前面提到的 galois 库来测试其行为。以下代码示例说明了如何使用此库来处理多项式。

在有限域中将多项式相加

在下面的代码中，我们定义了两个多项式：p1 = x² + 2x + 102 和 p2 = x² + x + 1，然后将它们进行符号相加，生成 2x² + 3x。请注意，在有限域 p = 103 中，常数系数项加起来为零。

import galois
GF103 = galois.GF(103) # p = 103

# we define a polynomial x^2 + 2x + 102 mod 103
p1 = galois.Poly([1,2,102], GF103)

print(p1)
# x^2 + 2x + 102

# we define a polynomial x^2 + x + 1 mod 103
p2 = galois.Poly([1,1,1], GF103)

print(p1 + p2)
# 2x^2 + 3x

galois 库非常智能，它能够将负整数解释为加法逆元，如下面的代码所示：

import galois
GF103 = galois.GF(103) # p = 103

# We can input "-1" as a coefficient, and that will
# automatically be calculated as `p - 1`
# -1 becomes 102 in a field p = 103
p3 = galois.Poly([-1, 1], GF103)
p4 = galois.Poly([-1, 2], GF103)

print(p3)
# 102x + 1
print(p4)
# 102x + 2

在有限域中将多项式相乘

我们可以将多项式相乘在一起：

print(p3 * p4)
# x^2 + 100x + 2

请注意，p3 和 p4 是 1 阶多项式，而它们的乘积是 2 阶多项式。

在有限域中寻找多项式的根

在有限域上寻找多项式的根是一个独立的话题（有关算法，请参见维基百科页面有限域上的多项式分解 factorizing polynomials over finite fields）。galois 库可以使用 roots 函数执行并计算出根。这对于验证多项式形式的算术约束是否真正创建了预期的约束来说可能会很方便。

print((p3 * p4).roots())
# [1, 2]

`galois` 库的注意事项（Gotchas）

该库会悄无声息地对作为系数传递的浮点数进行向下取整（floor）：

# The galois library will silently convert
# floats into a integer
galois.Poly([2.5], GF103)
# Poly(2, GF(103))

如果传递的数字大于或等于 p，该库将会抛出异常（revert）：

# The follow code fails because we cannot
# have coefficients the order of the field or higher
galois.Poly([103], GF103)
# ValueError: GF(103) arrays must have elements in `0 <= x < 103`, not [103].

通过 RareSkills 了解更多

查阅我们的 ZK 书籍，了解更多关于零知识证明的内容。

练习题

在下面的问题中，请使用为 21888242871839275222246405745257275088548364400416034343698204186575808495617 的有限域 p。请注意，galois 库初始化这种大小的 GF 对象 galois.GF(p) 需要一些时间。

一名开发人员创建了一个算术电路 x * y * z === 0 和 x + y + z === 0，目的是约束所有的信号都为零。请找到一个反例，其中该约束被满足，但 x、y 和 z 并不全部为 0。
一名开发人员使用多项式 x² + 2x + 3 === 11 创建了一个电路，并证明了 2 是一个解。另一个解是什么？提示：将电路写成 x² + 2x - 8 === 0，然后手动分解该多项式以寻找其根。最后，计算根在有限域中的同余元素，以找到另一个解。

最初发布于 2024 年 4 月 29 日