| title |
tags |
27. 有限域 |
zk |
abstract algebra |
field |
finite field |
galois field |
|
这一讲，我们将介绍有限域（也称伽罗瓦域），它是包含有限个元素的域，经常出现在密码学和零知识证明的算法中。
有限域（Finite Field），也被称为伽罗瓦域（Galois Field，以现代群论创始人伽罗瓦命名），是包含有限个元素的域。我们通常用 $GF(q)$ 或 $F_q$ 表示一个包含 $q$ 个元素的有限域。
性质1. 有限域的元素个数只能是素数 $p$ 或素数的幂次 $p^n$。 包含 $p$ 个元素的域被称为素域（Prime Field），包含 $p^n$ 个元素的被称为素域的扩域。
最常见的一类有限域是整数模 $p$ 域 $GF(p)$（也可写为 $F_p$），这类有限域也被称为素域。你可以把素域理解为整数模 $p$ 的剩余类，和 $Z_p$ 一样，加法和乘法就是模 $p$ 下的加法和乘法。
举个例子，有限域 $GF(2)$ （也可写为 $F_2$）包含两个元素 $\set{0, 1}$，正好能表示 1 bit。它的加法表和乘法表如下：
$GF(2)$加法表
$GF(2)$乘法表
再举个例子，有限域 $GF(3)$ 包含3个元素 $\set{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 \pmod{3}
$$
$$
1 \cdot 3 = 0 \pmod{3}
$$
$$
2 \cdot 3 = 0 \pmod{3}
$$
性质3. 任何包含 $p$ 个元素的有限域都与素域 $F_p$ 同构。
这意味着我们可以利用素域 $F_p$ 来研究其他元素个数为 $p$ 的有限域，它们本质上是相同的。
素域扩域是指阶为 $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} = \set{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 = \set{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$ 的根。这样构建的有限域可以表示为：
$$
\set{0, 1, \alpha, 1 + \alpha}
$$
本来是 $\set{0, 1, \alpha, \alpha ^2}$，但是 $\alpha^2 = -\alpha -1 = \alpha + 1$。有限域 $F_4$ 中的加法和乘法的运算都是在 $F_2[x]/(x^2 + x + 1)$ 中进行，并按照 $x^2 + x + 1$ 的同余关系取模。
我们可以用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 这一讲，我们介绍了有限域，它是是密码学和零知识证明最常用的数学结构。有限域包括包括素域及其扩域：素域 $F_p$ 是有限域中最简单的一类，包含素数 $p$ 个元素；素域的扩域包含 $q^n$ 个元素，由素域 $F_p$ 和不可约多项式构造。