# 素数域及其扩展域
## 素数域
### 定义
素数域是元素个数为素数$p$的有限域，记作$\text{GF}(p)$或$\mathbb{F}_p$，其元素为$\{0, 1, 2, \dots, p-1\}$，运算为模$p$的加法和乘法。

### 性质

加法群：所有元素在模$p$加法下构成一个循环群，生成元为 1。
乘法群：非零元素在模$p$ 乘法下构成循环群（即存在本原根）。
域的特性：满足交换律、结合律、分配律，且每个非零元素都有乘法逆元。
### 与模运算的关系

加法：$a + b \mod p$
乘法：$a \cdot b \mod p$
逆元：对任意非零元素 $a$，存在 $a^{-1}$ 满足$a \cdot a^{-1} \equiv 1 \mod p$

## 扩展域
### 定义
扩展域是素数域$\text{GF}(p)$的扩域，元素个数为$p^n ( n \geq 2 )$，记作$\text{GF}(p^n)$。其元素可表示为系数在$\text{GF}(p)$中的多项式，次数小于$n$，并通过模一个$n$次不可约多项式构造。

### 性质

结构：元素为形如$a_0 + a_1 x + \dots + a_{n-1}x^{n-1}$的多项式，系数$a_i \in \text{GF}(p)$。
运算规则：
加法：逐项系数模$p$相加。
乘法：多项式相乘后模一个$n$次不可约多项式，同时系数模$p$。
域的特性：与素数域类似，满足所有域公理，且非零元素构成循环乘法群。

### 与模运算的关系
系数运算：所有系数运算均在$\text{GF}(p)$中完成（即模$P$）。
多项式模运算：乘法结果需模一个不可约多项式$f(x)$，确保结果次数小于$n$，避免零因子。

## 素数域及其扩展域的区别和联系
- 构造方式：
素数域直接通过模素数$p$的整数环构造。
扩展域通过多项式环$\text{GF}(p)[x]$模不可约多项式构造。

- 元素表示：
素数域元素是整数。
扩展域元素是多项式（或等价于向量）。

- 运算复杂度：
扩展域的运算需同时处理多项式系数（模$p$）和多项式模运算（模不可约多项式）。

## 例子说明
素数域$\text{GF}(5)$：

元素：$\{0, 1, 2, 3, 4\}$
运算：例如$3 + 4 = 7 \mod 5 = 2，2 \times 3 = 6 \mod 5 = 1$
扩展域 $\text{GF}(2^2)$：

不可约多项式：$f(x) = x^2 + x + 1$
元素：${0, 1, x, x+1}$
乘法：$x \cdot (x+1) = x^2 + x \mod f(x) = (x+1) + x \mod 2 = 1$