纠错码Lecture12-有限域(II)

Lecture12

有限域(II)2内容有限域的加法结构有限域的代数结构多项式的因式分解正规基和对偶基3有限域的加法结构域的特征满足ne=0的最小n值为域的特征，这里e为乘法单位元，0为域的零元，n取自正整数GF(p)的特征为p每一个域的特征或为素数，或为∞域的特征说明了域中加法运算的循环性，而域中元素的级则说明了乘法运算的循环性。元素的周期对域中元素a≠0，满足na=0的最小n值为a的周期。（注意对于域而言，在加法上用周期，在乘法上用级）域中非0元的周期都相同，且与域的特征相等在p特征域中，域整数全体（形如ne的全体域元素:n=…,-2,-1,0,1,2,…）构成p阶素子域，它与模p的整数域GF(p)同构4有限域加法性质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的倍数5有限域加法性质若w1,w2,…,wk是p特征域的元素，则对于一切自然数n，恒有若k是p特征域的域整数，则对于一切自然数n，必满足方程，即Fermat定理：对GF(pm)中的任何元素w，恒有任何小于素数p的整数b满足，如p特征域中，元素为域整数的充要条件是满足6最小多项式若为方程的根，则GF(pm)中互不相同的m个元素是f(x)的m个不同的根。这m个根称为方程f(x)的共轭根系能满足pm=1(modn)的最小整数m，称为p对模n的方次数系数取自GF(p)的，以w为根的所有首一多项式中，次数最低的称为w的最小多项式m(x)，w的最小多项式的次数m称为w的次数，称w为m次域元素7最小多项式性质m(x)在GF(p)上不可约若w也是f(x)的根，则m(x)可整除f(x)若w取自GF(pm)，则有m(x)可整除设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)的本原多项式的根级数均为pm-1，且本原多项式必为m次多项式w为最小多项式的根，若w是特征为p的有限域F上的m次域元素，则所有小于m次的多项式f(x)将w代入，得到的集合构成pm阶子域。（以最小多项式为模）如：GF(2)上f(x)=x3+x+1，以GF(23)上的元素w为根，则GF(2)上小于3次w多项式全体构成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线性无关，可作为域空间的基。可以由GF(p)上的一个m次本原或既约多项式，用它的根w构成的这组基底的线性组合，构造一个GF(pm)有限域9互反多项式定义设GF(p)上的m次多项式则称为互反多项式例：性质若α为f(x)的根，则α-1为f*(x)的根若f(x)既约，则f*(x)也为既约；反之亦然若f(x)为本原多项式，则f*(x)也为本原多项式；反之亦然

10多项式的周期定义设f(x)∈Fp[x],f(0)≠0（即x!|f(x)），则f(x)|(xl-1)的最小正整数l，称为f(x)的周期（或指数），记为p(f)性质f(x)的周期l是以f(x)为模所构成多项式剩余类环中乘法群内元素之级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多项式的周期性质(cont.)GF(p)上多项式f(x)的标准分解式若为则f(x)的周期式中是≥x的最小整数

12多项式的周期ExampleGF(2)上的多项式因为以5级元素为根以15级元素为根

13有限域的代数结构有限域的阶必为其特征（素数）之幂设f(x)为p阶有限域GF(p)上的一个d次既约多项式，则多项式剩余类集合Fp[x]/f(x)构成pd阶有限域GF(pd)。即GF(pd)是GF(p)的扩域，且f(x)在GF(pd)内有根GF(pr)含有子域GF(ps)的充要条件是s|r若β∈GF(pr)

，则β∈GF(ps)中的充要条件是。特别是在任何域中若，则β是0或1p阶有限域上的每一个d次首一既约多项式，皆能整除，只要d|m14最小扩域系数取自GF(p)上的多项式=所有次数除尽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既约多项式的数目GF(p)上m次既约多项式的数目是

式中为Mobius函数例：

GF(2)上3次既约多项式的数目分别为16同构m重、多项式剩余类以及α多项式之间均同构，都可用来表示pm阶有限域17因式分解分解注意到22=1(mod3)

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

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

Q(15)(x)非既约，进一步分解为（待定系数法）18待定系数法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级元素的最小多项式的次数为6，因此9级元素必在GF(26)上。设α为GF(26)上的本原域元素α63=1，则(α7)9=1，α7为9级元素。因此故21正规基和对偶基

定义为GF(pm)域的正规基，这里，α是GF(pm)中的本原域元素α∈GF(qm)，则它在GF(q)上的迹定义为其中，q为素数或素数幂对所有的α、β∈GF(qm)，有22正规基和对偶基Example:α是f(x)=x3+x2+1的根，则与GF(pm)的基底相对应，若满足，则称GF(pm)的基底是B的对偶基

23Example

若α是本原多项式f