##### 有限域 - 有限域 - **有限域**是一个元素个数[[有限集|有限]]的[[域]]. 最基本的是素数阶域, 对于任意[[素数]] $p$ 有 $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$, 这是所有整数模 $p$ 的[[同余|同余类]]构成的一个域. 而更一般的有限域元素个数为 $p^n$, 它是 $\mathbb{F}_p$​ 的一个维数为 $n$ 的有限扩域 $\mathbb{F}_{p^n}$, 是 $\mathbb{F}_p[x]$ 模去一个[[不可约多项式]]生成的理想 $\langle f(x) \rangle$ 的[[商环]] - $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ - $\mathbb{F}_{p^n} \cong \mathbb{F}_p[x]/\langle f(x) \rangle$ >[!example]- 有限域 >- 有限域阶数 $q = p^n$ > - 素数域 $\mathbb{F}_p$, 当 $n = 1$ > - 当 $q = p$ 为素数时, 有限域 $\mathbb{F}_p$ 是模 $p$ 的整数环, 即 $\mathbb{Z}/p\mathbb{Z} = \{0, 1, 2, \ldots, p-1\}$ > - 加法, 模 $p$ 加法, 例如 $\mathbb{F}_5$ 中, $3 + 4 = 7 \equiv 2 \pmod{5}$ > - 乘法, 模 $p$ 乘法, 例如 $\mathbb{F}_5$ 中, $3 \cdot 4 = 12 \equiv 2 \pmod{5}$ > - 逆元, 通过扩展欧几里得算法求解, 例如 $\mathbb{F}_5$ 中, $3$ 的乘法逆元满足 $3 \cdot x \equiv 1 \pmod{5}$, 解得 $x = 2$, 因为 $3 \cdot 2 = 6 \equiv 1 \pmod{5}$ > - $\mathbb{F}_3 = \{0, 1, 2\}$ > - 加法, $1 + 2 = 0 \pmod{3}$ > - 乘法, $2 \cdot 2 = 4 \equiv 1 \pmod{3}$ > - 扩展域 $\mathbb{F}_{p^n}$, 当 $n \geq 2$ > - 当 $q = p^n$ 且 $n \geq 2$, 有限域可以通过模不可约多项式的商环构造 > - 多项式环, 取素数域 $\mathbb{F}_p$ 上的多项式环 $\mathbb{F}_p[x]$, 即系数在 $\mathbb{F}_p$ 中的多项式 > - 不可约多项式, 选择一个在 $\mathbb{F}_p[x]$ 中次数为 $n$ 的不可约多项式 $f(x)$. 不可约多项式是指不能分解为更低次数多项式的乘积, 类似于素数 > - 商环构造, 有限域 $\mathbb{F}_{p^n}$ 同构于 $\mathbb{F}_p[x] / \langle f(x) \rangle$, 其中 $\langle f(x) \rangle$ 是由 $f(x)$ 生成的理想 > - 元素表示, 域的元素是次数小于 $n$ 的多项式, 即 $\{ a_0 + a_1 x + \cdots + a_{n-1} x^{n-1} \mid a_i \in \mathbb{F}_p \}$, 运算在模 $f(x)$ 和模 $p$ 下进行 > - 构造 $\mathbb{F}_4 = \mathbb{F}_{2^2}$ > - 取 $p = 2$, $n = 2$, 在 $\mathbb{F}_2[x]$ 中选择不可约多项式 $f(x) = x^2 + x + 1$ > - 域 $\mathbb{F}_4 = \mathbb{F}_2[x] / \langle x^2 + x + 1 \rangle$, 元素为 $\{0, 1, \alpha, \alpha + 1\}$, 其中 $\alpha$ 是 $f(x)$ 的根, 满足 $\alpha^2 = \alpha + 1$ > - 加法, $\alpha + (\alpha + 1) = 1$ > - 乘法, $\alpha \cdot \alpha = \alpha^2 = \alpha + 1$ > - 乘法群, 非零元素 $\{1, \alpha, \alpha + 1\}$ 构成循环群, 满足 $(\alpha + 1)^2 = \alpha$, $(\alpha + 1)^3 = 1$