糾錯碼Lecture12-有限域(II)

Lecture12

有限域(II)2內(nèi)容有限域的加法結(jié)構(gòu)有限域的代數(shù)結(jié)構(gòu)多項式的因式分解正規(guī)基和對偶基3有限域的加法結(jié)構(gòu)域的特征滿足ne=0的最小n值為域的特征，這里e為乘法單位元，0為域的零元，n取自正整數(shù)GF(p)的特征為p每一個域的特征或為素數(shù)，或為∞域的特征說明了域中加法運算的循環(huán)性，而域中元素的級則說明了乘法運算的循環(huán)性。元素的周期對域中元素a≠0，滿足na=0的最小n值為a的周期。（注意對于域而言，在加法上用周期，在乘法上用級）域中非0元的周期都相同，且與域的特征相等在p特征域中，域整數(shù)全體（形如ne的全體域元素:n=…,-2,-1,0,1,2,…）構(gòu)成p階素子域，它與模p的整數(shù)域GF(p)同構(gòu)4有限域加法性質(zhì)GF(p)為GF(pm)的基域，GF(pm)為GF(p)的擴域，GF(pm)的特征為p。如GF(22)的4個元素:00,01,10,11中的每一個特征均為2；故GF(22)是一個特征為2的域在特征為p的域中，恒有其中，a是域中的任一元素在p特征域中，對任何域元素a,b，恒有在p特征域中，任一元素的級均不是p的倍數(shù)5有限域加法性質(zhì)若w1,w2,…,wk是p特征域的元素，則對于一切自然數(shù)n，恒有若k是p特征域的域整數(shù)，則對于一切自然數(shù)n，必滿足方程，即Fermat定理：對GF(pm)中的任何元素w，恒有任何小于素數(shù)p的整數(shù)b滿足，如p特征域中，元素為域整數(shù)的充要條件是滿足6最小多項式若為方程的根，則GF(pm)中互不相同的m個元素是f(x)的m個不同的根。這m個根稱為方程f(x)的共軛根系能滿足pm=1(modn)的最小整數(shù)m，稱為p對模n的方次數(shù)系數(shù)取自GF(p)的，以w為根的所有首一多項式中，次數(shù)最低的稱為w的最小多項式m(x)，w的最小多項式的次數(shù)m稱為w的次數(shù)，稱w為m次域元素7最小多項式性質(zhì)m(x)在GF(p)上不可約若w也是f(x)的根，則m(x)可整除f(x)若w取自GF(pm)，則有m(x)可整除設(shè)w是p特征域GF(pm)中的n級元素，而pm=1(modn)，則w的最小多項式m(x)是m次多項式，且在GF(pm)域中完全分解m(x)為一次因式之積，所以稱GF(pm)為m(x)的分離域或分解域8本原多項式在GF(pm)中，以本原元為根的最小多項式稱為該域的本原多項式GF(pm)的本原多項式的根級數(shù)均為pm-1，且本原多項式必為m次多項式w為最小多項式的根，若w是特征為p的有限域F上的m次域元素，則所有小于m次的多項式f(x)將w代入，得到的集合構(gòu)成pm階子域。（以最小多項式為模）如：GF(2)上f(x)=x3+x+1，以GF(23)上的元素w為根，則GF(2)上小于3次w多項式全體構(gòu)成23階子域：0,1,w,w+1,w

2,w

2+1,w

2+w,w

2+w+1對于m次元素w，有1,w,w2,…,wm-1線性無關(guān)，可作為域空間的基?？梢杂蒅F(p)上的一個m次本原或既約多項式，用它的根w構(gòu)成的這組基底的線性組合，構(gòu)造一個GF(pm)有限域9互反多項式定義設(shè)GF(p)上的m次多項式則稱為互反多項式例：性質(zhì)若α為f(x)的根，則α-1為f*(x)的根若f(x)既約，則f*(x)也為既約；反之亦然若f(x)為本原多項式，則f*(x)也為本原多項式；反之亦然

10多項式的周期定義設(shè)f(x)∈Fp[x],f(0)≠0（即x!|f(x)），則f(x)|(xl-1)的最小正整數(shù)l，稱為f(x)的周期（或指數(shù)），記為p(f)性質(zhì)f(x)的周期l是以f(x)為模所構(gòu)成多項式剩余類環(huán)中乘法群內(nèi)元素之級f(x)∈Fp[x],f(0)≠0，則f(x)|(xl-1)的充要條件是p(f)|l多項式(xm-1)|(xn-1)的充要條件是m|n若f(x)是Fp[x]中m次既約多項式，則f(x)之周期p(f)等于f(x)在GF(pm)中的根的級

11多項式的周期性質(zhì)(cont.)GF(p)上多項式f(x)的標準分解式若為則f(x)的周期式中是≥x的最小整數(shù)

12多項式的周期ExampleGF(2)上的多項式因為以5級元素為根以15級元素為根

13有限域的代數(shù)結(jié)構(gòu)有限域的階必為其特征（素數(shù)）之冪設(shè)f(x)為p階有限域GF(p)上的一個d次既約多項式，則多項式剩余類集合Fp[x]/f(x)構(gòu)成pd階有限域GF(pd)。即GF(pd)是GF(p)的擴域，且f(x)在GF(pd)內(nèi)有根GF(pr)含有子域GF(ps)的充要條件是s|r若β∈GF(pr)

，則β∈GF(ps)中的充要條件是。特別是在任何域中若，則β是0或1p階有限域上的每一個d次首一既約多項式，皆能整除，只要d|m14最小擴域系數(shù)取自GF(p)上的多項式=所有次數(shù)除盡m的GF(p)上的首一既約多項式之積如：x4-x=x(x+1)(x2+x+1)若f(x)為GF(p)上的m次既約多項式，且m|d，則任何pd階有限域必含有f(x)的全部根若d=m，則m次首一既約多項式f(x)的全部根在GF(pm)中，稱GF(pm)為f(x)的包含所有根的最小擴域，稱為f(x)的分裂域或分解域例：GF(2)上的既約多項式必在GF(24)上完全分裂，但不能在任何中間域GF(22)完全分裂15既約多項式的數(shù)目GF(p)上m次既約多項式的數(shù)目是

式中為Mobius函數(shù)例：

GF(2)上3次既約多項式的數(shù)目分別為16同構(gòu)m重、多項式剩余類以及α多項式之間均同構(gòu)，都可用來表示pm階有限域17因式分解分解注意到22=1(mod3)

Q(3)(x)既約24=1(mod5)

Q(5)(x)既約24=1(mod15)

Q(15)(x)非既約，進一步分解為（待定系數(shù)法）18待定系數(shù)法Q(15)(x)的既約因式必為x4+Ax3+Bx2+Cx+11不是15級元素

A+B+C=11)A=B=C=1

x4+x3+x2+x+1=Q(5)(x);rejected2)A、B、C中只有1個為1B=1

x4+x2+1=(x2+x1+1)2;rejectedA=1

x4+x3+1;acceptedC=1

x4+x+1;acceptedRemark:x4+x3+1，x4+x+1為互反多項式因此19因式分解

均以15級元素為根。因此，若以此多項式作剩余類，就能得到24階有限域GF(24)。若以的根α表示，則上的15個非0元素如下所示20因式分解把x9-1分解為GF(2)上的既約因式乘積找9級元素的最小多項式，注意到26=1(mod9);故9級元素的最小多項式的次數(shù)為6，因此9級元素必在GF(26)上。設(shè)α為GF(26)上的本原域元素α63=1，則(α7)9=1，α7為9級元素。因此故21正規(guī)基和對偶基

定義為GF(pm)域的正規(guī)基，這里，α是GF(pm)中的本原域元素α∈GF(qm)，則它在GF(q)上的跡定義為其中，q為素數(shù)或素數(shù)冪對所有的α、β∈GF(qm)，有22正規(guī)基和對偶基Example:α是f(x)=x3+x2+1的根，則與GF(pm)的基底相對應(yīng)，若滿足，則稱GF(pm)的基底是B的對偶基

23Example

若α是本原多項式f