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

1、1 有限域基礎(chǔ)知識(shí)1.1 有限域( Galois 域)的構(gòu)造令p為一個(gè)素?cái)?shù).則對(duì)任意的一個(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)mod p, aO b=(a?b)mod p則GF(p),O為一個(gè)有p個(gè)元素的有限域，其中零元素為0，單位元 為 1.令 a 為 G

2、F(p) 中的一個(gè)非零元素 . 由于 gcd(a,p)=1 ，因此，存在整數(shù)b,c，使得 ab+ pc=1 .由此得到 a的逆元為 a-1= bmod p.域 GF(p)稱(chēng)為一個(gè)素域(prime field).例注1:給定a和p，例1中的等式ab+ pc=1可以通過(guò)擴(kuò)展的歐幾里得除法得到，從而求得 GF(p) 中任意非零元素的逆元 .例2 (有限域GF(pn)從GF(p)出發(fā)，對(duì)任意正整數(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)?=ao + aix

3、+a2x2+? +an- ixn-1 | aiGF(p),0 i n- 1在GF(pn)上定義加法 和乘法 O分別為模g(x)加法和模g(x)乘法, 即任意的 a(x),b(x) GF(pn)，a(x)b(x)= a(x)+b(x), a(x)O b(x)=( a(x)?b(x)mod g(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 .

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

5、次不可約多項(xiàng)式的個(gè)數(shù)為Nq(n)=1 nEd|n p(nd)qd=1 nEdm p(d)qn/d其中 為Moebius函數(shù)，定義為u(m)= ? ? ? 1(- 1)k0 如果 m=1 如果 m= pp2? pk,其中p 1,p2,pk為互不相同的素?cái)?shù)其它1.2 有限域的性質(zhì)令 GF(q) 是一個(gè)含有 q 個(gè)元素的有限域， F?q=GF(q)?0 為有限域 GF(q) 中所有非零元素構(gòu)成的集合 . 則在乘法之下 F?q 是一個(gè)有限 循環(huán)群. 循環(huán)群 F?q 的一個(gè)生成元稱(chēng)為有限域 GF(q) 的一個(gè)本原元.若a GF(q)為一個(gè)本原元，則GF(q)=0,1, a, a2,，aq-2并且 aq-

6、 1=1，即 aq = a.定義：設(shè) GF(q) 是一個(gè)含有 q 個(gè)元素的有限域， GF(p ) 是 GF(q) 的一個(gè)含有p個(gè)元素的子域(p不一定為素?cái)?shù))，a GF(q).則GF(p)上以a 為根，首項(xiàng)系數(shù)為1，并且次數(shù)最低的多項(xiàng)式稱(chēng)為 a在GF(p)上的極小多 項(xiàng)式(minimal polynomial ofa over GF(p).特別地，若a GF(q)為GF(q)的一個(gè)本原元，則a在GF(p)上的極小多項(xiàng)式稱(chēng)為 GF(p) 上的一個(gè)本原多項(xiàng)式 (primitive polynomial forGF(q) over GF(p).定義注1:對(duì)任意的a GF(q)， a在GF(p)上的極小

7、多項(xiàng)式存在并且唯 一，并且 a 在 GF(p) 上的極小多項(xiàng)式為 GF(p) 上的一個(gè)不可約多項(xiàng)式 .定義注2:設(shè)a GF(q)，貝U a和aP在GF(p)上具有相同的極小多項(xiàng) 式. 更進(jìn)一步，集合B(a)= a, aP,仇P2, aP3,apj,-.中的元素具有相同的極小多項(xiàng)式.設(shè)q=pn，則apn= a.因此，集合B( a)中 互不相同的元素的個(gè)數(shù)(記為 r)不超過(guò)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è)a GF(q)， r為滿(mǎn)足 ar= a的最小正整數(shù).則

8、 a 在 GF(p) 上的極小多項(xiàng)式 g(x) 是一個(gè) r 次不可約多項(xiàng)式，并且b( a= a, a, aP2,，apr-中的元素為 g(x) 在 GF(q) 上的所有不同的根，即g(x)=(x- a)(x- ap)(x- ap2)? (x- apr-1).注：r的計(jì)算方法如下：設(shè) a在F?q中的階為k.集合Z?k=m | 0 m wk- 1,gcd (m ,k)=1在模k乘法運(yùn)算下是一個(gè)含有 機(jī)k)個(gè)元素的有限群(其中$為歐拉(Euler) 函數(shù)). 則 r 等于 pmod k 在 Z?k 中的階.推論：設(shè) GF(q) 是一個(gè)含有 q 個(gè)元素的有限域， GF(p) 是 GF(q) 的一個(gè)含有

9、p個(gè)元素的子域設(shè)|GF(q)|= pn，即q = pn設(shè) a GF(q)為GF(q)的一個(gè)本原元，貝U a在GF(p)上的極小多項(xiàng)式g(x)的次數(shù)為n , 并且g(x)=( x- a(X- ap)(x- a2)? (x- apn-1).更進(jìn)一步，a aP, aP2,，apn-1均為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ù)為 $(pn- 1)n，其中$為歐拉函數(shù)例3考慮二兀域 GF(2)上的不可約多項(xiàng)式 p ( a)= a3 +

10、a+1 ,構(gòu)造有限域GF(23)= GF(2) a/?P( a)?=,1, a, a+1, a2, a2+1, a2 + a, a2 + a+1.容易驗(yàn)證，a, a, a3, a4, a5, a都是GF(23)的本原兀.GF(2)上的首項(xiàng)系數(shù)為 1 的 3 次本原多項(xiàng)式有兩個(gè)，分別為(i) a, a2, a4 在 GF(2) 上的極小多項(xiàng)式g(x)=( x+ a)(x+ a2)(x+ a4)= x3+x+1(ii) a3,a5,a6 在 GF(2) 上的極小多項(xiàng)式g(x)=x3+x2+1有限域 GF(p) 上的本原多項(xiàng)式一定是 GF(p) 上的不可約多項(xiàng)式；但是，GF(p) 上的不可約多項(xiàng)式不

11、一定是 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) 的本原兀 .下面例子說(shuō)明不可約多項(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,d GF(2).顯然，x GF(24).由于

12、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ì)算，其中1 m 16.由 “1.1 有限域的構(gòu)造” 的 “例2” 可知，我們只需先找到一個(gè) GF(2) 上 的m次不可約多項(xiàng)式g(x),得到集合 GF(2)x/?g(x)?，然后定義其上 的加法和乘法分別為模 g(x) 加法和模 g(x) 乘法，即得到有限域 GF(2m).然而，這樣得到的

13、有限域 GF(2m) 中，元素 x 未必是本原元，這將給后面的 (乘法)運(yùn)算帶來(lái)很多麻煩 . 因此，在不可約多項(xiàng)式 g(x) 的挑選上， 我們最好 選擇一個(gè) 本原多項(xiàng)式 . 這其實(shí)就是 Matlab 中的做法 .Matlab 中 GF(2 m ) 的元素： 在 Matlab 中GF(2m):=GF(2)D/?p(D)?，其中 p(D)為一個(gè) GF(2)上的 m 次本 原多項(xiàng)式 .GF(2m)=am-1Dm-1+am-2Dm- 2+? +a1D+a0, | ai GF(2),0i GF8 = gf(0:7,3,13)GF8 = GF(2A3) array. Primitive pol yn om

14、ial = DA3+DA2+1 (13 decimal)Array elements =01234567如果不指定本原多項(xiàng)式，則 Matlab 將使用默認(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_POLY ，則生成二元域 GF(2) 中的元素. gf(0:1)ans = GF(2) array.

15、Array elements =0 1生成的有限域中的數(shù)組可以參與運(yùn)算(+、.、A、等).注意：參與運(yùn)算的操作數(shù)必須來(lái)自同一個(gè)有限域，用于生成有限域的本原多項(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*GF8 ans = GF(2A3) array. Primitive pol yn omial = DA3+D+1 (11 decimal)Array el

16、ements = 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 defi ned for this order 2A3 and primitive polynomial 13. Arithmetic still works correctly but multiplication, exponentiation, and inversion o

17、f 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 =00000123024603650451000045675713127473260 5 7 2 3 6 4 10617243507346152在這里我們用兩個(gè)不同的本原多項(xiàng)式構(gòu)

18、造有限域GF(2 3 )，得到兩張不同的乘法表.注1：當(dāng)我們計(jì)算 GF(2) D/ ? D3+ D2+1 ? 的乘法表時(shí)， Matlab 給產(chǎn)生一個(gè)警告 “ Warning: Lookup tables not defi ned for this order 2A3 andprimitive polynomial 13.” 從警告中我們可以看出， Matlab 中有限域的乘法是通過(guò)查表來(lái)完成的，這樣可以顯著地提高計(jì)算的速度 . 我們可以通過(guò)命令 gftable 來(lái)創(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)