密码学学习笔记——筑基篇·卷四（有限域）

有限域

有限域(伽罗瓦域)

概念回顾:

有限域：元素个数(阶)有限的域。

特征：$ma=\theta$ ($\forall a\in R)$的最小正整数$m;$ 否则 $m=0$。即 Char $R=m$
$(me=\theta\left(e\in R\right)$的最小正整数$m;$ 否则 $m=0)$

有限域的特征一定是素数

素域：不包含任何真子域的域 (任何真子集都不会构成其子域)

从下面开始，若无特殊说明$p$为素数，$F$为有限域。

定理1:阶为素数的有限域必是素域，其特征是这个素数

定理2:任何有限域都包含一个同构于$Z_p$的子域

引理:$K是F的子域,\quad|K|=q,\quad[F{:}K]=n,\quad则|F|=q^n$

定理2: $F的特征是p,K是F的素子域,[F;K]=n, 则 |F|=p^n$

有限域的唯一性

定理 (有限域的唯一性):对于任意素数$p$,任意正整数$n$,都存在阶为$p^n$的有限域。任何阶为$p^n$的有限域都同构于$x^{p^n}-x$在$Z_p$上的分裂域。

引理：$F$的阶为$q$,$K$是$F$的子域，$\forall a\in F$,则

(1) $a^q=a$

$(2)x^q-x\in K[X]$在$K$上的分裂域为$F$,且 $x^q-x=\prod_{a\in F}(x-a)$

结论:具有相同元素的有限域都是同构的
阶为q的有限域，统一用F表示(有的书里用GF(q)表示)

有限域的结构特点

有限域$\Longrightarrow$阶为$p^n$

任意素数$p$,任意正整数$n\Rightarrow$存在阶为$p^n$的有限域
阶为$p^n$的有限域，特征为$p$,包含阶为$p$的素子域

$n$是其在该素子域上的扩张维度

子域准则 (subfield criterion)

定理 (子域准则):设$q=p^n$,有限域$F_q$每个子域的阶都具有$p^m$的形式，
其中$m$是$n$的正因子。反之，如果$m$是$n$的正因子，必然存在$F_q$的唯一子域，其阶为$p^m$。

例：例：求有限域$F_{2^{30}}$的所有子域

解：30的正因子有1，2,3,5,6,10,15,30,则
所求子域为$F_2,F_{2^2},F_{2^3},F_{2^5},F_{2^6},F_{2^{10}},F_{2^{15}},F_{2^{30}}$

有限域的乘法群

$F_q$:有限域(有$q$个元素)
$F_q^*$:有限域的乘法群(不包含零元，只有$q-1$个元素)

定理1：有限域的乘法群是循环群

本原元(primitive element)

定义 (本原元): 有限域$F_q$乘法群的生成元称为$F_q$的本原元.

区分概念：

本原元：有限域乘法群的生成元
原根：模运算下循环群的生成元

定理2:$F_r是F_q的有限扩张,则F_r是F_q的单代数扩张:对于任意F_r的本原元a,都有F_r=F_q(a)。$

推论：对于任意有限域$F_q$,任意正整数$n$,$F_q[X]$里都有一个度为$n$的不可约多项式。

构造有限域

$F_q\rightarrow F_{q^n}$

基于“不可约多项式”构造有限域：$F_q[X]/(f(x))$
基于“基”构造有限域：$F_q(a),f(a)=0$

$F_{q^n}\colon F_q[X]/(f(x))\cong F_q(a)$

基于不可约多项式构造有限域

$f(x)\in F_q[X]$是不可约多项式，则 $F_q[X]/(f(x))$是有限域
$deg(f(x))=n$,则$F_qX)=F_q^n$

例子:$F_{2^{8}}=\{r(x)|r(x)\in F_2[X],deg(r(x))<8\}$

$r(x)=a_7x^7+\cdots+a_1x+a_0$
$r(x){:}0x^{7}+\cdots+0x+0\longrightarrow00\\x^{7}+\cdots+0x+0\longrightarrow01\\\cdots\\x^{7}+\cdots+x+1\longrightarrow FF$
多项式：$x^6+x^4+x^2+x+1$
二进制：01010111

十六进制：57
十六进制：57+83=D4(二进制对应比特异或)
多项式：$(x^6+x^4+x^2+x+1)+(x^7+x+1)=x^7+x^6+x^4+x^2$(二进制：11010100十六进制：$D4$)

十六进制：57×83
多项式：$(x^6+x^4+x^2+x+1)\times(x^7+x+1)$ mod $f(x)$
多项式的扩展欧几里得算法

$r_1(x),r_2(x)\in F_{q^n}$

加法：$r_1(x)+r_2(x)$(不需要 $f(x)$参与)
乘法：$r_1(x)r_2(x)$ mod $f(x)$ (扩展的欧几里得算法)

基于“基”构造有限域

1.$ 找$F_q[X]$里的不可约多项式$f(x)$

2.$ 算出$f(x)$的一个根，设为$a$,即$f(a)=\theta$。

扩域就是单代数扩张$F_q(a)$

设$deg(f(x))=n$,则$F_q(a)$的基为：$e,a,…,a^n-1$
$F_q(a)$元素：$b_0+ b_1a+ \cdots + b_{n- 1}a^{n- 1}$ $( F_q( a) = F_{q^n})$

$b_i是F_q里的元素$

例：$f(x)=x^{8}+x^{4}+x^{3}+x+1$

$f(a)=a^{8}+a^{4}+a^{3}+a^{4}+4$

$F_{2^{8}}=\{b_{0}+b_{1}a+\cdots+b_{7}a^{7}|b_{i}\in F_{2}\}$

十六进制:57
二进制:01010111
元素:$a^6+a^4+a^2+a+1 $

$57+83=D4\colon\left(a^6+a^4+a^2+a+1\right)+\left(a^7+a+1\right)=a^7+a^6+a^4+a^2$
$\begin{aligned}&57\times83\colon(a^6+a^4+a^2+a+1)\times(a^7+a+1)\\&=a^{13}+a^{11}+a^9+a^8+a^6+a^5+a^4+a^3+1\\&f(a)=a^3+a^4+a^3+a+1=0\text{,有}\\&a^8=-a^4-a^3-a-1=a^4+a^3+a+1\\&a^9=a^5+a^4+a^2+a\\&a^{11}=a^7+a^6+a^4+a^3\\&a^{13}=a^9+a^3+a^5+a^5\\&57\times83=C1:\left(a^6+a^4+a^2+a+1\right)\times\left(a^7+a+1\right)=a^7+a^6+1\end{aligned}$

分圆域(cyclotomic field)

$n是正整数，K是任意域，f(x)=x^n-e\in K[x]$

$f(x)=x^n-e=(x-b_1)...(x-b_n)$ $1\leq i\leq n,\:f(b_i)=b_i^n-e=(x-b_1)\:...(b_i-b_i)\:...(x-b_n)=\theta$

$b_i$ 是$x^n-e$的根。

$x^n-e$在$K$上的分裂域为$K(b_1,…,b_n)$

定义(分圆域):$n$是正整数，$K$是任意域，$x^n-e$在$K$上的分
裂域称为$K$上$n$次分圆域，记为$K^{(n)}$。

$1\leq i\leq n, f(b_i)=b_i^n-e=(x-b_1) ...(b_i-b_i) ...(x-b_n)=\theta\\\text{有 }b_i^n=e\text{,即 }b_1,...,b_n\text{都是}e\text{的}n\text{次根。}\\\text{定义}(n\text{次单位根})\text{:}x^n-e\text{在}K^{(n)}\text{里的根}(\text{即 }b_1,...,b_n)\text{称为}\\K\text{上}n\text{次单位根}(n\text{th roots of unity})\text{。}$

$E^{(n)}$:$x^n-e$在$K^{(n)}$里的根组成的集合，记为$E^{(n)}$
$E^{(n)}$的结构依赖于$n$和$K$的特征$m$。

定理1：$K$的特征$m$不是$n$的因子，则$E^{(n)}$是乘法循环群，阶为$n$。

定义$(n$次本原单位根):$E^(n)$是乘法循环群时 (即$m$不是$n$的因子),
$E^{(n)}$的生成元称为$K$上$n$次本原单位根(primitive $n$th root of
unity)。

概念区分：

本原元：有限域乘法群的生成元
原根：模运算下循环群的生成元
$n$次本原单位根：乘法循环群 $E^{(n)}$的生成元

例：$n$次分圆域$\mathbb{Q}^(n)$是$x^n-1$在Q上的分裂域

$\mathbb{Q}^{(n)}$是复数域的子域。

分圆多项式 (cyclotomic polynomial)

$K$的特征不是$n$的因子，则$x^n-e$在$K^(n)$里的根形成乘法循环群$E^{(n)}$
$E^{(n)}:n$个元素，$\phi(n)$个生成元$(n$次本原单位根)

定义(分圆多项式):

域$K$的特征不是正整数$n$的因子，$a_1,…,a_r$
是K上所有$n$次本原单位根，则多项式

$Q_n(x)=\prod_{i=1}^r(x-a_i)$

称为$K$上$n$次分圆多项式，其中$r=\phi(n)$。

定义(分圆多项式):域$K$的特征不是正整数$n$的因子，$a$是$K$上的
一个$n$次本原单位根，则多项式

$Q_n(x)=\prod_{s=1}^n(x-a^s)\\gcd(s,n)=1$

称为$K$上$n$次分圆多项式。

定理1:K的特征不是正整数$n$的因子，则$x^n-e=\prod_{d|n}Q_d(x)$

引理：$d$是正整数$n$的真因子 $(1\leq d<n)$,则$Q_n(x)\mid\frac{x^n-e}{x^d-e}$

基于分圆域构造有限域

定理1：有限域$F$的特征不是正整数$n$的因子，则

$(1)Q_n(x)$可以分解为$F[X]$里$\phi(n)/d$个不同的度为$d$的首一不可约多项式的乘积，$d$ 是满足$q^d\equiv1\left(modn\right)$的最小正整数。
$(2)F^{(n)}$是这些多项式的分裂域
$(3)\left[F^{(n)}{:}F\right]=d$。设$F=F_q$,则 $F^{(n)}=F_{q^d}$

定理2：有限域$K$是$F_q$的任意子域，则$F_q$是$K$上的$q-1$次分圆域

例：$F_{16}$是$F_2$、$F_4$、$F_8$上的15次分圆域

基于“分圆域”构造有限域

设$F_p$是$F_q$的子域，则$F_q$是$F_p$上的$q-1$次分圆域

在$F_p[X]$里分解$Q_{q-1}(x)\in F_p[X]$为首一不可约多项式的乘积
求出任意一个首一不可约多项式的根$a$,易知$a\in F_q$是本原元
$\theta , \boldsymbol{a}, \boldsymbol{a}^2, . . . , \boldsymbol{a}^{q- 1}$就是$F_q$里的元素

有限域的矩阵表示

伴随矩阵(companion matrix)

定义(伴随矩阵):设$K$是域，$f(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1}+x^n\in$
$K[X]$是首一多项式。$f(x)$的伴随矩阵是如下的$n\times n$矩阵：

$f(A)=a_0I+a_1A+\cdots+a_{n-1}A^{n-1}+A^n=\theta$

其中，$I$为$n\times n$单位矩阵

基于“伴随矩阵”构造有限域

一.设$f(x)\in F_p\left[X\right]$是首一不可约多项式，度为$n$

$A$是$f(x)$的伴随矩阵，则有 $f(A)=\theta$
构造一组基$I,A,…,A^{n-1}$
$F_{p^n}$的元素为 $b_0I+b_1A+\cdots+b_{n-1}A^{n-1}$,其中 $b_0,b_1,…,b_{n-1}\in F_p$

二.$设F_q是F_p的扩域,则F_q是F_p上的q-1次分圆域$

$Q_{q-1}(x)分解为首一不可约多项式的乘积,f(x)是其中一个多项式。$
$令C是f(x)的伴随矩阵,则f(C)=\theta,有Q_{q-1}(C)=\theta$
$C是Q_{q-1}(x)的根,也是F_q的本原元$
$F_q的元素为\theta,C,\ldots,C^{q-1}$

多项式的阶(order)

$\begin{aligned}&\text{定义(多项式的阶):又称多项式的周期(period)、多项式的指数}\\&(\text{exponent)。设}f(x)\text{是有限域上的非零多项式,则}\\&·f(x)的常数项不为零元:使得f(x)|(x^n-e)的最小正整数n,\\&\text{称为}f(x)\text{的阶,记为 }ord\left(f(x)\right)\text{。}\\&·f(x)\text{的常数项为零元:设}f(x)=x^tf^{\prime}(x)\text{(}f^{\prime}(x)\text{的常数项不为零}\\&\text{元),则 }ord\left(f(x)\right)=ord\left(f^{\prime}(x)\right)\end{aligned}$

性质：设$f(x)\in F_q[X]$是非常数多项式，它的常数项不为零元，则存在正整数$n\leq q^m-1$,使得$f(x)|(x^n-e)$
特别地：

常数多项式的阶为1 (证明：设$a\in F_q[X]$是常数多项式，则 $x-e=aa^{-1}(x-$
$e)$,有$a|(x-e)$,即$ord(a)=1)$
多项式$x$ 的阶为1 (证明：设$f(x)=x$,常数项为零元，则 $f(x)=xf^{\prime}(x)，f’(x)=e\text{,有}ord\big(f(x)\big)=ord(f’(x))=ord(e)=1\big)$

计算多项式的阶

将多项式f(x)因式分解成首一不可约多项式的乘积
分别算出这些首一不可约多项式的阶
用这些首一不可约多项式的阶算出f(x)的阶

定理1：设 $f(x)=g_1(x)g_2(x)…g_k(x)$是有限域上的多项式，$g_1(x),…,g_k(x)$两两互素的非零多项式，则

$ord(f(x))=lcm(ord(g_1(x)),…,ord(g_k(x)))$。

定理2：$g(x)\in F_q[X]$是不可约多项式，度为$m$,阶为$n$,常数
项不为零元。$a\in F_{q^m}^*,g(a)=\theta$,则 $n$等于$a$在$F_q^m$里的阶

推论：$g(x)\in F_q[X]是不可约多项式，度为m，则ord(g(x))|(q^m-1)$

定理3：$g(x)\in F_q[X]$是不可约多项式，阶为$n$,常数项不为零元，则$ord( g( \boldsymbol{x}) ^b) = \boldsymbol{n}p^t$ $( \boldsymbol{b}$是正整数),其中$p$是$F_q$的特征,$t$是满足$p^t\geq b$的最小整数。

定理4：$f(x)\in F_q[X]\text{是非常数多项式,它的常数项不为零元,}$

$f(x)=ag_1^{b_1}(x)…g_k^{b_k}(x)$

$a\in F_q,b_1,…,b_k\text{是正整数,}g_1(x)…,g_k(x)\in F_q[X]\text{是两两互素的首一不可约多项式,则 }$

$ord(f(x))=np^t\text{,其中}p\text{是}F_q\text{的特征,}t\text{是满足}p^t\geq max(b_1,…,b_k)\text{ 的最小整数,}$

$n=lcm(ord(g_1(x)),…,ord(g_k(x)))\text{。}$

$\begin{aligned} &\text{例：}f(x)=x^{10}+x^9+x^3+x^2+e\in F_2[X] \\ &1.f(x)=\left(x^2+x+e\right)^3(x^4+x+e) \\ &2.\left(x^2+x+e\right)^3\text{的阶为12} \\ &3.x^4+x+e\text{的阶为15}(定理2、推论) \\ &4.f(x)\text{的阶为}lcm(12,15)=60(定理1) \end{aligned}$

本原多项式(primitive polynomial)

有限域里本原元的极小多项式

定义(本原多项式): $f(x)\in F_q[X]$是非常数多项式，度为$m$,设$a\in F_q^m$是本原元，如果$f(x)$是$a$在$F_q$上的极小多项式，则$f(x)$称为$F_q$上的本原多项式。

极小多项式$\Rightarrow$不可约多项式，则本原多项式$\Rightarrow$不可约多项式
$f( a) = \theta$, $a\in F_{q^m}$是本原元，则 $f(x)$的根$a$是$F_q^m$的生成元

$定理1:f(x)\in F_q[X]$,度为$m$,则 $f(x)$是$F_q$上的本原多项式$\Leftrightarrow f(x)$是首一的，常数项非零元，$ord(f(x))=q^m-1$

$\begin{aligned}&\text{定理2:}f(x)\in F_q[X]\text{是非常数首一多项式,度为}m\text{,}a=(-1)^mf(0)\text{,则}\\&f(x)\text{是}F_q\text{上的本原多项式}\Leftrightarrow a\in F_q\text{是本原元,}r=\frac{q^m-1}{q-1}\text{是满足 }x^r\mathrm{~mod~}f(x)\\&\text{等于}F_q\text{的某个元素的最小正整数。另外,}f(x)\text{是}F_q\text{上的本原多项式}\Longrightarrow x^r\equiv\\&a\left(mod\ f(x)\right)。\end{aligned}$

构造不可约多项式

构造极小多项式

极小多项式本质上是一种不可约多项式，要构造不可约多项式，构造一个极小多项式即可。

$F_q:$基域
$F_{q^m}:$向量空间
$a\in F_{q^m}:$定义元素
$e,a,…,a^{m-1}:$基
设$b\in F_{q^m}$的极小多项式是$g(x)=d_0+d_1x+\cdots+d_mx^m\in F_q[X]$ ,则$g(b)=\theta$

构造本原多项式(primitive polynomial)

定义(本原多项式):$f(x)\in F_q[X]$是非常数多项式，度为$m$,设$a\in F_q^m$是本原元，如果$f(x)$是$a$在$F_q$上的极小多项式，则$f(x)$称为$F_q$上的本原多项式。

$F_{q^m}$里非零元素个数$:q^{m-1}$ 本原元的阶：$q^m-1$

设 $q^m-1=h_1…h_k$,其中正整数$h_1,…,h_k$彼此互素，设非零元素 $a_i\in F_{q^m}^*$的阶为$h_i$,则
$c=a_1…a_k$的阶为$q^m-1$,

即 $c\in F_q^m$是本原元。

定理：设 $g(x)$是$F_q$上度为$m$的不可约多项式，$c\in F_{q^m},g(c)=\theta$,则$g(x)$的根为$c,c^q,c^{q^2},\dots ,c^{q^{m-1}}$

迹(trace)

定义(迹): $设 a\in F=F_{q^m}, K=F_q, a在K上的迹Tr_{F/K}(a)定义为\\Tr_{F/K}(a)=a+a^q+\cdots+a^{q^{m-1}}\\如果K是素子域,Tr_{F/K}(a)称为“绝对迹”(absolute trace),简记为Tr_F(a)$

迹的值域是子域K，算出来是K中的一个元素

特征多项式 (characteristic polynomial)

定义 (特征多项式):设 $g(x)\in K[X]$是$a$在$K$上的极小多项式。$g(x)$的度为$d,d\mid m$,则 $g(x)^{m/d}\in K[X]$ 称作$a$在$K$上的特征多项式。

$\text{设 }g(x)^{m/d}=a_0+a_1x+\cdots+a_{m-1}x^{m-1}+x^m\text{。}g(x)\text{ 的根是}\\a,a^q,...,a^{q^{d-1}}\in F,\text{ 则 }g(x)^{m/d}\text{的根是 }a,a^q,...,a^{q^{m-1}}\in F,\text{ 有}\\g(x)^{m/d}=(x-a)(x-a^q)...(x-a^{q^{m-1}})。\\\text{整理 }g(x)^{m/d}\text{ 的两个表达式可知,}Tr_{F/K}(a)=-a_{m-1}\text{。}$

定义(迹的传递性)：设 $F$是$K$的扩域，$K$是$L$的扩域，对于所有的$a\in F$,有
$Tr_{F/L}(a)=Tr_{K/L}(Tr_{F/K}(a))$

迹的性质：

迹的性质：设$F=F_q^m,K=F_q$,迹函数$Tr_{F/K}$满足以下性质：
$(1)Tr_{F/K}(a+b)=Tr_{F/K}(a)+Tr_{F/K}(b)$,对于所有$a,b\in F$
$(2)Tr_{F/K}(c\cdot a)=c\cdot Tr_{F/K}(a)$,对于所有$c\in K,a\in F$
$(3)Tr_{F/K}$是从$F$到K的线性变换，其中$F$和$K$都看作是$K$的向量空间
$(4)Tr_{F/K}(c)=mc$,对于所有$c\in K$
$(5)Tr_{F/K}(a^q)=Tr_{F/K}(a)$,对于所有$a\in F$

迹的应用

$K=F_q:$基域
$F=F_{q^m}$:向量空间
$a_1,…,a_m:$基($对偶基：b_1,…,b_m$）
设$c\in F$,有$c=c_1a_1+\cdots+c_ma_m$
$= Tr_{F/ K}( b_1c) a_1+ \cdots + Tr_{F/ K}( b_mc) a_m$ ,
$b_1,…,b_m\in F$
关系式：$c_j=Tr_{F/K}(b_jc)$

$i\neq j:Tr_{F/K}(b_j a_i)=\theta\\i=j:Tr_{F/K}(b_j a_i)=e$

对偶基(dual basis)

定义 (对偶基):设$F$和$K$是有限域，$F$是K的扩域，$\{a_1,…,a_m\}$和$\{b_1,…,b_m\}$
是$K$上$F$的两组基。如果对于$1\leq i,j\leq m$,有

$i\neq j:Tr_{F/K}(b_j\:a_i)=\theta\\i=j:Tr_{F/K}(b_j\:a_i)=e$

则 $\{a_1,…,a_m\}$和$\{b_1,…,b_m\}$称为对偶基，也称互补基 (complementary basis)。
$\{a_1,…,a_m\}=\{b_1,…,b_m\}$时，$\{a_1,…,a_m\}$叫自对偶基(self-dual basis)。

每个基的对偶基：都存在且唯一

范(norm)

定义 (范): 设 $a\in F= F_q^m, K= F_q$, $a$在$K$上的范$N_F/K(a)$定义为
$N_{F/K}(a)=a\cdot a^q\cdot\cdots\cdot a^{q^{m-1}}=a^{\frac{q^m-1}{q-1}}$

设 $g(x)\in K[X]$是$a$在$K$上的极小多项式。$g(x)$的度为$d,d\mid m$,则
$g(x)^{m/d}\in K[X]$ 称作$a$在$K$上的特征多项式。
设$g(x)^{m/d}=a_0+a_1x+\cdots+a_{m-1}x^{m-1}+x^m$。$g(x)$的根是
$a,a^q,…,a^{q^{d-1}}\in F$,则 $g(x)^{m/d}$的根是 $a,a^q,…,a^{q^{m-1}}\in F$,有
$g(x)^{m/d}=(x-a)(x-a^q)…(x-a^{q^{m-1}})$。
整理$g(x)^{m/d}$的两个表达式可知，$N_{F/K}(a)=(-1)^ma_0$。

定义 (范的传递性):设 $F$是$K$的扩域，$K$是$L$的扩域，对于所有的$a\in\mathcal{F}$,有$N_{F/L}(a)=N_{K/L}(N_{F/K}(a))$

$\begin{aligned}&\text{范的性质:设 }F=F_{q^m}, K=F_q, \text{范函数 }N_{F/K} \text{满足以下性质}:\\&(1) N_{F/K}(a\cdot b)=N_{F/K}(a)\cdot N_{F/K}(b)\text{,对于所有}a,b\in F\\&(2) N_{F/K}\text{将}F\text{映射到}K\text{,将}F^*\text{映射到}K^*\\&(3) N_{F/K}(c)=c^m, \text{对于所有}c\in K\\&(4) N_{F/K}(a^q)=N_{F/K}(a), \text{对于所有}a\in F\end{aligned}$

代数闭包(algebraic closure)

$\begin{aligned}&\text{设}K\text{是域,}K\text{的代数闭包}\overline{K}\text{是包含}K\text{和}K[X]\text{里所有多项式的根的最}\text{小扩域。}\\&\overline{K}=K(a_1,a_2,a_3,...)\\&\text{其中,}a_1,a_2,a_3,...\text{是}K[X]\text{里所有多项式的根。}\end{aligned}$

$\overline{K}$包含$K$的所有代数元素

例：复数域C是实数域R的代数闭包