信息安全数学基础_环和域基础知识.ppt

信息安全数学基础-环和域,计算机科学与技术系王常远chywang12813980688127184780948,环的定义,环(Ring):一个非空集合S上有两种运算：加法“+”和乘法“”，如果这两种运算满足以下性质，就称为环：(R,+)是一个交换群，加法单位元记为0（称为零元）；R关于乘法“”满足结合律:(ab)c=a(bc),并有单位元,记为1；分配律成立:(a+b)c=ac+bc,c(a+b)=ca+cb.注：0是抽象的写法，不同于整数中的0.“+”和“”是抽象的运算,环的例子（1）,在通常的加法和乘法运算下，Z,Q,R和C都是环，加法单位元为0，乘法单位元为1。,环的例子（2）,对任意n0，在模n加法和模n乘法下，Zn是一个环。加法单位元为0，乘法单位元为1。,环的例子(3),多项式环Zx,环中的零元,对于环中的任意元素a,都有0a=a0=0一般地，0与1不相等，否则1a=a,而0a=0，这表明环中只有一个元素，平凡情形，一般不考虑所以0关于乘法没有可逆元,环的几个性质,设R是一个环,a,bR,有:a(-b)=(-a)b=-(ab)(-a)(-b)=ab,交换环,类似于交换群的定义，如果一个环关于乘法运算具有可交换性，就称它为交换环。,无零因子环,设R是一个环,如果存在a,bR,a0,b0,但ab=0,那么称R是有零因子环,否则称R是无零因子环.ab=0a=0或b=0.,无零因子环的性质,性质1.设R是无零因子环,那么若a0,ab=ac,则b=c;若a0,ba=ca,则b=c.,性质2.设R是无零因子环,那么R中非零元的加法阶相等,或者为,或者为素数.,子环、理想和商环,子环(subring),设R是一个环,S是R的非空子集,如果S关于R的运算也构成环,则称S是R的子环.,理想(Ideal),设R是一个环,I是R的一个子环,如果aI,rR,有raR,arR,则称I是R的一个理想.,理想的例子,Fx为数域F上的一元多项式环,I=a1x+a2x2+anxn|aiF,nN,即I是由所有常数项为0的多项式构成的集合,则I是Fx的理想.,主理想,由R中一个元素a生成的理想称为主理想.,商环,设I是环R的理想,在加法商群R/I上定义如下乘法(x+I)(y+I)=(x+y)+I则R/I关于加法和乘法构成一个环.,环同态,设R和R是两个环,f是R到R的一个映射,如果a,bR,均有f(a+b)=f(a)+f(b),f(ab)=f(a)f(b),那么称f是R到R的环同态映射.如果f是满射,那么称R和R同态;如果f是双射,那么称R和R同构.,类似的有环同态基本定理,概念的类比,域的定义,域(Field),非空集合F，若F中定义了加和乘两种运算，且满足：1)F关于加法构成阿贝尔群，加法恒等元记为02)F中所有非零元素对乘法构成阿贝尔群，乘法恒等元记为13)加法和乘法之间满足分配律则F与这两种运算构成域每一个非零元都是可逆元的有单位元的交换环如实数域复数域有理数域,域的例子（1）,在通常的加法和乘法运算下，Q,R和C都是域。,域的例子（2）,令p是一个素数，在模p加法和模p乘法运算下，Zp是一个域.也记为Fp或者GF(p).,注意：整数环Z不是域；当n是合数时，Zn不是域。有限群、子群、商群和群的阶的概念可以直接推广到环和域中。,域的特征,F是域，其特征char(F)定义为单位元1的加法阶,即使得的最小自然数n，如果不存在这样的自然数，那么记char(F)=.,性质：如果char(F)有限，那么一定是素数.,域的例子（3）,构造方法,域上的多项式环不可约多项式,利用不可约多项式构造有限域,ZZp,FxFx/f(x),Fp=Zp,p为素数,F为p阶有限域f为n次不可约多项式,Fx/f(x)为pn阶有限域,域上的多项式的带余除法,设F是一个域，f,g是Fx中的两个多项式，且g不为0，类似于整数的除法：f=gq+r，其中，q,r是Fx中的两个多项式，且deg(r)deg(g).,带余除法的例子,f(x)=x5+x4+x3+x2+x+1F2xg(x)=x3+x+1F2xq=x2+x,r=x2+1,不可约多项式,定义:设F是一个域，f(x)Fx,f(x)的次数为正数，若f(x)=g(x)h(x)，其中f(x),h(x)Fx,则g(x)和h(x)中必有一个为常数多项式,那么称f(x)是不可约的.,注意：多项式的可约性依赖于该多项式定义在什么样的代数结构上.一个多项式在一种代数结构上不可约，但可能在另一种代数结构上就是可约的.,例,对于二次多项式f(x)=x2-2x+2：.（1）在复数域上可约；（2）在实数域上不可约；（3）在F3上不可约.,利用不可约多项式构造域,定义:Fx是域F上的多项式环,f,g,rFx,g0,满足f=gq+r,deg(r)deg(g),称r为f除以g的余式,记为rf(modg).考虑Fx中所有多项式模g(x)的余式,将这些集合称为Fx模g(x)的多项式,记为Fx/g(x).,利用不可约多项式构造域,令F是一个域，f(x)是Fx中的一个非零多项式，那么Fx/f(x)是一个环，当且仅当f(x)在F上不可约时，Fx/f(x)是一个域.,f(x)是Fx中的一个不可约多项式，当F是域时，Fx/f(x)是一个域.将f(x)称为域Fx/f(x)的定义多项式.,定理,令F为含有p个元素的域，f(x)是F上的n次不可约多项式，那么域Fx/f(x)中元素的个数是pn.Fx/f(x)是Fx中所有次数小于deg(f)=n、系数取遍F中所有p个元素的多项式全体构成的集合.共有pn个这样的多项式.,注意：在此定理中，并没有假设p是素数，事实上，F可以是任意域，称Fx/f(x)为由基域F通过域扩张得到的扩域.,Pn阶域的存在性,Zp是阶为p的域；对任意的有限域F和任意的正整数n，Fx中一定存在n次不可约多项式.推论对于每一个素数p和每一个正整数n，都存在一个阶为pn的有限域.,域Fpx/f(x)中结构是很清楚的，它仅是所有次数小于n、系数在Fp的所有多项式的集合；在同构的意义下，这是唯一的阶为pn的有限域.,例：由GF(2)上的既约多项式p(x)=x4+x+1扩成GF(24),4位向量形式多项式形式生成元幂形式指数形式,000000-00011a000010 xa110100 x2a221000 x3a330011x+1a440110 x2+xa551100 x3+x2a66,4位向量形式多项式形式生成元幂形式指数形式,1011x3+x+1a770101x2+1a881010 x3+xa990100 x2a10100111x2+x+1a11111110 x3+x2+xa12121111x3+x2+x+1a13131101x3+x2+1a14141001x3+1a1515,例子(1),实数域:R不可约多项式f(x)=x2+1Rx/f(x)(ax+b)+(cx+d)=(a+c)x+(b+d)(ax+b)(cx+d)=acx2+(ad+bc)x+bd=(ad+bc)x+(bd-ac)(modf(x),Rx/f(x)C,ax+bai+b,求逆g(x)=ax+b(a0),例子(2),二元