《有限域基础选讲.ppt》由会员分享，可在线阅读，更多相关《有限域基础选讲.ppt（14页珍藏版）》请在三一办公上搜索。
1、有限域基础,1.群,群的定义设G是一个集合,G上定义了一种运算,记为“”,如果该运算满足 i)a,bG,(ab)ca(bc);ii)存在一个eG,对于aG,有aeeaa成立,称e为G的单位元;iii)aG,存在a1G,使得aa1a1ae成立,称a1为a的逆元;则称G在定义的运算下构成一个群.若该运算还满足条件 iV)a,bG,abba;则称G在定义的运算下构成一个交换(abel)群.,循环群设G是一个群,如果存在一个gG,对任意的bG,有整数jZ,使得baj,称G为循环群,a为G的生成元.子群设G是一个群,子集HG,如果H在G的运算下仍构成一个群,则H为G的子群.例1.1:全体整数Z构成的集合
2、在加法的运算下构成一个交换(abel)群.HhZ|h0 mod 3构成G的一个子群.例1.2:集合Fp0,1,p1在加法的运算下构成一个交换(abel)群,Fp*在乘法运算下构成一个交换群,且都是循环群.,2.环,环的定义 设R是一个集合,R上定义了两种运算,加法“”和乘法“”,如果运算满足 i)加法运算构成abel群;ii)a,b,cR,(ab)ca(bc);iii)a,b,cR,a(bc)abac,(bc)abaca;则称R在定义的运算下构成一个环.若该运算还满足条件 iV)a,bG,abba则称R为交换环.,子环 设R是一个环,如果SR在R的运算下仍是一个环,称S为R的子环.理想 设JR
3、,如果J满足 i)J为R的子环;ii)aJ,rR,有arJ且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);Ak(x)Fpx/f(x)|g(x)整除k(x)Fpx/f(x)
4、则A构成Fpx/f(x)的一个理想且为主理想.主理想整环 若环R的每个理想都是主理想,则称R为主理想整环,易知,剩余类环和多项式环都是主理想整环.,3.有限域,3.1 有限域的概念 在有限集合F上定义了两个二元运算:加法“”和乘法“”,如果(F,)是交换群,F的非零元素对乘法构成交换群,而且乘法对加法满足分配律,则称(F,)是有限域.,3.2 有限域的主要性质,i)在有限域中所有的元素的加法阶都相同而且都是素数,称该素数为有限域的特征.(或者有另外的定义:对于aF,满足na0的最小正整数n为F的特征)ii)p素数,阶为qpm的有限域Fq的特征为p;iii)Fq的非零元素对乘法构成循环群,循环群
5、的生成元为该有限域的生成元;,iv)利用F2上的m次不可约多项式f(x)定义有限域F2m:F2m=F2x/(f(x)F2m am1xm1a1xa0|ai0,1 为了方便,表示成向量的集合F2m(am1a1a0)|ai0,1,F2m 中加法是简单的向量按位相加,乘法是向量对应的多项式相乘模f(x)的结果.若设为f(x)的一个根，f()=0,则F2m=1,1+,且1,2m-1根是线性空间F2m/F2的一组基。例:F2上的4阶不可约多项式f(x)x4x1,F24a3x3a2x2a1xa0|ai0,1a3a2a1a0|ai0,1 则有(1 0 1 1)(1 0 0 1)(0 0 1 0)(1 0 1
6、1)(1 0 0 1)(1 1 1 1)这是因为(x3x21)(x31)x6x5x21 x3x2x1mod f(x).,3.3 有限域上的多项式环,有限域F上定义的多项式集合Fx f(x)|f(x)anxna1xa0,aiF,an0,n0令g(x),h(x)分别是k次多项式和l次多项式,g(x)akxka1xa0,ak0,h(x)blxlb1xb0,bl0.在Fx上定义标准的加法和乘法:g(x)h(x)(aibi)xi,g(x)h(x)ci xi,其中ciai b0ai1b1 a0bi.(Fx,)是有限域F上的多项式环.,不可约多项式 Fx中次数大于1的多项式 f(x)不能写成两个低次多项式的
7、乘积,称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)x6x5x3x2x1,h(x)x4x31,那么q(x)x2,r(x)x3x1.,最大公因子 有限域Fp0,1,p1上的多项式环Fpx中,若f(x)同时是非零多项式g(x),h(x)的因子,而且是所有g(x),h(x)公共因子中次数最高的,则称f(x)是g(x),h(x)的最大公因子,当f(x)1时,称
8、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)m1,f(0)0,则存在正整数eqm1,使得 f(x)|xe1成立的最小的正整数e称为多项式f(x)的阶,记为ord(f)或p(f).不可约多项式的阶 设 f(x)Fqx是m次不可约多项式,f(0)0,则f(x)|qm1.本原多项式 设f(x)Fqx是m次不可约多项式,f(0)0,如果p(f)qm1,则称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 am1xm1a1xa0|ai0,1 为了方便,表示成向量的集合F2m(am1a1a0)|ai0,1,若设为f(x)的一个根，f()=0,则F2m=1,1+,。任意输入x,y F2m,试实现x+y,x y，并将结果写入文件中。,
