有限域

创建时间 2021-10-07

更新时间 2021-11-21

分类

读书笔记

域

设 $F$ 是一个集合， $F$ 中的元素有两个运算 $+$ 加法和 $\cdot$ 乘法，满足如下的公理，则称之为域：

对于任意 $a, b, c \in F$ ：

公理一封闭性： $F$ 对运算 $+$ 和 $\cdot$ 封闭，意思是， $a + b \in F$ ， $a\cdot b \in F$
公理二交换律： $a + b = b + a$ , $a \cdot b = b \cdot a$
公理三结合律： $(a + b) + c = a + (b + c)$ , $a\cdot (b \cdot c) = (a \cdot b) \cdot c$
公理四分配律： $a\cdot(b + c) = a\cdot b + a \cdot c$

同时， $F$ 有两个不同的元素 $0$ 和 $1$ ，分别成为零元和幺元，必须满足：

公理五 $a + 0 = a$
公理六 $a \cdot 1 = a$ ， $a \cdot 0 = 0$
公理七对于任意 $a \in F$ ，存在加法逆元 $-a \in F$ 满足 $a + (-a) = 0$
公理八对于任意 $a \neq 0 \in F$ ，存在乘法逆元 $a^{-1}$ 满足 $a \cdot a^{-1} = 1$

通常我们简写 $a \cdot b$ 为 $ab$ ，记 $F^*\xlongequal{\text{def}} F / \{0\}$ ，表示去掉 $0$ 元的 $F$

一些例子

$Z_2$ 的加法表；

$+$	0	1
0	0	1
1	1	0

很显然，这是一个异或逻辑；

$Z_2$ 的乘法表；

$\cdot$	0	1
0	0	0
1	0	1

也很显然，这是一个与逻辑；

引理：设 $\forall a, b \in F$ ，其中 $F$ 是域，则：

$(-1) \cdot a = -a$

如果 $ab=0$ ，则 $a=0$ 或 $b = 0$

证明：

$\begin{aligned} & (-1) \cdot a + a \\ \xlongequal{公理六}& (-1) \cdot a + a \cdot 1 \\ \xlongequal{交换律}& a \cdot (-1) + a \cdot 1\\ \xlongequal{结合律}& a \cdot [(-1) + 1]\\ \xlongequal{公理七}& a \cdot 0\\ \xlongequal{公理六}& 0\\ \Rightarrow& (-1) \cdot a = -a \end{aligned}$

若 $a \neq 0$ ，则：

$\begin{aligned} 0 \xlongequal{公理六}& a^{-1} \cdot 0 \\ \xlongequal{假设}& a^{-1} \cdot (ab) \\ \xlongequal{结合律}& (a^{-1}a)b \\ \xlongequal{交换律}& (aa^{-1})b \\ \xlongequal{公理八}& 1 \cdot b \\ \xlongequal{交换律}& b \cdot 1 \\ \xlongequal{公理六}& b \\ \end{aligned}$

由于对称性，对于 $b \neq 0$ 的情况，同理可证。

定义：设 $a, b$ 和 $m > 1$ 是整数，如果 $m \mid (a - b)$ 则 $a, b$ 模 $m$ 同余：

$a\equiv b \pmod m$

定理： $Z_m$ 是域，当且仅当 $m$ 是素数；

定义：设 $F$ 是一个域， $F$ 的 特征(characteristic) 是使得 $p \cdot 1 = 0$ 成立的最小正整数 $p$ 。如果 $F$ 不存在这样的正整数，则定义 $F$ 的特征为 $0$

定理：若 $p$ 为域 $F$ 的特征，则 $p = 0$ 或 $p$ 是一个素数；

定理：对于一些 $n \geqslant 1$ 的整数，特征为 $p$ 的有限域 $F$ 的包含 $p^n$ 个元素；

多项式环

定义：设 $F$ 是一个域，集合

$F[x]:= \left\{ \sum_{i = 0}^n a_i x^i : a_i \in F, n \geqslant 0\right\}$

叫做 $F$ 上的 多项式环，环是满足公理一到七的集合；

$F[x]$ 的元素是 $F$ 上的多项式，对于多项式 $\displaystyle f(x) =\sum_{i=0}^n a_ix^i$ ，其中 $n$ 叫做多项式 $f(x)$ 的 阶(degree)，记作 $\deg(f(x))$ ；

如果 $a_n \neq 0$ ，一个 $n$ 阶非零多项式 $\displaystyle f(x) =\sum_{i=0}^n a_ix^i$ ，如果 $a_n = 1$ ，则说多项式 $f(x)$ 是首一的 (monic)；

对于 $F$ 上的 $n > 0$ 阶多项式 $f(x)$ ，如果存在两个多项式 $g(x), h(x)$ 满足 $\deg(g(x)) < n$ , $\deg(h(x)) < n$ ，并且 $f(x) = g(x) \cdot h(x)$ ，则称 $f(x)$ 是 可约(reducible) 的；否则则称 $f(x)$ 在 $F$ 上 不可约；

定义：设 $f(x) \in F[x]$ 是一个 $n > 1$ 阶的多项式，对于任意 $g(x) \in F[x]$ 的多项式，存在一个唯一的多项式对 $[s(x), r(x)]$ ，满足 $\deg(r(x)) < \deg(f(x))$ 或者 $r(x) = 0$ 使得 $g(x) = s(x) f(x) + r(x)$ 成立，多项式 $r(x)$ 称为 $g(x)$ 除以 $f(x)$ 的剩余多项式，记为 $g(x) \equiv r(x) \pmod {f(x)}$

定义：设 $f(x), g(x) \in F[x]$ 是两个非零多项式
- $f(x), g(x)$ 的最大公因子 记为 $\gcd(f(x), g(x))$ ，是除 $f(x), g(x)$ 最高阶的首一多项式；
- 特别的，如果 $\gcd(f(x), g(x)) = 1$ ，我们则说 $f(x), g(x)$ 互素；
- $f(x), g(x)$ 的最小公倍式，是 $f(x), g(x)$ 同为因子的最低阶的首一多项式；

定理：设 $f(x)$ 是一个域 $F$ 上的多项式， $\deg(f(x)) > 1$ ，则 $F[x]/f(x)$ ，加运算和乘运算定义如下表，构成一个环，当且仅当 $f(x)$ 不可约时 $F[x]/f(x)$ 是一个域；

$Z$	$F[x]$
$Z_m = \{0, 1, \cdots, m - 1\}$	$\displaystyle F[x]/f(x):= \left\{ \sum_{i = 0}^n a_i x^i : a_i \in F, n \geqslant 1\right\}$
$a + b := a + b \pmod m$	$g(x) + h(x) := g(x) + h(x) \pmod {f(x)}$
$a \cdot b := ab \pmod m$	$g(x) \cdot h(x) := g(x)h(x) \pmod {f(x)}$
$Z_m$ 是一个环	$F[x]/f(x)$ 是一个环
$Z_m$ 是一个域，当且仅当 $m$ 是素数	$F[x]/f(x)$ 是一个域，当且仅当 $f(x)$ 不可约

有限域结构

引理：设 $F$ 是有限域，有 $q$ 个元素，对于任意 $\beta \in F$ ，有 $\beta^q = \beta$

推论：设 $F$ 是一个 $E$ 的子域， $|F| = q$ ，元素 $\beta \in E$ ，当且仅当 $\beta^q = \beta$ 时， $\beta \in F$ ；

定理：对于任意素数 $p$ 和整数 $n \geqslant 1$ ，存在一个唯一有 $p^n$ 个元素的有限域；

这里的唯一是一种同构的概念。

定义：设 $F_q$ 是有限域， $\alpha \in F_q$ ，如果 $F_q = \{0, \alpha, \alpha^2, \cdots, \alpha^{q - 1}\}$ ，则称 $\alpha$ 为 $F_q$ 的 本原元(primitive element) 或者 生成器(generator)

定义：非零元素 $\alpha \in F_q$ 的阶 (order)，记为 $\text{ord}(\alpha)$ ，是最小正整数 $k$ 使得 $\alpha^k = 1$

引理：
- 阶 $\text{ord}(\alpha)$ 整除 $q - 1$ 对于所有 $\alpha \in F^*_q$
- 对于两个非零元素 $\alpha, \beta \in F^*_q$ ，如果 $\gcd(\text{ord}(\alpha), \text{ord}(\beta)) = 1$ ，则 $\text{ord}(\alpha \beta) = \text{ord}(\alpha) \times \text{ord}(\beta)$

命题：
- $F_q$ 的非零元素 $\alpha$ 是本原元，当且仅当 $\text{ord}(\alpha) = q - 1$
- 所有有限域都有至少一个本原元

注：本原元可能不唯一

最小多项式

设 $F_q$ 是 $F_r$ 的子域，对于一个元素 $\alpha \in F_r$ ，我们感兴趣的是非零多项式 $f(x) \in F_q[x]$ 有做小的次使得 $f(\alpha) = 0$ 成立；

定义：设 $\alpha \in F_{q^m}$ ， $\alpha$ 关于 $F_q$ 的一个 最小多项式，是 $F_q[x]$ 中最低阶的非零首一多项式 $f(x)$ ，使得 $f(\alpha) = 0$

例：设 $\alpha$ 是 $1 + x + x^2 \in F_2[x]$ 的一个根，那么 $x$ 和 $1 + x$ 显然不是关于 $\alpha$ 的最小多项式，因此 $1 + x + x^2$ 是 $\alpha$ 最小多项式；

因为

$\begin{aligned} & 1 + (1 + \alpha) + (1 + \alpha)^2 \\ = & 1 + 1 + \alpha + 1 + \alpha^2 \\ = & 1 + \alpha + \alpha^2 =0\\ \end{aligned}$

而且 $1 + \alpha$ 不是关于 $x$ 或者 $1 + x$ 的根，所以 $1 + x + x^2$ 同样是 $1 + \alpha$ 的最小多项式；

定理：
- $F_{q^m}$ 中的元素 $\alpha$ 关于 $F_q$ 的最小多项式存在且唯一，该多项式在 $F_q$ 上同样不可约；
- 如果一个首一不可约多项式 $M(x) \in F_q[x]$ 有 $\alpha \in F_{q^m}$ 最为根，则它是 $\alpha$ 关于 $F_q$ 的最小多项式

定义：设 $n$ 与 $q$ 互素， $q$ 模 $n$ 的 分圆陪集(cyclotomic coset) 包含 $i$ 定义为：

$C_i = \{(i \cdot q^j\pmod n) \in Z_n : j = 0, 1, \cdots \}$

如果 $C_{i_1}, \cdots, C_{i_t}$ 是不同的且 $\displaystyle \bigcup_{j = i}^t C_{i_j} = Z_n$ ，则 $Z_n$ 的子集 $\{i_1, \cdots, i_2\}$ 叫做 $q$ 模 $n$ 的分圆陪集 代表的完整集合

注意：

容易验证两个分圆陪集要么相等要么交集为空，因此分圆陪集是 $Z_m$ 的一个划分；
如果 $n = q^m - 1$ 对于一些 $m \geqslant 1$ 成立，每个分圆陪集包含至多 $m$ 个元素，如 $q^m \equiv 1 \pmod {q^m - 1}$ ；
容易得到， $n = q^m -1$ 对于一些 $m \geqslant 1$ ，若 $\gcd(i, q^m - 1) = 1$ ，则 $|C_i| = m$ ；

例：考虑 2 模 15 的分圆陪集

$C_i = \{(i \cdot q^j\pmod n) \in Z_n : j = 0, 1, \cdots \}$

则 $q = 2$ , $n = 15$

$\begin{aligned} C_0 =& \{0 \cdot 2^j\pmod {15}\} = \{0\}, \\ C_1 =& \{1 \cdot 2^j\pmod {15}\} = \{1, 2, 4, 8\}, \\ C_3 =& \{3 \cdot 2^j\pmod {15}\} = \{3, 6, 9, 12\}, \\ C_5 =& \{5 \cdot 2^j\pmod {15}\} = \{5, 10\}, \\ C_7 =& \{7 \cdot 2^j\pmod {15}\} = \{7, 11, 13, 14\}. \end{aligned}$

因此，在同一个分圆陪集中的元素的分圆陪集都是一样的，比如 $C_1 = C_2 = C_4 = C_8$ ，那么集合 $\{0, 1, 3, 5, 7\}$ 是一个 $2$ 模 $15$ 代表分圆陪集的完整集合。

下面我们可以确定有限域中所有元素的最小多项式了；

定理：设 $\alpha$ 是 $F_{q^m}$ 的本原元（生成器），则 $a^i$ 关于 $F_q$ 的最小多项式是：

$M^{(i)}(x):= \prod_{j \in C_i} (x - \alpha^j)$

其中 $C_i$ 是 $q$ 模 $q^m - 1$ 包含 $i$ 的唯一分圆陪集；

注意：

$\alpha^i$ 的最小多项式的次数等于包含 $i$ 的分圆陪集的元素数量；
通过上面的定理，我们可以知道当且仅当 $i, k$ 在同一个分圆陪集中时， $\alpha^i$ 和 $\alpha^k$ 有相同的最小多项式；

定理：设 $n$ 是一个正整数， $\gcd(q,n) = 1$ ，设 $m$ 是一个正整数，满足 $n \mid (q^m - 1)$ ，设 $\alpha$ 是 $F_{q^m}$ 的本原元，且 $M^{(j)}(x)$ 是 $\alpha^j$ 关于 $F_q$ 的最小多项式，设 $\{s_1, \cdots, s_t\}$ 是 $q$ 模 $n$ 的分圆陪集代表的完整集合，则多项式 $x^n - 1$ 可分解成在 $F_q$ 上的首一不可约多项式：

$x^n - 1 = \prod_{i = 1}^t M^{({(q^m - 1)s_i / n})}(x)$

推论：设 $n$ 是一个正整数且 $\gcd(q, n) = 1$ ，则 $x^n - 1$ 在 $F_q$ 上的首一不可约因子的数量，等于 $q$ 模 $n$ 的分圆陪集的数量；

例子：还是上面 2 模 15 哪个例子；

$f(x) = 1 + x^3 + x^4$ 是 $F_{16}$ 的不可约多项式，于是：

$\begin{aligned} 0 &= 0 \\ \alpha^0 &= 1 \\ \alpha^1 &= \alpha^1 \\ \alpha^2 &= \alpha^2 \\ \alpha^3 &= \alpha^3 \\ \alpha^4 &= \alpha^3 + 1 \\ \alpha^5 &= \alpha^4\alpha = (\alpha^3 + 1) \alpha = \alpha^4 + \alpha = \alpha^3 + \alpha + 1 \\ \alpha^6 &= \alpha^5\alpha = (\alpha^3 + \alpha + 1) \alpha = \alpha^4 + \alpha^2 + \alpha = \alpha^3 + \alpha^2 + \alpha + 1\\ \alpha^7 &= \alpha^6\alpha = (\alpha^3 + \alpha^2 + \alpha + 1) \alpha = \alpha^4 + \alpha^3 + \alpha^2 + \alpha = \alpha^2 + \alpha + 1\\ \alpha^8 &= \alpha^7\alpha = (\alpha^2 + \alpha + 1) \alpha = \alpha^3 + \alpha^2 + \alpha \\ \alpha^9 &= \alpha^8\alpha = (\alpha^3 + \alpha^2 + \alpha) \alpha = \alpha^4 + \alpha^3 + \alpha^2 = \alpha^2 + 1\\ \alpha^{10} &= \alpha^9\alpha = (\alpha^2 + 1) \alpha = \alpha^3 + \alpha \\ \alpha^{11} &= \alpha^{10}\alpha = (\alpha^3 + \alpha) \alpha = \alpha^4 + \alpha^2 = \alpha^3 + \alpha^2 + 1 \\ \alpha^{12} &= \alpha^{11}\alpha = (\alpha^3 + \alpha^2 + 1) \alpha = \alpha^4 + \alpha^3 + \alpha= \alpha + 1 \\ \alpha^{13} &= \alpha^{12}\alpha = (\alpha + 1) \alpha = \alpha^2 + \alpha \\ \alpha^{14} &= \alpha^{13}\alpha = (\alpha^2 + \alpha) \alpha = \alpha^3 + \alpha^2\\ \alpha^{15} &= \alpha^{14}\alpha = (\alpha^3 + \alpha^2) \alpha = \alpha^4 + \alpha^3 = 1 = \alpha^0\\ \end{aligned}$

$M^{(i)}(x):= \prod_{j \in C_i} (x - \alpha^j)$

$\begin{aligned} M^{({0})}(x) =& (x - \alpha^0) = x + 1 \\ M^{({1})}(x) =& (x - \alpha^1)(x - \alpha^2)(x - \alpha^4)(x - \alpha^8) \\ =& x^4 + x^3 + 1 \\ M^{({3})}(x) =& (x - \alpha^3)(x - \alpha^6)(x - \alpha^9)(x - \alpha^{12}) \\ =& x^4 + x^3 + x^2 + x + 1 \\ M^{({5})}(x) =& (x - \alpha^5)(x - \alpha^{10})\\ =& x^2 - (\alpha^5 + \alpha^{10})x + \alpha^{15}\\ =& x^2 + x + 1\\ M^{({7})}(x) =& (x - \alpha^7)(x - \alpha^{11})(x - \alpha^{13})(x - \alpha^{14}) \\ &= x^4 + x + 1 \\ \end{aligned}$

$x^n - 1 = \prod_{i = 1}^t M^{({(q^m - 1)s_i / n})}(x)$

$\begin{aligned} x^{15} - 1 =& \prod_{i = 1}^t M^{({(2^4 - 1)s_i / 15})}(x) \\ =& \prod_{i = 1}^t M^{({s_i})}(x) \\ =& M^{({0})}(x) M^{({1})}(x) M^{({3})}(x) M^{({5})}(x) M^{({7})}(x) \\ =& (x + 1) (x^2 + x + 1) (x^4 + x + 1) (x^4 + x^3 + 1) (x^4 + x^3 + x^2 + x + 1) \end{aligned}$

伽罗瓦域

伽罗瓦域 $GF(q)$ 是具有有限个元素 $q$ 的域。

对于任意 $q = p^m$ ，其中 $p$ 为素数， $m$ 为正整数，存在一个唯一的伽罗瓦域；除此之外，不存在其他有限域。

为什么伽罗瓦域与线性码有关？

假设将一个二进制生成矩阵 $G$ 和二进制向量 $s$ 推广到元素来自更大集合的矩阵和向量，并对定义乘积 $Gs$ 的加法和乘法运算进行推广。

为了产生对称信道的一个合适输入，如果对于随机 $s$ , 乘积 $Gs$ 以等概率产生放大集合中的所有元素，则会方便许多。

如果这些元素在加法和乘法运算下都形成一个群，那么均匀分布最容易得到保证，因为这些运算不会破坏元素间的对称。当一个乘法群的两个随机元素相乘时，可以等概率地产生所有元素。

对其他集合（如整数集），这一点不成立，因为乘法运算产生某些元素（合数）的可能性更大些。由定义可知，伽罗瓦域避免了这种破坏对称效应。

有限域

域

一些例子

多项式环

有限域结构

最小多项式

伽罗瓦域

评论