27.有限域

文档摘要

title: 27. 有限域 tags: zk abstract algebra field finite field galois field WTF zk 教程第 27 讲：有限域这一讲，我们将介绍有限域（也称伽罗瓦域），它是包含有限个元素的域，经常出现在密码学和零知识证明的算法中。有限域有限域（Finite Field），也被称为伽罗瓦域（Galois Field，以现代群论创始人伽罗瓦命名），是包含有限个元素的域。我们通常用 $GF(q)$ 或 $Fq$ 表示一个包含 $q$ 个元素的有限域。性质1. 有限域的元素个数只能是素数 $p$ 或素数的幂次 $p^n$。包含 $p$ 个元素的域被称为素域（Prime Field），包含 $p^n$ 个元素的被称为素域的扩域。


title: 27. 有限域
tags:
  - 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）包含两个元素 \set{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个元素 \set{0,1,2}，它的加法表和乘法表如下：

GF(3)加法表

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

GF(3)乘法表

·	1	2
0	0	0
1	1	2
2	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 的有限域，它们本质上是相同的。

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} = \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 的同余关系取模。

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(GF4.arithmetic_table("+"))
print("有限域 GF(4) 的乘法表")
print(GF4.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 和不可约多项式构造。