信道编码-有限域和多项式

1、第四章 多项式与有限域学习本章目的：对Xn-1进行因式分解(n=qm-1,q为素数)X15-1=(x+1)(x 4 + x 3+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.理想理想定义定义: 交换

2、环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的剩余类环I 0: 05-510-10 .1+I 1:16-411-9.2+I 2:

3、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次多项式域（

4、群、环）与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）素多项式=首一 +

5、 既约多项式分解的唯一性a=p1r1p2r2(素数幂的积）f(x)=p1(x)r1p2 (x) r2每一个首一多项式可唯一分解为素多项式的幂的积(定理4.2.3)欧几里德除法若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

6、(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),g(x)=(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 阶循环子

7、群 。 循环群是可换群，所以由其中元素i皆能生成一个循环群，其阶数为i的级数。这个循环群可以是它本身，或是它的子群。四、循环群3.循环群G 的性质：1) G 必为阿贝尔群；2) a为n 级元素，则 ak 的级为n /(k,n);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互素的自然数的个数)四、

8、循环群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

9、级元素称为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可分解为 。10)(niix五、有限域GF(q)的乘法结构2.定理定理 7 7：Fq

10、必有本原域元素存在，所以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 = . 20)(qiix五、有限域GF(q)的乘法结构例 GF(2)上的多项式x15 1=GF(16)-0=1 , , 2, 3 , , 14每个元素的级是15的因子，15的因子有1、3、5、15，所以

11、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

12、)(x) Q(5)(x) Q(15)(x)140)(iix140)(iix140)(iix五、有限域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至少可分解为分园多项式的积10)(niix ksnqGFndddnsxQxx1)(|)()()1级元素的中为（五、有限域GF(q)的乘法结构定理定理7 7*

13、* (定理4.4.5, p120): (求分园多项式) xn 1 = Q(d)(x)为分圆多项式， Q(d)(x) = = 为MobiusMobius函数函数， (m)= 0, m有平方因子 =(-1)k, m 不含平方因子, 且可分 解为k个因子的积 = 1 , m =1ndddxQ|)()(dmmmdmx|)/() 1(dmmmmdx|)(/) 1(六、有限域GF(q)的加法结构1. 基本概念1) 周期:模拟乘法的级 a+a +a +a +a =na =0 n个a 相加，即加法幂，记为na (课本的na不是n乘a） 任意aGF(q)(a0),满足na =0的最小正整数或。2）特征：乘法单位

14、元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矛盾。 （根据结合律

15、）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)中的元素npkkezezezezezkZzezknnnnnpppppppp)()()()() ,1111（六、有限域GF(q)的加法结构定理定理1212

16、: 在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)若F

17、q上多项式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),在这个域中， 。0)(xf可见，如果f(x)是GF(p)上的素多项式，而且f(w)=0, 则f(x)为w的最小多项式。六、有限域GF(q)的加法结构定理定理 15 15 (课本没有)：设Fq为FQ的真子域，是FQ的本原元， 的

18、次数为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 qm10miiia10miiia10miiia10miiia10miiib0)(1021miiiiba10miiia六、有限域GF(q)的加法结构第二步：证Q qm 为FQ的本原域元素，则 FQ: = k 又设在Fq的

19、最小多项式为 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)：有限域 的阶必为其特征的幂，因此它是素数的幂。 10miiimf2011012011101miiimiiimmiiimmmiiimmffffff）（六、有限域GF(q)的加法结构3共轭根: 定理定理1616 （定理4.5.6）: f(x)为Fp上的多项式， w为Fp

20、的扩展域上的元素且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 （mod n)P P对模对模n n的方次数的方次数: 满足pm 1 (mod n )的最小整数m称为p对模n的方次数0)(npwfn

21、pw2pw1mpwwwmppppppwwwmm)(六、有限域GF(q)的加法结构定理定理1616* * （推论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)等于F

22、qx/f(x)中 的级数。10)(miqiwxx七、有限域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)的全部根。 rpFspFmqxmxfxfxf| )()()(且，为素多项式mqxmqFrrspppFF:0nq七、有限域GF(q)的代数结构定理定理

23、22 22 (定理4.6.8） Fq上的m次既约多项式的数目是 . (d)为Mobius函数。 mdddmqdm1|/)(/八、小结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) 任意两个同阶的域同构.所有方法生成的有限域本质上是一样的，只是表示方法（即加法表与乘法表不一样）不一样，只要找到一种方法生成即可。0)(11qiiq

24、xxxx八、小结如何求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)mdddmqdm1|/)(/,.,

25、1 , 0)(/ 1, 0mFfkkkppkxfxxfxF考察元素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个共扼根系共扼