1 有限域基础知识
1.1 有限域(Galois域)的构造
令 p 为一个素数. 则对任意的一个正整数 n，存在一个特征为 p，元素个数为 pn 的有限域 GF(pn).web
注：任意一个有限域，其元素的个数必定为 pn，其中 p 为一个素数(有限域的特征)，n 为一个正整数.数组
例1(有限域 GF(p)) 令 p 为一个素数，集合
svg
GF(p)=Zp={0,1,2,…,p−1}.
在
GF(p)
上定义加法
⊕
和乘法
⊙
分别为模
p
加法和模
p
乘法，即任意的
a,b∈GF(p)
，
a⊕b=(a+b)modp,a⊙b=(a⋅b)modp
则
为一个有
p
个元素的有限域，其中零元素为
0
，单位元为
1
.
令 a 为 GF(p) 中的一个非零元素. 因为 gcd(a,p)=1，所以，存在整数 b,c，使得 ab+pc=1. 由此获得 a 的逆元为 a−1=bmodp.函数
域 GF(p) 称为一个素域(prime field).this
例注1： 给定 a 和 p，例1中的等式 ab+pc=1 能够经过扩展的欧几里得除法获得，从而求得 GF(p) 中任意非零元素的逆元.atom
例2(有限域 GF(pn)) 从 GF(p) 出发，对任意正整数 n，n≥2，咱们能够构造元素元素个数为 pn 的有限域 GF(pn) 以下：
令 g(x) 为一个 GF(p) 上次数为 n 的不可约多项式，集合
spa
GF(pn)=GF(p)[x]/⟨g(x)⟩={a0+a1x+a2x2+⋯+an−1xn−1|ai∈GF(p),0≤i≤n−1}
在
GF(pn)
上定义加法
⊕
和乘法
⊙
分别为模
g(x)
加法和模
g(x)
乘法，即任意的
a(x),b(x)∈GF(pn)
，
a(x)⊕b(x)=a(x)+b(x),a(x)⊙b(x)=(a(x)⋅b(x))modg(x)
则
为一个有
pn
个元素，特征为
p
的有限域，其中零元素为
GF(p)
中的
0
，单位元为
GF(p)
中的
1
.
令 a(x) 为 GF(pn) 中的一个非零元素. 因为 gcd(a(x),g(x))=1，所以，存在 GF(p) 上的多项式 b(x),c(x)，使得 a(x)b(x)+g(x)c(x)=1. 由此获得 a(x) 的逆元为 a−1(x)=b(x)modg(x).code
域 GF(pn) 称为 GF(p) 的(n 次)扩域(extension field)，而 GF(p) 称为 GF(pn) 的子域(subfield).orm
例注2.1： 给定 GF(p) 上的多项式 a(x) 和 g(x)，例2中的等式 a(x)b(x)+g(x)c(x)=1 能够经过扩展的欧几里得除法获得，从而求得 GF(pn) 中任意非零元素的逆元.xml
例注2.2：设 GF(q) 是一个含有 q 个元素的有限域. 对任意正整数 n, GF(q) 上的 n 次不可约多项式必定存在. 更进一步，GF(q) 上首项系数为 1 的 n 次不可约多项式的个数为
Nq(n)=1n∑d|nμ(nd)qd=1n∑d|nμ(d)qn/d
其中
μ
为Moebius函数，定义为
μ(m)=⎧⎩⎨1(−1)k0如果m=1如果m=p1p2⋯pk,其中p1,p2,…,pk为互不相同的素数其它
1.2 有限域的性质
令 GF(q) 是一个含有 q 个元素的有限域，F∗q=GF(q)∖{0} 为有限域 GF(q) 中全部非零元素构成的集合. 则在乘法之下 F∗q 是一个有限循环群. 循环群 F∗q 的一个生成元称为有限域 GF(q) 的一个本原元.
若 α∈GF(q) 为一个本原元，则
GF(q)={0,1,α,α2,…,αq−2}
而且
αq−1=1
，即
αq=α
.
定义：设 GF(q) 是一个含有 q 个元素的有限域，GF(p) 是 GF(q) 的一个含有 p 个元素的子域(p 不必定为素数)，α∈GF(q). 则 GF(p) 上以 α 为根，首项系数为 1，而且次数最低的多项式称为 α 在 GF(p) 上的极小多项式(minimal polynomial of α over GF(p)).
特别地，若 α∈GF(q) 为 GF(q) 的一个本原元，则 α 在 GF(p) 上的极小多项式称为 GF(p) 上的一个本原多项式(primitive polynomial for GF(q) over GF(p)).
定义注1：对任意的 α∈GF(q)， α 在 GF(p) 上的极小多项式存在而且惟一，而且 α 在 GF(p) 上的极小多项式为 GF(p) 上的一个不可约多项式.
定义注2：设 α∈GF(q)， 则 α 和 αp 在 GF(p) 上具备相同的极小多项式. 更进一步，集合
B(α)={α,αp,αp2,αp3,…,αpi,…}
中的元素具备相同的极小多项式. 设
q=pn
，则
αpn=α
. 所以，集合
B(α)
中互不相同的元素的个数(记为
r
)不超过
n
. 能够证实，
α
为
GF(q)
的一个本原元当且仅当
r=n
.
定理：设 GF(q) 是一个含有 q 个元素的有限域，GF(p) 是 GF(q) 的一个含有 p 个元素的子域. 设 α∈GF(q)，r 为知足 αpr=α 的最小正整数. 则 α 在 GF(p) 上的极小多项式 g(x) 是一个 r 次不可约多项式，而且
B(α)={α,αp,αp2,…,αpr−1}
中的元素为
g(x)
在
GF(q)
上的全部不一样的根，即
g(x)=(x−α)(x−αp)(x−αp2)⋯(x−αpr−1).
注：r 的计算方法以下：设 α 在 F∗q 中的阶为 k. 集合
Z∗k={m|0≤m≤k−1,gcd(m,k)=1}
在模
k
乘法运算下是一个含有
φ(k)
个元素的有限群(其中
φ
为欧拉(Euler)函数). 则
r
等于
pmodk
在
Z∗k
中的阶.
推论：设 GF(q) 是一个含有 q 个元素的有限域，GF(p) 是 GF(q) 的一个含有 p 个元素的子域. 设 |GF(q)|=pn，即 q=pn. 设 α∈GF(q) 为 GF(q) 的一个本原元，则 α 在 GF(p) 上的极小多项式 g(x) 的次数为 n，而且
g(x)=(x−α)(x−αp)(x−αp2)⋯(x−αpn−1).
更进一步，
α,αp,αp2,…,αpn−1
均为
GF(q)
的本原元.
注：设 GF(p) 是一个含有 p 个元素的有限域，n 是任意一个正整数，则 GF(p) 上的 n 次本原多项式必定存在. 更进一步，GF(p) 上的首项系数为 1 的 n 次本原多项式的个数为 φ(pn−1)n，其中 φ 为欧拉函数.
例3 考虑二元域 GF(2) 上的不可约多项式 p(α)=α3+α+1，构造有限域
GF(23)=GF(2)[α]/⟨p(α)⟩={0,1,α,α+1,α2,α2+1,α2+α,α2+α+1}.
容易验证，
α,α2,α3,α4,α5,α6
都是
GF(23)
的本原元.
GF(2)
上的首项系数为
1
的
3
次本原多项式有两个，分别为
(i)
α,α2,α4
在
GF(2)
上的极小多项式
g(x)=(x+α)(x+α2)(x+α4)=x3+x+1
(ii)
α3,α5,α6
在
GF(2)
上的极小多项式
g(x)=x3+x2+1
有限域 GF(p) 上的本原多项式必定是 GF(p) 上的不可约多项式；可是，GF(p) 上的不可约多项式不必定是 GF(p) 上的本原多项式.
定理：设 GF(q) 是一个含有 q 个元素的有限域，GF(p) 是 GF(q) 的一个含有 p 个元素的子域， g(x) 是 GF(p) 上的一个不可约多项式. 则 g(x) 为 GF(p) 上的本原多项式当且仅当 g(x) 在 GF(q) 上的根都是 GF(q) 的本原元.
下面例子说明不可约多项式不必定是本原多项式.
例4 考虑二元域 GF(2) 上的不可约多项式 p(x)=x4+x3+x2+x+1，构造有限域
GF(24)=GF(2)[x]/⟨p(x)⟩={a+bx+cx2+dx3|a,b,c,d∈GF(2)}.
显然，
x∈GF(24)
. 因为
x5=1
，即
x
的阶为
5
，所以，
x
不是
GF(24)
的本原元. 因而，
p(x)
不是
GF(2)
上的本原多项式. 另外，能够验证
x+1
是
GF(24)
的本原元.
2 Matlab 中的有限域计算函数
Matlab 中自带的有限域的计算是在 GF(2m) 上进行的，即在二元域 GF(2) 的扩域中进行计算，其中 1≤m≤16.
由 “1.1 有限域的构造” 的 “例2” 可知，咱们只需先找到一个 GF(2) 上的 m 次不可约多项式 g(x)，获得集合 GF(2)[x]/⟨g(x)⟩，而后定义其上的加法和乘法分别为模 g(x) 加法和模 g(x) 乘法，即获得有限域 GF(2m).
然而，这样获得的有限域 GF(2m) 中，元素 x 未必是本原元，这将给后面的(乘法)运算带来不少麻烦. 所以，在不可约多项式 g(x) 的挑选上，咱们最好选择一个本原多项式. 这其实就是 Matlab 中的作法.
Matlab 中 GF(2m) 的元素： 在 Matlab 中 GF(2m):=GF(2)[D]/⟨p(D)⟩，其中 p(D) 为一个 GF(2) 上的 m 次本原多项式.
GF(2m)={am−1Dm−1+am−2Dm−2+⋯+a1D+a0,|ai∈GF(2),0≤i≤m−1}
所以，每一个
GF(2m)
中的元素
本质上是一个次数小于
m
的多项式，每一个元素和多项式之间有“1-1”对应关系. 例如，取
m=3
和本原多项式
p(D)=D3+D+1
，则咱们获得有限域
GF(23)
，其中的元素和多项式之间的对应关系以下：
GF(23)
GF(2)[D]/⟨p(D)⟩
二进制
0
0
000
1
1
001
2
D
010
3
D+1
011
4
D2
100
5
D2+1
101
6
D2+D
110
7
D2+D+1
111
GF(2) 上的多项式由系数组成的二进制所对应的(十进制)数字来表示. 例如，多项式 p(D)=D3+D+1 的系数组成的二进制为 1011，所以，多项式 p(D) 表示为数字 11.
2.1 定义有限域数组
在 Matlab 中，函数 gf 用来定义一个有限域数组，函数申明以下：
X_GF = GF(X,M,PRIM_POLY)
函数建立有限域 GF(2M) 上的一个数组，使用的 GF(2) 上的 M 次本原多项式为 PRIM_POLY； M 是一个 1 至 16 之间的整数；数组 X 中的元素为 0 至 2M−1 之间的数.
例如，生成有限域 GF(23) 中的全部元素，并令本原多项式为 p(D)=D3+D2+1.
>> GF8 = gf(0:7,3,13)
GF8 = GF(2^3) array. Primitive polynomial = D^3+D^2+1 (13 decimal)
Array elements =
0 1 2 3 4 5 6 7
若是不指定本原多项式，则 Matlab 将使用默认本原多项式. 例如
>> gf(0:7,3)
ans = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)
Array elements =
0 1 2 3 4 5 6 7
在这里例子中，Matlab 使用了 3 次本原多项式 D3+D+1.
若是不指定次数 M 和本原多项式 PRIM_POLY，则生成二元域 GF(2) 中的元素.
>> gf(0:1)
ans = GF(2) array.
Array elements =
0 1
生成的有限域中的数组能够参与运算(+、、.、.^、\等). 注意：参与运算的操做数必须来自同一个有限域，用于生成有限域的本原多项式也必须相同！
一个典型的例子是计算有限域的乘法表以下：
>> GF8 = gf(0:7,3)
GF8 = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)
Array elements =
0 1 2 3 4 5 6 7
>> GF8'*GF8
ans = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)
Array elements =
0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7
0 2 4 6 3 1 7 5
0 3 6 5 7 4 1 2
0 4 3 7 6 2 5 1
0 5 1 4 2 7 3 6
0 6 7 1 5 3 2 4
0 7 5 2 1 6 4 3
>> GF8 = gf(0:7,3,13)
GF8 = GF(2^3) array. Primitive polynomial = D^3+D^2+1 (13 decimal)
Array elements =
0 1 2 3 4 5 6 7
>> GF8'*GF8
Warning: Lookup tables not defined for this order 2^3 and
primitive polynomial 13. Arithmetic still works
correctly but multiplication, exponentiation, and
inversion of elements is faster with lookup tables.
Use gftable to create and save the lookup tables.
> In gf.gettables at 35
In gf.mtimes at 20
ans = GF(2^3) array. Primitive polynomial = D^3+D^2+1 (13 decimal)
Array elements =
0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7
0 2 4 6 5 7 1 3
0 3 6 5 1 2 7 4
0 4 5 1 7 3 2 6
0 5 7 2 3 6 4 1
0 6 1 7 2 4 3 5
0 7 3 4 6 1 5 2
在这里咱们用两个不一样的本原多项式构造有限域 GF(23)，获得两张不一样的乘法表.
注1：当咱们计算 GF(2)[D]/⟨D3+D2+1⟩ 的乘法表时，Matlab 给产生一个警告 “Warning: Lookup tables not defined for this order 2^3 and primitive polynomial 13.” 从警告中咱们能够看出，Matlab 中有限域的乘法是经过查表来完成的，这样能够显著地提升计算的速度. 咱们能够经过命令 gftable 来建立并保存查找表格.
注2：用本原多项式 D3+D+1 和 D3+D2+1 生成两个不一样的元素个数为 8 的有限域，然而这两个有限域是同构的. 通常地，咱们有以下有限域同构定理：
定理： 任意两个元素个数相同的有限域必定同构.
与本原元多项式相关的函数
primpoly
函数 primpoly 用于计算 GF(2) 上的本原多项式，函数申明以下：
PR = PRIMPOLY(M, OPT, 'nodisplay')
其中 M 为本原多项式的次数，其取值为 2 至 16 之间的整数；选项 OPT 的定义以下：
OPT = 'min' 给出一个权值最小的本原多项式
OPT = 'max' 给出一个权值最大的本原多项式
OPT = 'all' 给出全部的本原多项式
OPT = L 给出全部权值为L的本原多项式
字符串 ‘nodisplay’ 用于关闭默认的本原多项式显示方式.
例如，输出 GF(2) 上全部次数为 3 的本原多项式.
>> primpoly(3,'all')
Primitive polynomial(s) =
D^3+D^1+1
D^3+D^2+1
ans =
11
13
>> primpoly(3,'all','nodisplay')
ans =
11
13
isprimitive
函数 isprimitive 用来检查 GF(2) 上的多项式是否为本原多项式，函数申明以下：
CK = ISPRIMITIVE(A)
其中 A 为一个表示多项式的数字，而且表示的多项式的次数不能超过 16. 若是 A 为本原多项式，则返回 1；不然返回 0.
例如，检查多项式 D3+D2+1 和 D3+D2+D+1 是否为本原多项式以下：
>> isprimitive(13)
ans =
1
>> isprimitive(15)
ans =
0
其它函数
见 Matlab 帮助.
