1 有限域基础知识
1.1 有限域（Galois域）的构造
令 p 为一个素数. 则对任意的一个正整数 n，存在一个特征为 p，元素个数为 pn 的有限域 GF(pn). 注：任意一个有限域，其元素的个数一定为 pn，其中 p 为一个素数（有限域的特征），n 为一个正整数.
例1（有限域 GF(p)） 令 p 为一个素数，集合
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
则 <GF(p),⊕,⊙> 为一个有 p 个元素的有限域，其中零元素为 0，单位元为 1.
令 a 为 GF(p) 中的一个非零元素. 由于 gcd(a,p)=1，因此，存在整数 b,c，使得 ab+pc=1. 由此得到 a 的逆元为 a−1=bmodp.
域 GF(p) 称为一个素域(prime field).
例注1： 给定 a 和 p，例1中的等式 ab+pc=1 可以通过扩展的欧几里得除法得到，从而求得 GF(p) 中任意非零元素的逆元.
例2（有限域 GF(pn)） 从 GF(p) 出发，对任意正整数 n，n≥2，我们可以构造元素元素个数为 pn 的有限域 GF(pn) 如下：
令 g(x) 为一个 GF(p) 上次数为 n 的不可约多项式，集合
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)
则 <GF(pn),⊕,⊙> 为一个有 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).
域 GF(pn) 称为 GF(p) 的（n 次）扩域(extension field)，而 GF(p) 称为 GF(pn) 的子域(subfield).
例注2.1： 给定 GF(p) 上的多项式 a(x) 和 g(x)，例2中的等式 a(x)b(x)+g(x)c(x)=1 可以通过扩展的欧几里得除法得到，从而求得 GF(pn) 中任意非零元素的逆元.
例注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. 集合
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议