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

1、1有限域基礎(chǔ)知識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,p-,1、在GF(p)上定義加法 與乘法 O分別為模p加法與模p乘法，即任意 的 a,b GF(p),a b=(a+b)modp, aO b=(a%)modp則GF(p),O為一個(gè)有p個(gè)元素的有限域，其中零元素為0,單位元為1、令a為GF(p)中的一個(gè)非零元素、 由于gcd(a,p)

2、=1,因此，存在整數(shù)b,c, 使得 ab+pc=1、 由此得到 a的逆元為 a-1=bmodp、域GF(p)稱為一個(gè)素域(prime field)例注1：給定a與p,例1中的等式ab+pc=1可以通過擴(kuò)展的歐幾里得除法得到，從而求得GF(p)中任意非零元素的逆元、例2(有限域GF(pn)從GF(p)出發(fā)，對任意正整數(shù)n,n>2我們可以構(gòu)造元素元素個(gè)數(shù)為pn的有限域GF(pn)如下：令g(x)為一個(gè)GF(p)上次數(shù)為n的不可約多項(xiàng)式，集合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>為一個(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) 的逆元為 a-1(x)=b(x)modg(x)、域 GF(pn)稱為 GF(p

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

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

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

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

9、p)上的n次本原多項(xiàng)式一定存在、 更進(jìn)一步，GF(p)上的首項(xiàng)系數(shù)為1的n次本原多項(xiàng)式的個(gè)數(shù)為©pn-1)n,其中 小為歐拉函數(shù)、例3考慮二元域GF(2)上的不可約多項(xiàng)式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、 容易驗(yàn)證,5 m型,網(wǎng)，05, 06都就是 GF(23)的本原元、GF(2)上的首項(xiàng)系 數(shù)為1的3次本原多項(xiàng)式有兩個(gè)，分別為(i) a 理，04 在 GF(2) 上的極小多項(xiàng)式g(x)=(x+ ®(x+ 02)(x+ 曲=X3+X+1(ii) o3,

10、o5,06在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(q)上的根都就是GF(q) 的本原元、下面例子說明不可約多項(xiàng)式不一定就是本原多項(xiàng)式、例4考慮二元域 GF(2)上的不可約多項(xiàng)式 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)上的本原多項(xiàng)式、另外，可以驗(yàn)證x+1就是GF(24)的本原元、2 Matlab中的有限域計(jì)算函數(shù)Matlab中自帶的有限域的計(jì)算就是在 GF(2m)上進(jìn)行的，即在二元域GF(2) 的擴(kuò)域中進(jìn)行計(jì)算，其中iwmwi6由“1、1有限域的構(gòu)造”的“例2”可知，我們只需先找到一個(gè) GF(2)上 的m次不可約多項(xiàng)式g(x),得到集合GF(2)x/?g(x)?然后定義其上的加 法與乘法分別為模g

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

13、每個(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)制0000011001GF(23)GF(2)D/?p(D)?二進(jìn)制3D+10114D21005D2+11016D2+D1107D2+D+1111GF(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ù)組，函

14、數(shù)中明如下：X_GF = GF(X,M,PRIM_POLY)函數(shù)創(chuàng)建有限域 GF(2m)上的一個(gè)數(shù)組，使用的GF(2)上的M次本原多項(xiàng) 式為PRIM_POLYM就是一個(gè)1至16之間的整數(shù)；數(shù)組X中的元素為0至 2m- 1之間的數(shù)、例如，生成有限域GF(23)中的所有元素，并令本原多項(xiàng)式為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如果不指定本原多項(xiàng)式，則Matlab將使

15、用默認(rèn)本原多項(xiàng)式、例如>> 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次本原多項(xiàng)式D3+D+1、如果不指定次數(shù) M與本原多項(xiàng)式PRIM_POLYU生成二元域 GF(2)中的元 素、> > gf(0：1)ans = GF(2) array 、Array elements = 0 1生成的有限域中的數(shù)組可以參與運(yùn)算(+A、等)、注意：參與運(yùn)算的操作數(shù)必須來自同一個(gè)有限域，用

16、于生成有限域的本原多項(xiàng)式也必須相同！一個(gè)典型的例子就是計(jì)算有限域的乘法表如下：> > 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è)不同的本原多項(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 2A3 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)定理：定理：任意兩個(gè)元素個(gè)數(shù)相同的有限域一定同構(gòu)、與本原元多項(xiàng)式相關(guān)的函數(shù)primpoly函數(shù)primpoly用于計(jì)算GF(2)上的本原多項(xiàng)式，函數(shù)中明如