有限域

StateKeyLaboratoryofIntegratedServicesNetworksChapter4有限域内容近世代数基本知识复习子环与理想循环群有限域的乘法结构有限域的加法结构有限域的代数结构多项式的因式分解正规基和对偶基同余和剩余类同余若整数a和b被同一正整数m除时，有相同的余数，则称a、b关于模m同余，记为若则剩余类给定正整数m，将全体整数按余数相同进行分类，可获得m个剩余类：)(modmba1,,1,0mbabababa,1122(mod),(mod),abmabm12121212(mod),(mod)aabbmaabbm同态与同构代数系统满足一定规律或定律的系统称为代数系统。且有：1.有一群元素构成一个集合；2.在元素集合中有一个等价关系；3.在集合中定义了一个或数个运算，通过运算建立起元素之间的关系；4.有一组假定。同态与同构：设f是代数系统(A,·)到(B,*)的映射，如果它满足条件f(a1·a2)=f(a1)*f(a2)a1,a2∈A,f(a1),f(a2)∈B则称f是A到B的同态映射，集合A与B同态。如果同态映射f又是双射，则称为同构映射，集合A与B同构。若f是A到A自身的同构映射，则称为自同构。群设G是一个非空集合，并在G内定义了一种代数运算“。”，若满足：则称G构成一个群。若加法，恒等元用0表示，若为乘法，恒等元称为单位元阿贝尔群(AbelianGroup)、可换群、交换群：满足交换律Gba,1)封闭性。对任意，恒有GbaGcba,,2)结合律。对任意，恒有cbacba3)G中存在一恒等元e,对任意Ga，使aaeea4)对任意Gaeaaaa11，存在a的逆元Ga1，使环非空集合R中，若定义了两种代数运算加和乘，且满足：1)集合R在加法运算下构成阿贝尔群2)乘法有封闭性3)乘法结合律成立，且加和乘之间有分配律环＝阿贝尔加群＋乘法半群相关概念有单位元环（乘法有单位元）交换环（乘法满足交换率）整环（无零因子环）域定义：非空集合F，若F中定义了加和乘两种运算，且满足：1)F关于加法构成阿贝尔群，加法恒等元记为02)F中所有非零元素对乘法构成阿贝尔群，乘法恒等元记为13)加法和乘法之间满足分配律域是一个可换的、有单位元、非零元素有逆元的环，且域中一定无零因子。元素个数无限的域称为无限域；元素个数有限的域称为有限域，用GF(q)或Fq表示q阶有限域。有限域也称为伽逻华域。定义若环R中的子集S，在环R中的定义的代数运算也构成环，则称S为R的子环，R为S的扩环判定非空子集S是R的子环的充要条件是：•对任何两个元素a,b∈S，恒有a-b∈S；•对任何两个元素a,b∈S，恒有ab∈S；例子全体整数集合构成一个可换环。以某一整数m的倍数全体构成其中的一个子环。如m=3,集合{…,-3,0,3,…}构成一个子环子环理想理想非空子集I是交换环R的理想的充要条件是：•对任何两个元素a,b∈I，恒有a-b∈I；Abel加群•对任何两个元素a∈I,r∈R，恒有ar=ra∈I；若I包含了a，则包含了a的一切倍元I构成一个Abel加群，所以可用它作为一个正规子群，把R中的元素进行分类划分陪集主理想若理想中的元素由一个元素的所有倍数及其线性组合生成，则称这个理想为主理想。在可换环R中，由一个元素a∈R所生成的理想I(a)={ra+na|r∈R,n∈Z}称为环R的一个主理想，称元素a为该主理想的生成元剩余类环定义设R是可换环，I为R的一个理想，于是R模I构成一个可换环，称它为环R以理想I为模的剩余类环例R=Z，I3={…,-3,0,+3,…}，R以I划分陪集为集合构成一个可换环0,3,0,3,;1,2,1,4,;2,1,2,5,0,1,2多项式多项式f(x)=fnxn+fn-1xn-1+…+f1x+f0其中i=0,1,…,n，该多项式称为域Fp上的多项式多项式次数degf(x)系数不为零的x的最高次数称为多项式f(x)的次数首一多项式最高次数的系数为1的多项式既约多项式设f(x)是次数大于零的多项式，若除常数和常数与本身的乘积以外，再不能被域Fp上的其他多项式整除，则称f(x)为域Fp上的既约多项式f(x)是否既约与讨论的域有关：f(x)=x2+1在实数域上既约，但在复数域上f(x)=(x+i)(x-i)，考虑GF(2)上？piFf既约多项式每一个首一多项式必可分解为首一既约多项式之积，并且当不考虑因式的顺序时，该分解是唯一的其中，pi(x)为首一既约多项式，为正整数d次多项式f(x)不可能有多于d个的一次因式,至多有d个根α为之根的充要条件是(x-α)|f(x)若p(x)是f(x)的k重既约因式，则p(x)必是f’(x)的k-1重既约因式1212()()()()iifxpxpxpxiGCD&LCMGCD(f(x),g(x))：同时除尽f(x)和g(x)的次数最高的首一多项式LCM[f(x),g(x)]：同时被f(x)和g(x)除尽的次数最低的首一多项式f(x)g(x)=(f(x),g(x))[f(x),g(x)]Euclidean算法(f(x),g(x))=A(x)f(x)＋B(x)g(x)98725343343335343()1()(1)(1)()1(1)(1)(),()11()()(1)()()()()fxxxxxxxxxxxxxgxxxxxxfxgxxfxxxxxxxAxfxBxgx多项式的加法和乘法设f(x)=fnxn+fn-1xn-1+…+f1x+f0g(x)=gmxm+gm-1xm-1+…+g1x+g0多项式相等若m=n，且对所有i,fi=gi,则f(x)=g(x)多项式加（若nm)f(x)+g(x)=fnxn+…+fm+1xm+1+(fm+gm)xm+…+(f1+g1)x+(f0+g0)多项式乘f(x)g(x)=hn+mxn+m+hn+m-1xn+m-1+…+h1x+h0piFfpiFg00,1,,,1,,ijijjiijijjimfgimnmhfgimmn多项式剩余类环结论按上述定义的加法和乘法运算，Fp[x]构成一个具有单位元、无零因子的可换环多项式剩余类环以一个Fp上的多项式f(x)=fnxn+fn-1xn-1+…+f1x+f0为模的剩余类全体构成一个多项式剩余类环Fp[x]上任一多项式f(x)的一切倍式集合If(x)组成一个理想。以此理想把Fp[x]划分陪集，这些陪集全体就构成了模f(x)的剩余类环剩余类之间的加法和乘法运算规则xbxaxbxaxbxaxbxaExamplesGF(2)上的多项式f(x)=x2+1的剩余类全体为：对所定义的加法和乘法运算，构成剩余类环元素没有乘法逆元1,,1,0xx22223322332230:01(1)(1)(1)1:11:111:1++1xxxxxxxxxxxxxxxxxxxxxxx32xx1x22100;111;111110xxxxxxxxxxxExamplesGF(2)上的多项式f(x)=x2+x+1的剩余类全体为：对所定义的加法和乘法运算，构成域结论：若n次首一多项式f(x)在域Fp上既约，则f(x)的剩余类环构成一个有pn个元素的有限域1,,1,0xx2222323232320:01(1)(1)(1)1:1+1:111:1+xxxxxxxxxxxxxxxxxxxxxxxx3231xxxx主理想环与同构多项式环Fp[x]的一切理想均是主理想多项式剩余类环Fp[x]/f(x)中的每一个理想都是主理想。且该主理想的生成元必除尽f(x)GF(2)上二次多项式与GF(2)上的三重。它们的元素具有如下的一一对应关系且在适当定义运算之后具有同样的性质与结构。称具有这种对应关系的两个集合为同构2;,,0,1abxcxabcabc定义：由一个单独元素的所有幂次所构成的群称为循环群，该元素为循环群的生成元幂次的含义与在群上所定义的运算有关。若定义加法运算，幂运算为连加运算；若定义乘法运算，则幂运算为连乘。循环群的生成元不止一个。凡是循环群必是可换群。例：模4剩余类全体关于加法运算构成循环群，生成元为1和3。循环群的定义23411;2111;31111;01111132413333;2333;33;033333有限循环群和无限循环群若元素a的所有幂次均不相同(无限循环群)存在整数h和k，使得ak=ah，则有a生成的循环群中元素个数有限(有限循环群)循环群元素的级若ak=ah，则有ah-k=e，定义使an=e的最小正整数为有限循环群元素a的级。a0=e,a1,…,an-1均不相同an=e，则a的一切幂次生成的元素都在G(a)={a0=e,a1,…,an-1}中可换群G中的每一个元素a都能生成一个循环群。若a为有限级，则生成有限循环群，a的级即为循环群中元素的个数(循环群的阶)循环群的构造及性质若a是n级元素，则am=e的充要条件是n|m若a是n级元素，b是m级元素，且(n,m)=1,则(ab)的级为nm若a是n级元素，则ak的级为n/(k,n)若a是dk级元素，则ak为d级元素n阶循环群中，每个元素的级是群阶数n的因子单位原根：n阶循环群中，每一个n级元素称为n次单位原根n阶循环群中有个单位原根欧拉函数：0,1,…,n-1中与n互素的个数如n=12=3×22，则有限循环群中级的性质nn111isiiinpp1212ssnppp2111122(21)3(31)4有限域的乘法结构域的乘法群必为某一个元素生成的循环群，即q阶域中必能找到一个，其级为q-1。即所有有限域元素都能表示成生成元的幂次的形式，此时的生成元称为本原元。在GF(q)中，每一个非0元素均满足xq-1=1，即都是方程xq-1-1=0的根。反之，xq-1-1=0的根必在GF(q)中GF(q)中必有本原域元素存在在含有n次单位原根的任意域上，有下述因式分解101nniixx分圆多项式以GF(q)中彼此不同的d级元素为全部根的首一多项式，称为d级分圆多项式，记为Q(d)(x)d级分圆多项式Q(d)(x)的次数为其中为Mobius函数，pi为素数d1()0|1nnididdnxxQx()||11dnnnddddddndnQxxx210|()(1),,11ikkpaaappaExamples分解GF(2)上的x15-1多项式15(1)(3)(5)(15)(1)(1)(3)1(3)3(1)32(5)1(5)5(1)5432(15)(15)3(5)5(3)15(1)1()()()()()1(1)()1(1)1(1)1()1(1)1(1)1()1(1)(1)(1)xQxQxQxQxQxxxQxxxxxxxQxxxxxxxxxQxxxxx315115875431(1)(1)(1)1xxxxxxxxxx有限域的加法结构域的特征满足ne=0的最小n值为域的特征，这里e为乘法单位元，0为域的零元，n取自正整数GF(p)的特征为p每一个域的特征或为素数，或为∞域的特征说明了域中加法运算的循环性，而域中元素的级则说明了乘法运算的循环性。元素的周期对域中元素a≠0，满足na=0的最小n值为a的周期。（