1、1 有限域基礎知識1.1 有限域（Galois域）的構造令 p 為一個素數. 則對任意的一個正整數 n，存在一個特征為 p，元素個數為 pn 的有限域 GF(pn).注：任意一個有限域，其元素的個數一定為 pn，其中 p 為一個素數（有限域的特征），n 為一個正整數.例1（有限域 GF(p)） 令 p 為一個素數，集合 GF(p)=Zp=0,1,2,p1.在 GF(p) 上定義加法 和乘法 分別為模 p 加法和模 p 乘法，即任意的 a,bGF(p)， ab=(a+b)modp, ab=(ab)modp則 <GF(p),> 為一個有 p 個元素的有限域，其中零元素為 0，

2、單位元為 1.令 a 為 GF(p) 中的一個非零元素. 由于 gcd(a,p)=1，因此，存在整數 b,c，使得 ab+pc=1. 由此得到 a 的逆元為 a1=bmodp.域 GF(p) 稱為一個素域(prime field).例注1： 給定 a 和 p，例1中的等式 ab+pc=1 可以通過擴展的歐幾里得除法得到，從而求得 GF(p) 中任意非零元素的逆元.例2（有限域 GF(pn)） 從 GF(p) 出發，對任意正整數 n，n2，我們可以構造元素元素個數為 pn 的有限域 GF(pn) 如下： 令 g(x) 為一個 GF(p) 上次數為 n 的不可約多項式，集合 GF(pn)=GF(p

3、)x/g(x)=a0+a1x+a2x2+an1xn1 | aiGF(p),0in1在 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) 上的多

4、項式 b(x),c(x)，使得 a(x)b(x)+g(x)c(x)=1. 由此得到 a(x) 的逆元為 a1(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 次不

5、可約多項式一定存在. 更進一步，GF(q) 上首項系數為 1 的 n 次不可約多項式的個數為 Nq(n)=1nd|n(nd)qd=1nd|n(d)qn/d其中 為Moebius函數，定義為 (m)=1(1)k0如果m=1如果m=p1p2pk,其中p1,p2,pk為互不相同的素數其它1.2 有限域的性質令 GF(q) 是一個含有 q 個元素的有限域，Fq=GF(q)0 為有限域 GF(q) 中所有非零元素構成的集合. 則在乘法之下 Fq 是一個有限循環群. 循環群 Fq 的一個生成元稱為有限域 GF(q) 的一個本原元.若 GF(q) 為一個本原元，則 GF(q)=0,1,2,q2并且 q1=1

6、，即 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) 上的極小多項

7、式存在并且唯一，并且 在 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) 上的極小

8、多項式 g(x) 是一個 r 次不可約多項式，并且 B()=,p,p2,pr1中的元素為 g(x) 在 GF(q) 上的所有不同的根，即 g(x)=(x)(xp)(xp2)(xpr1).注：r 的計算方法如下：設 在 Fq 中的階為 k. 集合 Zk=m | 0mk1,gcd(m,k)=1在模 k 乘法運算下是一個含有 (k) 個元素的有限群（其中 為歐拉(Euler)函數）. 則 r 等于 pmodk 在 Zk 中的階.推論：設 GF(q) 是一個含有 q 個元素的有限域，GF(p) 是 GF(q) 的一個含有 p 個元素的子域. 設 |GF(q)|=pn，即 q=pn.

9、 設 GF(q) 為 GF(q) 的一個本原元，則 在 GF(p) 上的極小多項式 g(x) 的次數為 n，并且 g(x)=(x)(xp)(xp2)(xpn1).更進一步，,p,p2,pn1 均為 GF(q) 的本原元.注：設 GF(p) 是一個含有 p 個元素的有限域，n 是任意一個正整數，則 GF(p) 上的 n 次本原多項式一定存在. 更進一步，GF(p) 上的首項系數為 1 的 n 次本原多項式的個數為 (pn1)n，其中 為歐拉函數.例3 考慮二元域 GF(2) 上的不可約多項式 p()=3+1，構造有限域 GF(23)=GF(2)/p()=0,1,+1,2,2+1,2+,2+1.容

10、易驗證，,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) 上的

11、一個不可約多項式. 則 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,dGF(2).顯然，xGF(24). 由于 x5=1，即 x 的階為 5，因此，x 不是 GF(24) 的本原元. 于是， p(x) 不是 GF(2) 上的本原多項式. 另外，可以驗證 x+1 是 GF(24) 的本原元.2

12、Matlab 中的有限域計算函數Matlab 中自帶的有限域的計算是在 GF(2m) 上進行的，即在二元域 GF(2) 的擴域中進行計算，其中 1m16. 由 “1.1 有限域的構造” 的 “例2” 可知，我們只需先找到一個 GF(2) 上的 m 次不可約多項式 g(x)，得到集合 GF(2)x/g(x)，然后定義其上的加法和乘法分別為模 g(x) 加法和模 g(x) 乘法，即得到有限域 GF(2m).然而，這樣得到的有限域 GF(2m) 中，元素 x 未必是本原元，這將給后面的（乘法）運算帶來很多麻煩. 因此，在不可約多項式 g(x) 的挑選上，我們最好選擇一個本原多項式. 這其實就是 Ma

13、tlab 中的做法.Matlab 中 GF(2m) 的元素： 在 Matlab 中 GF(2m):=GF(2)D/p(D)，其中 p(D) 為一個 GF(2) 上的 m 次本原多項式. GF(2m)=am1Dm1+am2Dm2+a1D+a0, | aiGF(2),0im1因此，每個 GF(2m) 中的元素本質上是一個次數小于 m 的多項式，每個元素和多項式之間有“1-1”對應關系. 例如，取 m=3 和本原多項式 p(D)=D3+D+1，則我們得到有限域 GF(23)，其中的元素和多項式之間的對應關系如下：GF(23)GF(2)D/p(D)二進制00000110012D01

14、03D+10114D21005D2+11016D2+D1107D2+D+1111GF(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 至 2M1 之間的

15、數. 例如，生成有限域 GF(23) 中的所有元素，并令本原多項式為 p(D)=D3+D2+1.>> GF8 = gf(0:7,3,13)GF8 = GF(23) array. Primitive polynomial = D3+D2+1 (13 decimal)Array elements = 0 1 2 3 4 5 6 7如果不指定本原多項式，則 Matlab 將使用默認本原多項式. 例如>> gf(0:7,3)ans = GF(23) array. Primitive polynomial = D3+D+1 (11 decimal)Array elements =

16、 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(23) array. Primitive polynomi

17、al = D3+D+1 (11 decimal)Array elements = 0 1 2 3 4 5 6 7>> GF8'*GF8ans = GF(23) array. Primitive polynomial = D3+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

18、(0:7,3,13)GF8 = GF(23) array. Primitive polynomial = D3+D2+1 (13 decimal)Array elements = 0 1 2 3 4 5 6 7>> GF8'*GF8Warning: Lookup tables not defined for this order 23 andprimitive polynomial 13. Arithmetic still workscorrectly but multiplication, exponentiation, andinversion of elements

19、is faster with lookup tables.Use gftable to create and save the lookup tables. > In gf.gettables at 35 In gf.mtimes at 20ans = GF(23) array. Primitive polynomial = D3+D2+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

20、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 23 and primitive polynomial 13.” 從警告中我們可以看出，Matlab 中有限域的乘法是通過查表來完成的，這樣可以顯著地提高計算的速度. 我們可以通過命令 gftable 來創建并保存查找表格. 注2：用本原多項式 D3+D+1 和 D3+D2+1 生成兩個不同的元素個數為 8 的有限域，然而這兩個有限域是同構的. 一般地，我們有如下有限域同構定理：定理： 任意兩個元素個數相同的有限域一定同構.與本原元多項式相關的函數primpoly函數 primpoly 用