> For the complete documentation index, see [llms.txt](https://chenyangwang.gitbook.io/mathematical-base-for-information-safety/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chenyangwang.gitbook.io/mathematical-base-for-information-safety/huan-yu-yu/you-xian-yu.md).

# 有限域

## **域的扩张**

* 设$$F$$为一个域，如果$$K$$是$$F$$的子域，则称$$F$$为$$K$$的扩域
* $$F$$为域$$K$$的一个扩张，将$$F$$看成$$K$$上的向量空间，若是有限维的，则称$$F$$为$$K$$的有限维扩张，$$K$$上向量空间$$F$$的维数称为扩张次数，记为$$\left\[F:K\right]$$
* 设$$R$$为一个整环，$$K$$是包含$$R$$的一个域，$$F$$是$$K$$的扩张
  * $$F$$的元素$$u$$称为$$R$$上的代数数，若存在一个非零多项式$$f\in R\left\[x\right]$$使得$$f\left(u\right)=0$$
    * 如果$$F$$的每个元素都是$$K$$上的代数数，$$F$$称为$$K$$的代数扩张
  * $$F$$的元素$$u$$称为$$R$$上的超越数，若不存在任何非零多项式$$f\in R\left\[x\right]$$使得$$f\left(u\right)=0$$
    * 如果$$F$$中至少有一个元素是$$K$$上的超越数，$$F$$称为$$K$$的超越扩张
* $$E$$是域$$F$$上的一个扩张$$F\left(\alpha\right)$$，$$\alpha$$为$$F$$上的代数数，则$$E=F\left(\alpha\right)$$上的元素$$\beta$$可以表示为$$\beta=b\_0+b\_1\alpha+\cdots+b\_{n-1}\alpha^{n-1},b\_i\in F$$

## **Galois域**

* 由素域$$F\_p$$的$$n$$次扩张构成的有限域$$F\_{p^n}$$为一种Galois域
* 有限域$$F\_{p^n}$$上的生成元$$g$$称为$$F\_{p^n}$$的本原元，$$F\_{p^n}=\left{0\right}\cup <g>$$，$$g$$定义的多项式叫本原多项式
  * 有限域$$F\_{p^n}$$上的乘法群$$F\_{p^n}^{\*}$$是一个循环群

## **有限域的表示**

* $$f\left(x\right)$$表现形式

  $$F\_{p^n}=\left{f\left(x\right)=a\_{n-1}x^{n-1}+\cdots +a\_1x+a\_0\in F\_p\left\[x\right]\right}$$

  * 易于加法运算
* $$g$$表现形式

  $$F\_{p^n}=\left{0\right}\cup <g>=\left{0,g^0=1,g,g^2,\cdots,g^{p^n-2}\right}$$

  * 易于乘法运算

## **有限域的本原元**

> **寻找本原元** 给定有限域$$F\_{p^n}$$，其中$$p$$为素数，设$$p^n-1$$的所有不同素因数为$$q\_1,\cdots,q\_s$$，则$$g$$是$$F\_{p^n}$$中本原元的充要条件为$$g^{\frac{p^n-1}{q\_i}}\not\equiv1,i=1,\cdots,s$$ 寻找本原元：Gauss算法
>
> * **STEP1:**&#x20;
>
>   令$$i=1$$，取$$F\_q$$中任一非零元$$a\_i$$，计算其阶，记为$$\mathrm{ord}\left(a\_i\right)=k\_i$$
> * **STEP2:**&#x20;
>
>   若$$k\_i=q-1$$，则$$a\_i$$为本原元，停止循环；否则转至STEP3
> * **STEP3:**&#x20;
>
>   取$$F\_q$$中另一非零元，满足$$b$$不是$$a\_i$$的整数次幂，计算其阶，记为$$\mathrm{ord}\left(b\right)=h$$，若$$h=q-1$$，则令$$a\_i+1=b$$为一本原元，停止循环；否则转至STEP4
> * **STEP4:**&#x20;
>
>   取整数$$t,s$$，使得$$t\mid k\_i,s\mid h,\left(t,s\right)=1,ts=\left\[k\_i,h\right]$$，令$$a\_{i+1}=a\_i^{\frac{k\_i}{t}}b^{\frac{h}{s}}$$，则$$\mathrm{ord}\left(a\_{i+1}\right)=k\_{i+1}=ts$$，$$i$$增加$$1$$，转至STEP2

> $$g$$**的幂的运算** $$g=a\_nx^n+\cdots+a\_1x+a\_0=\left(\overline{a\_n\cdots a\_0}\right)$$
>
> * 乘除：正常运算
> * 加法：异或运算