有限域

域的扩张

• 设$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:

  令$i=1$，取$F_q$中任一非零元$a_i$，计算其阶，记为$\mathrm{ord}\left(a_i\right)=k_i$
• STEP2:

  若$k_i=q-1$，则$a_i$为本原元，停止循环；否则转至STEP3
• STEP3:

  取$F_q$中另一非零元，满足$b$不是$a_i$的整数次幂，计算其阶，记为$\mathrm{ord}\left(b\right)=h$，若$h=q-1$，则令$a_i+1=b$为一本原元，停止循环；否则转至STEP4
• STEP4:

  取整数$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)$

• 乘除：正常运算

• 加法：异或运算