matlab有限域上的運(yùn)算

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

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

3、x2+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)則 為一個(gè)有 pn 個(gè)元素，特征為 p 的有限域，其中零元素為 GF(p) 中的 0，單位元為 GF(p) 中的 1.令 a(x) 為 GF(pn) 中的一個(gè)非零元素. 由于 gcd(a(x),g(x)=1，因此，存在 GF(p) 上的多項(xiàng)式 b(x),c(x)，使得 a(x)b(x)+g(x)c(x)=1. 由此得到 a(x) 的逆元為

4、 a1(x)=b(x)modg(x).域 GF(pn) 稱為 GF(p) 的（n 次）擴(kuò)域(extension field)，而 GF(p) 稱為 GF(pn) 的子域(subfield).推薦精選例注2.1： 給定 GF(p) 上的多項(xiàng)式 a(x) 和 g(x)，例2中的等式 a(x)b(x)+g(x)c(x)=1 可以通過擴(kuò)展的歐幾里得除法得到，從而求得 GF(pn) 中任意非零元素的逆元.例注2.2：設(shè) GF(q) 是一個(gè)含有 q 個(gè)元素的有限域. 對任意正整數(shù) n, GF(q) 上的 n 次不可約多項(xiàng)式一定存在. 更進(jìn)一步，GF(q) 上首項(xiàng)系數(shù)為 1 的 n 次不可約多項(xiàng)式的個(gè)數(shù)為

5、Nq(n)=1nd|n(nd)qd=1nd|n(d)qn/d其中 為Moebius函數(shù)，定義為 (m)=1(1)k0如果m=1如果m=p1p2pk,其中p1,p2,pk為互不相同的素?cái)?shù)其它1.2 有限域的性質(zhì)令 GF(q) 是一個(gè)含有 q 個(gè)元素的有限域，F(xiàn)q=GF(q)0 為有限域 GF(q) 中所有非零元素構(gòu)成的集合. 則在乘法之下 Fq 是一個(gè)有限循環(huán)群. 循環(huán)群 Fq 的一個(gè)生成元稱為有限域 GF(q) 的一個(gè)本原元.若 GF(q) 為一個(gè)本原元，則 GF(q)=0,1,2,q2并且 q1=1，即 q=.定義：設(shè) GF(q) 是一個(gè)含有 q 個(gè)元素的有限域，GF(p) 是 GF(q)

6、的一個(gè)含有 p 個(gè)元素的子域（p 不一定為素?cái)?shù)），GF(q). 則 GF(p) 上以 為推薦精選根，首項(xiàng)系數(shù)為 1，并且次數(shù)最低的多項(xiàng)式稱為 在 GF(p) 上的極小多項(xiàng)式(minimal polynomial of over GF(p). 特別地，若 GF(q) 為 GF(q) 的一個(gè)本原元，則 在 GF(p) 上的極小多項(xiàng)式稱為 GF(p) 上的一個(gè)本原多項(xiàng)式(primitive polynomial for GF(q) over GF(p).定義注1：對任意的 GF(q)， 在 GF(p) 上的極小多項(xiàng)式存在并且唯一，并且 在 GF(p) 上的極小多項(xiàng)式為 GF(p) 上的一個(gè)不可約多項(xiàng)

7、式.定義注2：設(shè) GF(q)， 則 和 p 在 GF(p) 上具有相同的極小多項(xiàng)式. 更進(jìn)一步，集合 B()=,p,p2,p3,pi,中的元素具有相同的極小多項(xiàng)式. 設(shè) q=pn，則 pn=. 因此，集合 B() 中互不相同的元素的個(gè)數(shù)（記為 r）不超過 n. 可以證明， 為 GF(q) 的一個(gè)本原元當(dāng)且僅當(dāng) r=n.定理：設(shè) GF(q) 是一個(gè)含有 q 個(gè)元素的有限域，GF(p) 是 GF(q) 的一個(gè)含有 p 個(gè)元素的子域. 設(shè) GF(q)，r 為滿足 pr= 的最小正整數(shù). 則 在 GF(p) 上的極小多項(xiàng)式 g(x) 是一個(gè) r 次不可約多項(xiàng)式，并且 B()=,p,p2,pr1中的元素

8、為 g(x) 在 GF(q) 上的所有不同的根，即 g(x)=(x)(xp)(xp2)(xpr1).推薦精選注：r 的計(jì)算方法如下：設(shè) 在 Fq 中的階為 k. 集合 Zk=m|0mk1,gcd(m,k)=1在模 k 乘法運(yùn)算下是一個(gè)含有 (k) 個(gè)元素的有限群（其中 為歐拉(Euler)函數(shù)）. 則 r 等于 pmodk 在 Zk 中的階.推論：設(shè) GF(q) 是一個(gè)含有 q 個(gè)元素的有限域，GF(p) 是 GF(q) 的一個(gè)含有 p 個(gè)元素的子域. 設(shè) |GF(q)|=pn，即 q=pn. 設(shè) GF(q) 為 GF(q) 的一個(gè)本原元，則 在 GF(p) 上的極小多項(xiàng)式 g(x) 的次數(shù)為

9、 n，并且 g(x)=(x)(xp)(xp2)(xpn1).更進(jìn)一步，,p,p2,pn1 均為 GF(q) 的本原元.注：設(shè) GF(p) 是一個(gè)含有 p 個(gè)元素的有限域，n 是任意一個(gè)正整數(shù)，則 GF(p) 上的 n 次本原多項(xiàng)式一定存在. 更進(jìn)一步，GF(p) 上的首項(xiàng)系數(shù)為 1 的 n 次本原多項(xiàng)式的個(gè)數(shù)為 (pn1)n，其中 為歐拉函數(shù).例3 考慮二元域 GF(2) 上的不可約多項(xiàng)式 p()=3+1，構(gòu)造有限域 GF(23)=GF(2)/p()=0,1,+1,2,2+1,2+,2+1.容易驗(yàn)證，,2,3,4,5,6 都是 GF(23) 的本原元. GF(2) 上的首項(xiàng)系數(shù)為 1 的 3

10、次本原多項(xiàng)式有兩個(gè)，分別為 (i) ,2,4 在 GF(2) 上的極小多項(xiàng)式 推薦精選g(x)=(x+)(x+2)(x+4)=x3+x+1(ii) 3,5,6 在 GF(2) 上的極小多項(xiàng)式 g(x)=x3+x2+1有限域 GF(p) 上的本原多項(xiàng)式一定是 GF(p) 上的不可約多項(xiàng)式；但是，GF(p) 上的不可約多項(xiàng)式不一定是 GF(p) 上的本原多項(xiàng)式. 定理：設(shè) GF(q) 是一個(gè)含有 q 個(gè)元素的有限域，GF(p) 是 GF(q) 的一個(gè)含有 p 個(gè)元素的子域， g(x) 是 GF(p) 上的一個(gè)不可約多項(xiàng)式. 則 g(x) 為 GF(p) 上的本原多項(xiàng)式當(dāng)且僅當(dāng) g(x) 在 GF(

11、q) 上的根都是 GF(q) 的本原元.下面例子說明不可約多項(xiàng)式不一定是本原多項(xiàng)式.例4 考慮二元域 GF(2) 上的不可約多項(xiàng)式 p(x)=x4+x3+x2+x+1，構(gòu)造有限域 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) 上的本原多項(xiàng)式. 另外，可以驗(yàn)證 x+1 是 GF(24) 的本原元.2 Matlab 中的有限域計(jì)算函數(shù)Matlab 中自帶的有限域的計(jì)算是在 GF(2m) 上進(jìn)行的，即在二元域 GF(2)

12、 的擴(kuò)域中進(jìn)行計(jì)算，其中 1m16. 推薦精選由 “1.1 有限域的構(gòu)造” 的 “例2” 可知，我們只需先找到一個(gè) GF(2) 上的 m 次不可約多項(xiàng)式 g(x)，得到集合 GF(2)x/g(x)，然后定義其上的加法和乘法分別為模 g(x) 加法和模 g(x) 乘法，即得到有限域 GF(2m).然而，這樣得到的有限域 GF(2m) 中，元素 x 未必是本原元，這將給后面的（乘法）運(yùn)算帶來很多麻煩. 因此，在不可約多項(xiàng)式 g(x) 的挑選上，我們最好選擇一個(gè)本原多項(xiàng)式. 這其實(shí)就是 Matlab 中的做法.Matlab 中 GF(2m) 的元素： 在 Matlab 中 GF(2m):=GF(2)

13、D/p(D)，其中 p(D) 為一個(gè) GF(2) 上的 m 次本原多項(xiàng)式. GF(2m)=am1Dm1+am2Dm2+a1D+a0,|aiGF(2),0im1因此，每個(gè) GF(2m) 中的元素本質(zhì)上是一個(gè)次數(shù)小于 m 的多項(xiàng)式，每個(gè)元素和多項(xiàng)式之間有“1-1”對應(yīng)關(guān)系. 例如，取 m=3 和本原多項(xiàng)式 p(D)=D3+D+1，則我們得到有限域 GF(23)，其中的元素和多項(xiàng)式之間的對應(yīng)關(guān)系如下：GF(23)GF(2)D/p(D)二進(jìn)制00000110012D0103D+10114D21005D2+1101推薦精選GF(23)GF(2)D/p(D)二進(jìn)制6D2+D1107D2+D+1111GF(

14、2) 上的多項(xiàng)式由系數(shù)組成的二進(jìn)制所對應(yīng)的（十進(jìn)制）數(shù)字來表示. 例如，多項(xiàng)式 p(D)=D3+D+1 的系數(shù)組成的二進(jìn)制為 1011，因此，多項(xiàng)式 p(D) 表示為數(shù)字 11.2.1 定義有限域數(shù)組在 Matlab 中，函數(shù) gf 用來定義一個(gè)有限域數(shù)組，函數(shù)申明如下：X_GF = GF(X,M,PRIM_POLY)函數(shù)創(chuàng)建有限域 GF(2M) 上的一個(gè)數(shù)組，使用的 GF(2) 上的 M 次本原多項(xiàng)式為 PRIM_POLY； M 是一個(gè) 1 至 16 之間的整數(shù)；數(shù)組 X 中的元素為 0 至 2M1 之間的數(shù). 例如，生成有限域 GF(23) 中的所有元素，并令本原多項(xiàng)式為 p(D)=D3+

15、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如果不指定本原多項(xiàng)式，則 Matlab 將使用默認(rèn)本原多項(xiàng)式. 例如推薦精選 gf(0:7,3)ans = GF(23) array. Primitive polynomial = D3+D+1 (11 decimal)Array elements = 0 1 2 3 4 5 6 7在這里例子中，Matlab 使用了 3 次本原多項(xiàng)式 D3+D+1.如果不指定

16、次數(shù) M 和本原多項(xiàng)式 PRIM_POLY，則生成二元域 GF(2) 中的元素. gf(0:1)ans = GF(2) array. Array elements = 0 1生成的有限域中的數(shù)組可以參與運(yùn)算（+、.、.、等). 注意：參與運(yùn)算的操作數(shù)必須來自同一個(gè)有限域，用于生成有限域的本原多項(xiàng)式也必須相同！一個(gè)典型的例子是計(jì)算有限域的乘法表如下： GF8 = gf(0:7,3)GF8 = GF(23) array. Primitive polynomial = D3+D+1 (11 decimal)Array elements = 0 1 2 3 4 5 6 7 GF8*GF8ans = G

17、F(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(0:7,3,13)GF8 = GF(23) array. Primitive polynomial = D3+D2+1 (13 decimal)Array elements

18、= 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 is faster with lookup tables.Use gftable to create and save the lookup tables. In gf.gettables at 35

19、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 0 6 1 7 2 4 3 5 0 7 3 4 6 1 5 2在這里我們用兩個(gè)不同的本原多項(xiàng)式構(gòu)造有限域 GF(23)，得到兩張不同的乘法表.注1：當(dāng)我們計(jì)算 GF(2)D/D3+D2+1 的乘法表時(shí)，Matlab 給產(chǎn)生一個(gè)警告 “Warning: Lookup tables not defined for this order 23 and primitive polynomial 13.” 從警告中我們可以看出，Matlab 中有限域的乘法是通過查表來完成的，這樣可以顯著地提高計(jì)算的速度. 我們可以通過命令 gftable 來創(chuàng)建并保存查找表格. 推薦精選注2：用本原多項(xiàng)式 D3+D+1 和 D3+D2+1 生成兩個(gè)不同的元素個(gè)數(shù)為 8 的有限域，然而這兩個(gè)有限域是同構(gòu)的. 一般地，我們有如下有限域同構(gòu)定理：定理： 任