有限域基础有限域基础1.群群群的定义群的定义设G是一个集合,G上定义了一种运算,记为“”,如果该运算满足 i)a,bG,(a b)c a (b c);ii)存在一个eG,对于aG,有ae ea a成立,称e为G的单位元;iii)aG,存在a1G,使得aa1 a1a e成立,称a1为a的逆元;则称G在定义的运算下构成一个群.若该运算还满足条件 iV)a,bG,a b b a;则称G在定义的运算下构成一个交换(abel)群.循环群循环群设G是一个群,如果存在一个gG,对任意的bG,有整数jZ,使得b aj,称G为循环群,a为G的生成元.子群子群设G是一个群,子集HG,如果H在G的运算下仍构成一个群,则H为G的子群.例例1.1:全体整数Z构成的集合在加法的运算下构成一个交换(abel)群.H hZ|h 0 mod 3构成G的一个子群.例例1.2:集合Fp 0,1,p 1在加法的运算下构成一个交换(abel)群,Fp*在乘法运算下构成一个交换群,且都是循环群.2.环环环的定义环的定义 设R是一个集合,R上定义了两种运算,加法“”和乘法“”,如果运算满足 i)加法运算构成abel群;ii)a,b,cR,(a b)c a (b c);iii)a,b,cR,a (b c)a b a c,(b c)a b a c a;则称R在定义的运算下构成一个环.若该运算还满足条件 iV)a,bG,a b b a则称R为交换环.子环子环 设R是一个环,如果S R在R的运算下仍是一个环,称S为R的子环.理想理想 设J R,如果J满足 i)J为R的子环;ii)aJ,rR,有ar J且raJ,则称J为R的理想.交换环的主理想交换环的主理想 设R是一个交换环且J是R的理想,如果存在aR,使J (a)ka|kJ,则称J为R的主理想,a为J的生成元.例例2.1:全体整数Z对于数的加法和乘法构成一个环,通常称 为整数环.但全体正整数对于加法和乘法就不构成一 个环,因为不满足加法条件iii,iv.例例2.2:设f(x)Fpx是Fp上的多项式环中n次多项式,则Fpx/f(x)g(x)Fpx|deg(g(x)n 构成一环,称为Fpx模f(x)的剩余类环.令f(x)g(x)h(x);A k(x)Fpx/f(x)|g(x)整除k(x)Fpx/f(x)则A构成Fpx/f(x)的一个理想且为主理想.主理想整环主理想整环 若环R的每个理想都是主理想,则称R为主理想整环,易知,剩余类环和多项式环都是主理想整环.3.有限域有限域3.1 有限域的概念有限域的概念 在有限集合F上定义了两个二元运算:加法“”和乘法“”,如果(F,)是交换群,F的非零元素对乘法构成交换群,而且乘法对加法满足分配律,则称(F,)是有限域.3.2 有限域的主要性质有限域的主要性质 i)在有限域中所有的元素的加法阶都相同而且都是素数,称该素数为有限域的特征.(或者有另外的定义:对于aF,满足na 0的最小正整数n为F的特征)ii)p素数,阶为q pm的有限域Fq的特征为p;iii)Fq的非零元素对乘法构成循环群,循环群的生成元为该有限域的生成元;iv)利用F2上的m次不可约多项式f(x)定义有限域F2m:F2m=F2x/(f(x)F2m am 1xm 1 a1x a0|ai0,1 为了方便,表示成向量的集合F2m(am 1 a1 a0)|ai0,1,F2m 中加法是简单的向量按位相加,乘法是向量对应的多项式相乘模f(x)的结果.若设为f(x)的一个根，f()=0,则F2m=1,1+,且1,2m-1根是线性空间F2m/F2的一组基。
例例:F2上的4阶不可约多项式f(x)x4 x 1,F24 a3x3 a2x2 a1x a0|ai0,1 a3 a2 a1 a0|ai0,1 则有(1 0 1 1)(1 0 0 1)(0 0 1 0)(1 0 1 1)(1 0 0 1)(1 1 1 1)这是因为 (x3 x2 1)(x3 1)x6 x5 x2 1 x3 x2 x 1 mod f(x).3.3 有限域上的多项式环有限域上的多项式环有限域F上定义的多项式集合Fx f(x)|f(x)anxn a1x a0,aiF,an 0,n 0令g(x),h(x)分别是k次多项式和l次多项式,g(x)akxk a1x a0,ak 0,h(x)blxl b1x b0,bl 0.在Fx上定义标准的加法和乘法:g(x)h(x)(ai bi)xi,g(x)h(x)cixi,其中ci aib0 ai 1b1 a0bi.(Fx,)是有限域F上的多项式环.),max(0kli不可约多项式不可约多项式 Fx中次数大于1的多项式 f(x)不能写成两个低次多项式的乘积,称f(x)是F上不可约多项式.因子因子 多项式环Fx 中,对次数不为零的两个多项式g(x),h(x),存在惟一的Fx中的多项式q(x),r(x),使得g(x)q(x)h(x)r(x),其中r(x)的此时小于h(x)的次数,如果r(x)0,则称h(x)是g(x)的因子.例例3.3.1:F2x中g(x)x6 x5 x3 x2 x 1,h(x)x4 x3 1,那么q(x)x2,r(x)x3 x 1.最大公因子最大公因子 有限域Fp 0,1,p 1上的多项式环Fpx 中,若f(x)同时是非零多项式g(x),h(x)的因子,而且是所有g(x),h(x)公共因子中次数最高的,则称f(x)是g(x),h(x)的最大公因子,当f(x)1时,称g(x),h(x)互素.可以使用Euclidean算法计算最大公因子.若f(x)是g(x),h(x)的最大公因子,则Fpx中存在s(x),使得s(x)g(x)t(x)h(x)f(x).3.4 有限域上的多项式有限域上的多项式 多项式的阶多项式的阶(周期周期)设f(x)Fqx,deg(f)m 1,f(0)0,则存在正整数e qm 1,使得 f(x)|xe 1成立的最小的正整数e称为多项式f(x)的阶,记为ord(f)或p(f).不可约多项式的阶不可约多项式的阶 设 f(x)Fqx是 m 次不可约多项式,f(0)0,则f(x)|qm 1.本原多项式本原多项式 设f(x)Fqx是 m 次不可约多项式,f(0)0,如果p(f)qm 1,则称f(x)为Fqx中本原多项式.作业 作业3：克莱茵4元群克表示为G=1,a,b,c，其运算为：1x=x,xG,ab=c,ac=b,bc=a,请实现上述运算。
作业4：有限域F2m=F2x/(f(x),f(x)是m次不可约多项式F2m am 1xm 1 a1x a0|ai0,1 为了方便,表示成向量的集合F2m(am 1 a1 a0)|ai0,1,若设为f(x)的一个根，f()=0,则F2m=1,1+,任意输入x,y F2m,试实现x+y,x y，并将结果写入文件中。