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,p,.在GF(p)上定義加法 和乘法 O分別為模p加法和模p乘法，即任意的 a,b GF(p),a b=(a+b)modp, aO b=(a?D)modp則GF(p),，O為一個(gè)有p個(gè)元素的有限域，其中零元素為 0,單位元為 1.令a為GF(p)中的一個(gè)非

2、零元素.由于gcd(a,p)=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, n2我們可以 構(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+a2X2+? +an-ixn-i |

3、 ai GF(p),0 簡-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)?)(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-

4、1(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ù)為Nq(n)=1nEd|n &qu

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

6、限域， GF(p) 是 GF(q) 的一個(gè)含有p個(gè)元素的子域(P不一定為素?cái)?shù))，a GF(q).則GF(p)上以a為 根，首項(xiàng)系數(shù)為 1并且次數(shù)最低的多項(xiàng)式稱為a在GF(p)上的極小多項(xiàng) 式(mi ni mal polyno mial of a over GF(p).特別地，若a GF(q)為GF(q)的一個(gè)本原元，則a在GF(p)上的極小 多項(xiàng)式稱為 GF(p) 上的一個(gè) 本原多項(xiàng)式 (primitive polynomial for GF(q) over GF(p).定義注1對任意的a GF(q)， a在GF(p)上的極小多項(xiàng)式存在并且唯一， 并且a在GF(p)上的極小多項(xiàng)式為 GF(p)

7、上的一個(gè)不可約多項(xiàng)式.定義注2：設(shè)a GF(q)，則a和a在GF(p)上具有相同的極小多項(xiàng)式.更進(jìn)一步，集合B(a)= a, a, a2, a3,a,中的元素具有相同的極小多項(xiàng)式.設(shè)q=pn，貝u an= a因此，集合B( a中 互不相同的元素的個(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è)a GF(q) ,r為滿足 ar= a的最小正整數(shù).則a 在 GF(p) 上的極小多項(xiàng)式 g(x) 是一個(gè) r 次不可約多項(xiàng)式，并且B(a)= a, a,

8、0p2, ，0pr- 1中的元素為 g(x) 在 GF(q) 上的所有不同的根，即g(x)=(x- 0(x- a)(x- a2)? (x- opr-1).注：r的計(jì)算方法如下：設(shè) a在F?q中的階為k.集合Z?k=m | 0 奇之-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è)a GF(q)為GF(q)的一個(gè)本原元，則 a在GF

9、(p)上的極小多項(xiàng)式g(x)的次數(shù)為n,并且g(x)=(x- a(x- a)(x- a2)? (x- O(pn- 1).更進(jìn)一步，a a, a?,an-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ù)為Kpn-1)n,其中©為歐拉函數(shù).例3考慮二元域GF(2)上的不可約多項(xiàng)式p( 0= a+ a+1，構(gòu)造有限域GF(23)=GF(2) q/?p( a?=0,1, a a+1, a, a+1, a+ a, a

10、+ a+1.容易驗(yàn)證， a a, a, a, a, 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)式不一定是 GF(p) 上的本原多項(xiàng)式 .定理：設(shè) GF(q) 是一個(gè)含有 q 個(gè)元素的有限域， GF(p) 是 GF(q) 的一個(gè) 含有 p

11、個(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)=GF(2)x/?o(x)?=a+bx+cx2+dx3 | a,b,c,d GF(2).顯然，x GF(24).由于X5=1，即x的階為5,因此，x不是GF(24)的 本原元 . 于是， p(x) 不是 GF(2) 上的本原多項(xiàng)式 . 另外，可以驗(yàn)證 x+1 是

12、GF(24) 的本原元 .2 Matlab 中的有限域計(jì)算函數(shù)Matlab 中自帶的有限域的計(jì)算是在 GF(2m) 上進(jìn)行的，即在二元域 GF(2)的擴(kuò)域中進(jìn)行計(jì)算，其中iwmw 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).然而，這樣得到的有限域 GF(2m) 中，元素 x 未必是本原元，這將給后面的 (乘法)運(yùn)算帶來很多麻煩 . 因此， 在不可約多項(xiàng)式 g(x) 的挑選上， 我們最好

13、 選擇一個(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- i+am- 2Dm-2+? +ai D+ao, | ai GF,0 im- 1因此，每個(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(2

14、3)GF(2)D/?p(D)?二進(jìn)制00000110012 D0103 D+10114 D21005 D2+11016 D2+D1107 D2+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ù)組，函數(shù)申明如下：X_GF = GF(X,M,PRIM_POLY) 函數(shù)創(chuàng)建有限域 GF(2M) 上的一個(gè)數(shù)組，使用的 GF(2) 上的 M 次本原多項(xiàng) 式為 PRIM_POL；

15、Y M 是一個(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 pol yn omial = DA3+DA2+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(2A3) array. Primiti

16、ve 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_POL，則生成二元域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(

17、0:7,3)GF8 = GF(2A3) array. Primitive pol yn omial = DA3+D+1 (11 decimal)Array elements =>> GF8'*GF8 ans = GF(2A3) array. Primitive polynomial = DA3+D+1 (11 decimal)Array elements =0 1 2 3 4 5 6 70 2 4 6 3 1 7 50 3 6 5 7 4 1 20 4 3 70 5 1 40 6 7 10 7 5 26 2 5 12 7 3 65 3 2 41 6 4 3>>

18、GF8 = gf(0:7,3,13)GF8 = GF(2A3) array. Primitive pol yn omial = DA3+DA2+1 (13 decimal)Array elements =>> GF8'*GF8Warning: Lookup tables not defined for this order 2A3 and primitive polynomial 13. Arithmetic still works correctly but multiplication, exponentiation, and inversion of elements

19、 is faster with lookup tables. Use gftable to create and save the lookup tables.> In gf.gettables at 35In gf.mtimes at 20 ans = GF(2A3) array. Primitive pol yn omial = DA3+DA2+1 (13 decimal)Array elements =0 00000000 12345670 2465713在這里我們用兩個(gè)不同的本原多項(xiàng)式構(gòu)造有限域GF(23)，得到兩不同的乘法表.注 1：當(dāng)我們計(jì)算 GF(2)D/?D3+D2+1?

20、 的乘法表時(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ì)算