readme.md

title	tags
27. 有限域	zk abstract algebra field finite field galois field

WTF zk 教程第 27 讲：有限域

这一讲，我们将介绍有限域（也称伽罗瓦域），它是包含有限个元素的域，经常出现在密码学和零知识证明的算法中。

1. 有限域

有限域（Finite Field），也被称为伽罗瓦域（Galois Field，以现代群论创始人伽罗瓦命名），是包含有限个元素的域。我们通常用 $GF(q)$ 或 $F_q$ 表示一个包含 $q$ 个元素的有限域。

性质1. 有限域的元素个数只能是素数 $p$ 或素数的幂次 $p^n$。 包含 $p$ 个元素的域被称为素域（Prime Field），包含 $p^n$ 个元素的被称为素域的扩域。

2. 素域

最常见的一类有限域是整数模 $p$ 域 $GF(p)$（也可写为 $F_p$），这类有限域也被称为素域。你可以把素域理解为整数模 $p$ 的剩余类，和 $Z_p$ 一样，加法和乘法就是模 $p$ 下的加法和乘法。

举个例子，有限域 $GF(2)$ （也可写为 $F_2$）包含两个元素 $\{0,1\}$，正好能表示 1 bit。它的加法表和乘法表如下：

$GF(2)$加法表

+	0	1
0	0	1
1	1	0

$GF(2)$乘法表

·	0	1
0	0	0
1	0	1

再举个例子，有限域 $GF(3)$ 包含3个元素 $\{0,1,2\}$，它的加法表和乘法表如下：

$GF(3)$加法表

+	0	1	2
0	0	1	2
1	1	2	0
2	2	0	1

$GF(3)$乘法表

·	0	1	2
0	0	0	0
1	0	1	2
2	0	2	1

下面介绍素域的一些性质：

性质2. 素域 $F_p$ 的特征为 $p$。 也就是说，$1 \cdot p = 0$，并且任意元素乘以 $p$ 也等于零元。

举个例子， $F_p$ 的特征为 $3$，有

$$0\cdot 3=0(\mathrm{mod}3)$$

$$1\cdot 3=0(\mathrm{mod}3)$$

$$2\cdot 3=0(\mathrm{mod}3)$$

性质3. 任何包含 $p$ 个元素的有限域都与素域 $F_p$ 同构。

这意味着我们可以利用素域 $F_p$ 来研究其他元素个数为 $p$ 的有限域，它们本质上是相同的。

3. 素域扩域

素域扩域是指阶为 $p^n$ 的域，它是素域 $F_p$ 的扩域。

构造方法： 假设 $F_p$ 是一个素域， $f(x)$ 是 $F_p$ 上的不可约多项式，它的度为 $n$，而 $(f(x))$ 是基于 $f(x)$ 构建的主理想，那么商环 $F_{p^n}=F[x]/(f(x))$ 是个阶为 $p^n$ 有限域，它由多项式环 $F[x]$ 中所有度小于 $n$ 的多项式组成：

$$F_{p^n}=\{a_{n-1}{x}^{n-1}+...+a_0|a_i\in F_p\}$$

有限域 $F_{p^n}$ 的加法就是多项式环的加法，而乘法是计算多项式环的乘法后再除以不可约多项式 $f(x)$，保证结果的度不超过 $n$。

因为有限域 $F_{p^n}$ 多项式的每个系数有 $p$ 中选择，一共有 $n$ 个系数，因此 $F_{p^n}$ 中共有 $p^n$ 个元素。

又因为每个系数都属于 $Z_p$，有限域 $F_{p^n}$ 的特征为 $p$。

举个例子，下面我们构造有限域 $F_4$。因为 $4=2^2$，我们通过 $F_2=\{0,1\}$ 来构造。首先，从多项式环 $F_2[x]$ 找出一个度为2的不可约多项式：

$$x^2+x+1$$

然后，我们构建商环 $F_2[x]/(x^2+x+1)$，即 $F_4$，其中元素是 $F_2[x]$ 中与 $x^2+x+1$ 同余的多项式的等价类。

这个有限域中的元素可以表示为 $a+b\alpha$，其中 $a,b\in F_2$， $\alpha$ 是 $x^2+x+1$ 的根。这样构建的有限域可以表示为：

$$\{0,1,\alpha ,1+\alpha \}$$

本来是 $\{0,1,\alpha ,{\alpha }^2\}$，但是 ${\alpha }^2=-\alpha -1=\alpha +1$。有限域 $F_4$ 中的加法和乘法的运算都是在 $F_2[x]/(x^2+x+1)$ 中进行，并按照 $x^2+x+1$ 的同余关系取模。

4. 代码实现

我们可以用galois包在python中实现有限域。在下面的程序中，我们构造了一个 $GF(4)$ 有限域，并打印了它的性质、元素、加法表和乘法表：

import galois

GF4 = galois.GF(4)
print("有限域 GF(4) 的性质", GF4.properties)
print("有限域 GF(4) 的元素", GF4.elements)

print("有限域 GF(4) 的加法表")
print(GF7.arithmetic_table("+"))
print("有限域 GF(4) 的乘法表")
print(GF7.arithmetic_table("*"))

## 输出示例
# 有限域 GF(4) 的性质 Galois Field:
#   name: GF(2^2)
#   characteristic: 2
#   degree: 2
#   order: 4
#   irreducible_poly: x^2 + x + 1
#   is_primitive_poly: True
#   primitive_element: x
# 有限域 GF(4) 的元素 [0 1 2 3]
# 有限域 GF(4) 的加法表
# x + y | 0  1  2  3 
# ------|------------
#     0 | 0  1  2  3 
#     1 | 1  0  3  2 
#     2 | 2  3  0  1 
#     3 | 3  2  1  0 
# 有限域 GF(4) 的乘法表
# x * y | 0  1  2  3 
# ------|------------
#     0 | 0  0  0  0 
#     1 | 0  1  2  3 
#     2 | 0  2  3  1 
#     3 | 0  3  1  2 

5. 总结

这一讲，我们介绍了有限域，它是是密码学和零知识证明最常用的数学结构。有限域包括包括素域及其扩域：素域 $F_p$ 是有限域中最简单的一类，包含素数 $p$ 个元素；素域的扩域包含 $q^n$ 个元素，由素域 $F_p$ 和不可约多项式构造。