信道编码有限域和多项式.ppt

第四章 多项式与有限域1学习本章目的：对Xn-1进行因式分解(n=qm-1,q为素数)X15-1=(x+1)(x4+x3+1)(x4+x3+x2+x+1)(x2+x+1)(x4+x+1)Xn-1?循环：只有最高位和最低位一、剩余类环1.环，子环、扩环回顾环（R，+，*）的定义定义了两种运算+和*R对+构成阿贝尔群*满足封闭性、结合律*对+满足分配律*不一定有恒等元1，R的元素不一定有逆元2.非空子集S是环（R，+，*）的子环的充要条件:1)a,b S:a-b S;S是群（R，+)的子群2)a,b S:ab S S对*满足封闭性一、剩余类环3.理想理想定义定义:交换环R中的非空子集I称为R中的理想，若：1)a,b I:a-b I;2)a I,r R:ar=ra I;1)+2)理想是个子环，2)I 中任一元素a的倍数在I中，即I由R的一些元素（可以是多个）的倍数组成。主理想主理想：由一个元素的的所有倍数组成的理想.这个元素叫生成元.主理想环主理想环:每一个理想都是主理想每一个理想都是主理想一、剩余类环4.剩余类环定理定理1 1(定理4.1.2)：设I 为可换环R的一个理想，则R/I构成一个可换环，称为模模I I的剩余类的剩余类环环。例:Mod5的剩余类环I0:05-510-10.1+I 1:16-411-9.2+I 2:27-312-8.3+I 3:38-213-7.4+I 4:49-114-6.0,1,2,3,4对模5+和模5*构成可换环二、多项式剩余类环1.多项式Fq上的多项式：f(x)=fnxn+fn-1xn-1+f2x2+f1x+f0fi Fq i=0,1,2,n次数n记为：f(x),f,degf(x),degfWhy多项式？矢量 a a=(1,0,1,1,0,1)（位置）多项式f(x)=x5+x3+x2 +1 （次数）为了借用多项式的运算来定义矢量的运算多项式的除法 例：(x9+x8+x7+x2+x+1）/（x4+x3+x+1）n次多项式域（群、环）与n维矢量域（群、环）在下列映射下同构：f(x)=fnxn+fn-1xn-1+f2x2+f1x+f0 （fnfn-1f2f1f0）二、多项式剩余类环定理定理2 2：集合G与G 同构（G为群(环、域)G为群(环、域)）首一多项式：fn=1，最高次数为1，f(x)1。Fqx:表示系数属于Fq的所有多项式的集合2.多项式环整数是一个环，多项式与整数类似。定理定理3 3：Fqx构成一个环零元：f(x)=0二、多项式剩余类环性质整数环多项式环零元素0f(x)=0恒等元1f(x)=1不可分解的元素数既约多项式（除提取常数，不能进行因式分解，定义4.4.2）素多项式=首一+既约多项式分解的唯一性a=p1r1p2r2(素数幂的积）f(x)=p1(x)r1p2(x)r2每一个首一多项式可唯一分解为素多项式的幂的积(定理4.23)欧几里德除法若ab,则a可唯一表示为:a=qb+r,0 r b若f(x)g(x),则:f(x)=q(x)g(x)+r(x)0 r(x)g(x)(定理4.2.2)二、多项式剩余类环性质整数环多项式环约数 最大公约数(a,b),GCD(a,b)最高公因式(定义4.2.3)(是首一多项式）（f(x),g(x),GCD(f(x),g(x)倍数 最小公倍数a,b,LCM(a,b)最低公倍式(定义4.2.4)(是首一多项式）f(x),g(x),LCM(f(x),g(x)欧几里德算法a=qb+r(a,b)=(b,r)(a,b)=Aa+BbA,B为正整数f(x)=q(x)g(x)+r(x)(f(x),gx)=(g(x),r(x)(例f(x)=x9+x8+x7+x2+x+1,g(x)=x4+x3+x+1)(f(x),g(x)=A(x)f(x)+B(x)g(x)0 A(x)g(x)-(f(x),g(x)0 B(x)k,n=h-k,n=h-k=h-k=k-k=e一定是 0=e,2,n-1例:Z/(8)2.定理定理4 4(定理4.3.1)：可换群G的任一n 级元素a 皆可生成一个n 阶循环子群。循环群是可换群，所以由其中元素i皆能生成一个循环群，其阶数为i的级数。这个循环群可以是它本身，或是它的子群。四、循环群3.循环群G 的性质：1)G 必为阿贝尔群；2)a为n 级元素，则 ak 的级为n/(kn);3)a为n 级元素，则am=e n|m;4)n 阶循环群中每个元素的级数m满足m|n.5)n 级元素a与m 级元素 b 满足(n,m)=1,则 ab为nm 级元素;4.定理 5(推论 4.3.3)：n 阶循环群中必有(n)个单位原根。(n)=|a|0 a n-1且（a,n）=1|(欧拉函数，小于n且与n互素的自然数的个数)四、循环群5.由已知循环群寻找其全部子群（定理4.3.2)G(a)为由a生成的n阶有限循环群，H为G(a)的子群1)H为有限阶循环群，或者是e,或者是由am 生成的q阶循环群：e，am，a2m，an-m（其中q|n,m=n/q）2)若m|n,则G中必有唯一的n/m阶循环子群，生成元是am五、有限域GF(q)的乘法结构有限域GF(q)非零元素全体对乘法构成阿贝尔群，由定理4，任一非零元素可生成一个有限循环子群，其阶称为的级，即使n=1的最小正整数n,称为GF(q)的n次单位原根，若n=q-1,则称为GF(q)-0的生成元，称为本原域元素。循环群的单位原根：循环群的单位原根：n级元素称为n次单位原根。本原域元素本原域元素(本原元本原元):):q-1级元素五、有限域GF(q)的乘法结构1.定理定理 6 6：Fq上的n级元素 生成的n阶循环群G()是方程 xn-1=0的全部根。证明：1)设 G()的级为h h,由定理4，可生成一个阶为h的循环子群，而子群的阶必为G)的阶n的因子，所以h|n,n=(h)n/h=12)方程xn-1=0的根不多于n个，而G()中，n个元素都是它的根，所以全部根落在G()中。推论推论1 1：若Fq含有n次单位原根，则xn 1可分解为 。五、有限域GF(q)的乘法结构2.定理定理 7 7：Fq 必有本原域元素存在，所以Fq 0是一个 q-1阶乘法循环群。所以 Fq 0=,2,q-2,q-1=e这称为有限域的幂表示法。2.推论推论2 2(定理4.4.1)：方程xq-1 1=0的全部根构成Fq 0.Fq为xq x=0的全部根，即xq x=x Fq称为xq x的最小分裂域3.推论推论3 3(费马费马FermaFerma定理定理,定理4.5.5)：Fq:q=.五、有限域GF(q)的乘法结构例 GF(2)上的多项式x15 1=GF(16)-0=1,2,3,14每个元素的级是15的因子，15的因子有1、3、5、15，所以GF(16)非0元素的级为1、3、5、15，其中i的级为15/（15,i)，所以1,2,3,4,5,6,7,8,9,10,11,12,13,14级:1,15,15,5,15,3,5,15,15,5,3,15,5,15,15级数为 1:1,3:5,105:3,6,9,12,15:,2,4,7,8,11,13,14把同级的一次因式相乘得 =(x-1)(x-5)(x-10)(x-3)(x-6)(x-9)(x-12)(x-)(x-2)(x-4)(x-7)(x-8)(x-11)(x-13)(x-14)=Q(1)(x)Q(3)(x)Q(5)(x)Q(15)(x)五、有限域GF(q)的乘法结构分园多项式 xn-1=为n级元素,则i为n/(n,i)级元素,把同级的分为一类,得k类,即n1=n/(n,i1),nd=n/(n,id),nk=n/(n,ik)以d级元素为根的所有一次因式的积叫分园多项式(定义4.4.3)分园多项式是GF(2)上的多项式,并且可以通过后面介绍的方法求得,亦即xn-1至少可分解为分园多项式的积2024/5/7周二21五、有限域GF(q)的乘法结构定理定理7*7*(定理4.4.5,p120):(求分园多项式)xn 1=Q(d)(x)为分圆多项式，Q(d)(x)=为MobiusMobius函数函数，(m)=0,m有平方因子 =(-1)k,m 不含平方因子,且可分解为k个因子的积 =1,m=1六、有限域GF(q)的加法结构1.基本概念1)周期:模拟乘法的级 a+a+a+a+a=na=0 n个a 相加，即加法幂，记为na (课本的na不是n乘a）任意aGF(q)(a0),满足na=0的最小正整数或。2）特征：乘法单位元e的周期，即满足ne=0的最小正整数n,如果nN:ne 0,则称域的特征为 a=a*e na=a+a+a=a*e+a*e+a*e =a*(e+e+e)=a*(ne)=0（根据分配律）n个六、有限域GF(q)的加法结构定理8：域中任一非零元素的周期都等于域的特征（定理4.5.1)域整数：a=ze(z Z Z)(e的倍数)例如GF(4)=0，1，2，3中，1+1=0，周期为2 0、1为域整数定理9：域的特征或为素数，或为。（定理4.5.2)假设特征h不为素数，h=m*n,则 he=(m*n)e=m(ne)=0 ne的周期 m h,这与定理8矛盾。（根据结合律）m*n个e相加 m个(ne)相加六、有限域GF(q)的加法结构定理10：在p特征域GF(q)中，全体域整数构成p阶素子域GF(p),且同构于Z/(p)(定理4.5.3)GF(p)称为GF(q)的基域，GF(q)称为GF(p)的扩域。定理11：p特征域GF(q)中，(定理4.5.4)aGF(q):(x-a)p=xp ap推论推论4:若k是p特征域的域整数，则 =k(nN N)(推论4.5.4)没有真子域P为素数X可以取扩域GF(q)中的元素六、有限域GF(q)的加法结构定理定理1212:在p特征域Fq中：元素a为域整数 ap-a=0 (定理4.5.5)2.最小多项式与本原多项式最小多项式、元素的次数、本原多项式最小多项式、元素的次数、本原多项式：设Fq为FQ 的子域，w FQ,m(x)是Fq上满足 m(w)=0的次数最低的首一多项式，称 m(x)为w在Fq上的最小多项式，m(x)称为w的次数。若w为FQ的本原元，则称m(x)为本原多项式。问题：f（x)=x-w 是不是w的最小多项式？六、有限域GF(q)的加法结构定理定理 13 13 (定理4.5.8)：w 在Fq上最小多项式m(x)的性质：1)m(x)在GF(p)上既约；2)存在且唯一；3)若Fq上多项式f(x)满足 f(w)=0,则 m(x)|f(x);（以w为根的多项式是m(x)的倍式）；4)m(x)|xq-x.w定理定理 14 14 (相当于定理4.6.2)：令f(x)为Fq上任意多项式，则存在扩展域FQ,在FQ中f(x)可分解为一次因子的积，称FQ为f(x)的分裂域分裂域。以素多项式f(x)生成一个有限域Fqx/f(x),在这个域中可见，如果f(x)是GF(p)上的素多项式，而且f(w)=0,则f(x)为w的最小多项式。六、有限域GF(q)的加法结构定理定理 15 15(课本没有)：设Fq为FQ的真子域，是FQ的本原元，的次数为m,则 Q=qm，且 FQ:=,ai Fq 证：第一步：证Q qm a.形式为 的元素在FQ中设=,ai Fq，则 FQ b.不同形式对应不同的元素 设1=,ai Fq 2=,bi Fq 且i:aibi 则1 2反证法，如1=2，则在Fq中有次数比m更小并以为根的素多项式。这与的次数为m矛盾形式为的元素有qm个，全部落在FQ中，所以Q qm六、有限域GF(q)的加法结构第二步：证Q qm 为FQ的本原域元素，则 FQ:=k 又设在Fq的最小多项式为f(x)=xm+fm-1xm-1+fm-2xm-2+f1x+f0则f()=m+fm-1 m-1+fm-2 m-2+f1 +f0=0，.k可表示为（m-1，m-2，,1)的线性组合，而（m-1，m-2，,1)的线性组合共qm个，所以Q qm 综上述，Q=qm推论推论5(定理4.6.1)：有限域的阶必为其特征的幂，因此它是素数的幂。六、有限域GF(q)的加法结构3共轭根:定理定理1616（定理4.5.6）:f(x)为Fp上的多项式，w为Fp的扩展域上的元素且f(w)=0,则对于n N N,有 ,叫w的共轭根共轭根，共轭根的集合组成共轭根系共轭根系 设w为f(x)的根（Fpm 的元素）,观察共轭根:n=0,1,2,m-1,m,m+1,w,wp,所以，方程f(x)=0的共轭根,最多m个。设m为满足wpk=w的最小正整数k,则w的共轭根有m个，这m个根实际上是由m个共轭根组成的m/m个循环。所以m|m设w的级数为n,则n|pm-1,所以pm1（modn)P P对模对模n n的方次数的方次数:满足pm 1(mod n)的最小整数m称为p对模n的方次数六、有限域GF(q)的加法结构定理定理16*16*（推论4.5.7）：各个共轭根的级数相同，最小多项式相同。w的级为n,则wp的级为n/(n,p)=n定理定理17 17（定理4.5.9）：设w是Fq的扩展域FQ的n级元素，而m是q对模n的方次数，则w的次数为m,且其在Fq上的最小多项式m(x)=3.多项式的周期多项式多项式 f(x)f(x)的周期的周期p(f):p(f):设f(x)Fqx,f(0)0,满足 f(x)|(xl-1)的最小正整数l.定理定理17*17*p(f)p(f)的性质的性质:p(f)等于Fqx/f(x)中的级数。七、有限域GF(q)的代数结构定理定理18 18（定理4.6.3）(1)s|r;（正向可直接从定理15推出）(2)定理定理19 19（定理4.6.4）Fq,nN N:定理定理20 20 (定理4.6.6）-x=(-x可分解为次数为m的因子的素多项式的积)定理定理21 21 (定理4.6.7）f(x)为Fq上的d次既约多项式，且d|m,则任一含有f(x)的全部根。七、有限域GF(q)的代数结构定理定理22 22 (定理4.6.8）Fq上的m次既约多项式的数目是 .(d)为Mobius函数。八、小结1.乘法结构1)Fq-0一定是q-1阶乘法循环群，Fq=0，2，,q-2，q-1=e,叫 有限域的幂表示法2)Fq 一定是方程xq-x=0的全部根，所以xq-x可分解为1次因式的积2.加法结构1)Fq的特征p一定是素数,而且满足q=pm.2)给出任一素数p和正整数m,一定存在GF(pm).3)任意两个同阶的域同构.所有方法生成的有限域本质上是一样的，只是表示方法（即加法表与乘法表不一样）不一样，只要找到一种方法生成即可。八、小结如何求GF(pm)?a)求以P为特征的域Fp=e,2e,pe=0b)求Fp上的m次素多项式f(x).（可查表,共有 个,见定理22)c)求有限域的剩余类表示法，去掉帽子得多项式表示法，可映射为矢量表示法(f(x)=fmxm+fm-1xm-1+,+f1x+f0映射为(fm,fm-1,.,f1,f0)f(x)=0（定理14）,f(x)为x的最小多项式，设f(x)的周期为n,则x为n级元素（定理17*），m为p关于模n的方次数（定理17），如n=pm-1,则f(x)为本原多项式，x为本原元,这时多项式表示法与幂表示法结合起来例，构造GF(4)考察元素x八、小结3.因式分解定理定理 14 14 (相当于定理4.6.2)：令f(x)为Fq上任意多项式，则存在扩展域FQ,在FQ中f(x)可分解为一次因子的积，称FQ为f(x)的分裂域分裂域。GF(pm)是方程xpm-x=0的全部根，所以在GF(pm)中，xpm-1-1可分解为一次因式的积，即 （1）把（1）式同级元素相乘，得分园多项式（Fp上，但不一定是素多项式），所以根据定理7*，Q(d)(x)=根据定理17，把（1）式共轭根的一次因式相乘，得最小多项式(Fp上，是素多项式),所以 其中，r为ws对模n的方次数，n为ws的级数，ms(x)为第s个共扼根系共扼根对应的最小多项式八、小结根据定理20,-x =(素多项式f(x)可查表)八、小结例：对x7-1进行因式分解 构造GF(8),查表得GF(2)上的素多项式f(x)=x3+x+1,求F2x/f(x),得GF(8),p134,表4-1 GF(8)=(0，1,，2，3，4，5，6)元素级方次数共轭根最小多项式101x+173（231mod 7)，2，4(x-)(x-2)(x-4)=x3+x+1373(231mod 7)3，5，6(x-3)(x-5)(x-6)=x3+x2+1(x-)(x-2)(x-4)=(x2+(+2)x+3)(x-4)=(x2+4x+3)(x-4)=x3+4x2+4x2+8 x+3 x+7=x3+x+1(x-3)(x-5)(x-6)=(x2+(3+5)x+8)(x-6)=(x2+2x+)(x-6)=x3+6x2+2x2+8 x+x+1=x3+x2+1x7-1=(x+1)(x3+x+1)(x3+x2+1)（1）事实上，根据定理20，(x3+x+1)|(x7-1),（x7-1）/(x3+x+1)=(x4+x2+x+1)又x=1必为x7-1的根，所以（x+1)|(x4+x2+x+1),求(x4+x2+x+1)/（x+1)=x3+x2+1，为素多项式，所以得（1）式谢谢！2024/5/7周二40