matlab有限域上的運算

1、1有限域基礎(chǔ)知識1、1有限域(Galois域)的構(gòu)造令p為一個素數(shù)、則對任意的一個正整數(shù)n,存在一個特征為p,元素個數(shù)為pn的有限域GF(pn)、注:任意一個有限域，其元素的個數(shù)一定為 pn,其中p為一個素數(shù)(有限域的特 征)，n為一個正整數(shù)、例1(有限域GF(p)令p為一個素數(shù)，集合GF(p)=Zp=0,1,2,p-,1、在GF(p)上定義加法 與乘法 O分別為模p加法與模p乘法，即任意 的 a,b GF(p),a b=(a+b)modp, aO b=(a%)modp則GF(p),O為一個有p個元素的有限域，其中零元素為0,單位元為1、令a為GF(p)中的一個非零元素、 由于gcd(a,p)

2、=1,因此，存在整數(shù)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)出發(fā)，對任意正整數(shù)n,n>2我們可以構(gòu)造元素元素個數(shù)為pn的有限域GF(pn)如下：令g(x)為一個GF(p)上次數(shù)為n的不可約多項式，集合GF(pn)=GF(p)x/?g(x)?=a0+aix+a2X2+? +an-ixn-i | ai GGF(p),0 所-1在GF(pn)上定義加法 與乘

3、法 O分別為模g(x)加法與模g(x)乘法, 即任意的 a(x),b(x)G GF(pn),a(x) b(x)=a(x)+b(x), a(x)O b(x)=(a(x)?D(x)modg(x)則 <GF(pn), ,O>為一個有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

4、)的(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：設(shè)GF(q)就是一個含有q個元素的有限域、對任意正整數(shù)n,GF(q)上的n次不可約多項式一定存在、 更進一步，GF(q)上首項系數(shù)為1 的n次不可約多項式的個數(shù)為Nq(n)=1nDi|n Mnd)qd=1nDi|n Md)qn/d其中為Moebius函數(shù)，定義為Mm)=? 1(-1)

5、k0 如果 m=1 如果 m=p1p2? pk,其中 p1,p2, pk為互不相同的素數(shù)其它1、2有限域的性質(zhì)令GF(q)就是一個含有q個元素的有限域，F(xiàn)?q=GF(q)?0為有限域GF(q)中所有非零元素構(gòu)成的集合、則在乘法之下F?q就是一個有限循環(huán) 群、循環(huán)群F?q的一個生成元稱為有限域 GF(q)的一個本原元、若慶 GF(q)為一個本原元，則GF(q)=0,1, 3,-2并且oq-1 = 1,即oq= a、定義：設(shè)GF(q)就是一個含有q個元素的有限域，GF(p)就是GF(q)的一 個含有p個元素的子域(p不一定為素數(shù)),氏GF(q)、則GF(p)上以5 為根，首項系數(shù)為1,并且次數(shù)最低

6、的多項式稱為a在GF(p)上的極小多項 式(minimal polynomial ofa over GF(p)、特別地，若 /GF(q)為GF(q)的一個本原元，則a在GF(p)上的極小 多項式稱為 GF(p)上的一個本原多項式(primitive polynomial forGF(q)over GF(p)、定義注1:對任意的 氐GF(q), a在GF(p)上的極小多項式存在并且唯一， 并且a在GF(p)上的極小多項式為 GF(p)上的一個不可約多項式、定義注2:設(shè)氏GF(q),則a與op在GF(p)上具有相同的極小多項式、 更進一步，集合B( 3= o,則 op2,卬3,，卬i,中的元素具有

7、相同的極小多項式、 設(shè)q=pn,則opn= 因此，集合B(熄中 互不相同的元素的個數(shù)(記為r)不超過n、可以證明，a為GF(q)的一個本 原元當(dāng)且僅當(dāng)r=n、定理：設(shè)GF(q)就是一個含有q個元素的有限域，GF(p)就是GF(q)的一 個含有p個元素的子域、設(shè) 長GF(q),r為滿足 妒=a的最小正整數(shù)、則 a在GF(p)上的極小多項式g(x)就是一個r次不可約多項式，并且B(熄= w即，型，印一中的元素為g(x)在GF(q)上的所有不同的根，即g(x) = (x- o)(x- Op)(x- Op2)? (x-沖-1)、注：r的計算方法如下：設(shè)a在F?q中的階為k、集合Z?k=m | 0mk-

8、 1,gcd(m,k)=1在模k乘法運算下就是一個含有&k)個元素的有限群(其中 小為歐拉(Euler)函數(shù))、則r等于pmodk在Z?k中的階、推論：設(shè)GF(q)就是一個含有q個元素的有限域，GF(p)就是GF(q)的一個含有p個元素的子域、設(shè)|GF(q)|=pn,即q=pn、設(shè)GF(q)為GF(q)的一個本原元，則a在GF(p)上的極小多項式g(x)的次數(shù)為n,并 且g(x)=(x- ®(x- op)(x-型)？ (x- apn-1)、更進一步，a op,陰2,，卬n-1均為 GF(q)的本原元、注：設(shè)GF(p)就是一個含有p個元素的有限域，n就是任意一個正整數(shù)，則GF(

9、p)上的n次本原多項式一定存在、 更進一步，GF(p)上的首項系數(shù)為1的n次本原多項式的個數(shù)為©pn-1)n,其中 小為歐拉函數(shù)、例3考慮二元域GF(2)上的不可約多項式p( 3=照+ 0+1,構(gòu)造有限域GF(23)=GF(2) o/?0( o)?=0,1, a, o+1, o2, o2+1, o2+ a, o2+ o+1、 容易驗證,5 m型,網(wǎng)，05, 06都就是 GF(23)的本原元、GF(2)上的首項系 數(shù)為1的3次本原多項式有兩個，分別為(i) a 理，04 在 GF(2) 上的極小多項式g(x)=(x+ ®(x+ 02)(x+ 曲=X3+X+1(ii) o3,

10、o5,06在GF (2)上的極小多項式g(x)=x3+x2 + 1有限域GF(p)上的本原多項式一定就是 GF(p)上的不可約多項式；但就是，GF(p)上的不可約多項式不一定就是 GF(p)上的本原多項式、定理：設(shè)GF(q)就是一個含有q個元素的有限域，GF(p)就是GF(q)的一 個含有p個元素的子域，g(x)就是GF(p)上的一個不可約多項式、則g(x) 為GF(p)上的本原多項式當(dāng)且僅當(dāng)g(x)在GF(q)上的根都就是GF(q) 的本原元、下面例子說明不可約多項式不一定就是本原多項式、例4考慮二元域 GF(2)上的不可約多項式 p(x)=x4+x3+x2+x+1，構(gòu)造有限 域GF(24)

11、=GF(2)x/?o(x)?=a+bx+cx2+dx3 | a,b,c,d G GF(2)、顯然，xG GF(24)、由于x5=1，即x的階為5,因此，x不就是GF(24)的本原元、于就是，p(x)不就是GF(2)上的本原多項式、另外，可以驗證x+1就是GF(24)的本原元、2 Matlab中的有限域計算函數(shù)Matlab中自帶的有限域的計算就是在 GF(2m)上進行的，即在二元域GF(2) 的擴域中進行計算，其中iwmwi6由“1、1有限域的構(gòu)造”的“例2”可知，我們只需先找到一個 GF(2)上 的m次不可約多項式g(x),得到集合GF(2)x/?g(x)?然后定義其上的加 法與乘法分別為模g

12、(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-1 Dm- 1+am-2Dm-2+? +a1D+a。，| aiG GF(2),0 i<m- 1因此，每個GF(2m)中的元素本質(zhì)上就是一個次數(shù)小于 m的多項式，

13、每個元 素與多項式之間有“1 -1”對應(yīng)關(guān)系、例如，取m=3與本原多項式p(D)=D3+D+1,則我們得到有限域 GF(23),其中的元素與多項式之間的對應(yīng) 關(guān)系如下：GF(23) GF(2)D/?p(D)?二進制0000011001GF(23)GF(2)D/?p(D)?二進制3D+10114D21005D2+11016D2+D1107D2+D+1111GF(2)上的多項式由系數(shù)組成的二進制所對應(yīng)的(十進制)數(shù)字來表示、 例如, 多項式p(D尸D3+D+1的系數(shù)組成的二進制為1011,因此，多項式p(D) 表示為數(shù)字11、2、1定義有限域數(shù)組在Matlab中，函數(shù)gf用來定義一個有限域數(shù)組，函

14、數(shù)中明如下：X_GF = GF(X,M,PRIM_POLY)函數(shù)創(chuàng)建有限域 GF(2m)上的一個數(shù)組，使用的GF(2)上的M次本原多項 式為PRIM_POLYM就是一個1至16之間的整數(shù)；數(shù)組X中的元素為0至 2m- 1之間的數(shù)、例如，生成有限域GF(23)中的所有元素，并令本原多項式為p(D尸D3+D2+1、>> GF8 = gf(0:7,3,13)GF8 = GF(2A3) array 、Primitive polynomial = DA3+DA2+1 (13 decimal)Array elements =0 1 2 3 4 5 6 7如果不指定本原多項式，則Matlab將使

15、用默認本原多項式、例如>> gf(0：7,3)ans = GF(2A3) array 、Primitive polynomial = DA3+D+1 (11 decimal) Array elements =0 1 2 3 4 5 6 7在這里例子中，Matlab使用了 3次本原多項式D3+D+1、如果不指定次數(shù) M與本原多項式PRIM_POLYU生成二元域 GF(2)中的元 素、> > gf(0：1)ans = GF(2) array 、Array elements = 0 1生成的有限域中的數(shù)組可以參與運算(+A、等)、注意：參與運算的操作數(shù)必須來自同一個有限域，用

16、于生成有限域的本原多項式也必須相同！一個典型的例子就是計算有限域的乘法表如下：> > GF8 = gf(0:7,3)GF8 = GF(2A3) array 、Primitive polynomial = DA3+D+1 (11 decimal)Array elements = 0 1 2 3 4 5 6 7> > GF8'*GF8ans = GF(2A3) array 、Primitive polynomial = DA3+D+1 (11 decimal)Array elements = 0000000001234567024631750365741204376

17、251051427360671532407521643> > GF8 = gf(0:7,3,13)GF8 = GF(2A3) array 、Primitive polynomial = DA3+DA2+1 (13 decimal)Array elements = 0 1 2 3 4 5 6 7> > GF8'*GF8Warning: Lookup tables not defined for this order 2A3 andprimitive polynomial 13、 Arithmetic still workscorrectly but multipl

18、ication, exponentiation, andinversion of elements is faster with lookup tables、Use gftable to create and save the lookup tables、> In gf 、gettables at 35In gf 、mtimes at 20ans = GF(2A3) array、Primitive polynomial = DA3+DA2+1 (13 decimal)Array elements =000000000123456702465713036512740451732605723

19、6410617243507346152在這里我們用兩個不同的本原多項式構(gòu)造有限域GF(23),得到兩張不同的乘法表、注1：當(dāng)我們計算GF(2)D/?D3+D2+1?的乘法表時,Matlab給產(chǎn)生一個警告 “Warning: Lookup tables not defined for this order 2A3 and primitive polynomial 13、”從警告中我們可以瞧出,Matlab中有限域的乘法就是通過查 表來完成的，這樣可以顯著地提高計算的速度、我們可以通過命令gftable 來創(chuàng)建并保存查找表格、注2:用本原多項式 D3+D+1與D3+D2+1生成兩個不同的元素個數(shù)為 8的有限域，然而這兩個有限域就是同構(gòu)的、一般地，我們有如下有限域同構(gòu)定理：定理：任意兩個元素個數(shù)相同的有限域一定同構(gòu)、與本原元多項式相關(guān)的函數(shù)primpoly函數(shù)primpoly用于計算GF(2)上的本原多項式，函數(shù)中明如