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

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,信息安全数学基础环和域基础知识,环的定义,环,(Ring),:,一个非空集合,S,上有两种运算：加法“,+”,和乘法“,”，如果这两种运算满足以下性质，就称为环：,(R, +),是一个交换群，加法单位元记为,0,（称为零元）；,R,关于乘法“,”满足结合律,: (a,b),c=a,(b,c),并有单位元,记为,1,；,分配律成立,: (a+b),c=a,c+b,c, c,(a+b)=c,a+c,b.,注：,0,是抽象的写法，不同于整数中的,0.,“,+”,和“,”是抽象的运算,环的例子（,1,）,在通常的加法和乘法运算下，,Z, Q, R,和,C,都是环，加法单位元为,0,，乘法单位元为,1,。,环的例子（,2,）,对任意,n0,，在模,n,加法和模,n,乘法下，,Z,n,是一个环。加法单位元为,0,，乘法单位元为,1,。,环的例子,(3),多项式环,Zx,环中的零元,对于环中的任意元素,a,都有,0a=a0=0,一般地，,0,与,1,不相等，否则,1a=a,而,0a=0,，这表明环中只有一个元素，平凡情形，一般不考虑,所以,0,关于乘法没有可逆元,环的几个性质,设,R,是一个环,a,b R,有,:,a(-b)=(-a)b=-(ab),(-a)(-b)=ab,交换环,类似于交换群的定义，如果一个环关于乘,法运算具有可交换性，就称它为交换环。,无零因子环,设,R,是一个环,如果存在,a,b,R, a0, b0,但,ab=0,那么称,R,是有零因子环,否则称,R,是无零因子环,.,ab=0 a=0,或,b=0.,无零因子环的性质,性质,1.,设,R,是无零因子环,那么,若,a,0, ab=ac,则,b=c;,若,a,0, ba=ca,则,b=c.,性质,2.,设,R,是无零因子环,那么,R,中非零元的加法阶相等,或者为,或者为素数,.,子环、理想和商环,子环,(subring),设,R,是一个环, S,是,R,的非空子集,如果,S,关于,R,的运算也构成环,则称,S,是,R,的子环,.,理想,(Ideal),设,R,是一个环, I,是,R,的一个子环,如果,a,I ,rR,有,ra,R,ar,R,则称,I,是,R,的一个理想,.,理想的例子,Fx,为数域,F,上的一元多项式环, I=a,1,x+a,2,x,2,+a,n,x,n,|a,i,F, n,N,即,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,关于加法构成阿贝尔群，加法恒等元记为,0,2) F,中所有非零元素对乘法构成阿贝尔群，乘法恒等元记为,1,3),加法和乘法之间满足分配律,则,F,与这两种运算构成域,每一个非零元都是可逆元的有单位元的交换环,如实数域,复数域,有理数域,域的例子（,1,）,在通常的加法和乘法运算下，,Q, R,和,C,都是域。,域的例子（,2,）,令,p,是一个素数，在模,p,加法和模,p,乘法,运算下，,Z,p,是一个域,.,也记为,F,p,或者,GF (p).,注意：,整数环,Z,不是域；,当,n,是合数时，,Z,n,不是域。,有限群、子群、商群和群的阶的概念可,以直接推广到环和域中。,域的特征,F,是域，其特征,char(F),定义为单位元,1,的加法阶,即使得 的最小自然数,n,，如果不存在这样的自然数，那么记,char(F) =.,性质：,如果,char(F),有限，那么一定是素数,.,域的例子（3）,构造方法,域上的多项式环,不可约多项式,利用不可约多项式构造有限域,Z Z,p,Fx Fx/f(x),F,p,=Z,p,p,为素数,F,为,p,阶有限域,f,为,n,次不可约多项式,Fx/f(x),为,p,n,阶有限域,域上的多项式的带余除法,设,F,是一个域，,f, g,是,Fx,中的两个多项式，且,g,不为,0,，类似于整数的除法：,f=gq+r,，,其中，,q, r,是,Fx,中的两个多项式，且,deg(r)deg(g).,带余除法的例子,f(x)=x,5,+x,4,+x,3,+x,2,+x+1F,2,x,g(x)=x,3,+x+1F,2,x,q=x,2,+x, r=x,2,+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)=x,2,- 2x+2,：,.,（,1,）在复数域上可约；,（,2,）在实数域上不可约；,（,3,）在,F,3,上不可约,.,利用不可约多项式构造域,定义,: Fx,是域,F,上的多项式环, f,g,r,Fx, g0,满足,f = gq + r, deg(r)deg(g),称,r,为,f,除以,g,的余式,记为,rf (mod g).,考虑,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),中元素的个数是,p,n,.,Fx/f(x),是,Fx,中所有次数小于,deg(f)=n,、系数取遍,F,中所有,p,个元素的多项式全体构成的集合,.,共有,p,n,个这样的多项式,.,注意：在此定理中，并没有假设,p,是素数，事实上，,F,可以是任意域，称,Fx/f(x),为由,基域,F,通过域扩张得到的,扩域,.,P,n,阶域的存在性,Z,p,是阶为,p,的域；,对任意的有限域,F,和任意的正整数,n,，,Fx,中一定存在,n,次不可约多项式,.,推论,对于每一个素数,p,和每一个正整数,n,，都存在一个阶为,p,n,的有限域,.,域,F,p,x/f(x),中结构是很清楚的，它仅是所有次数小于,n,、系数在,F,p,的所有多项式的集合；,在同构的意义下，这是唯一的阶为,p,n,的有限域,.,例：,由,GF(2),上的既约多项式,p(x)= x,4,+x+1,扩成,GF(2,4,),4位向量形式 多项式形式 生成元幂形式 指数形式,0000 0 0 -,0001 1,a,0,0,0010,x a,1,1,0100,x,2,a,2,2,1000,x,3,a,3,3,0011,x+1 a,4,4,0110,x,2,+x a,5,5,1100,x,3,+x,2,a,6,6,4位向量形式 多项式形式 生成元幂形式 指数形式,1011,x,3,+x+1 a,7,7,0101,x,2,+1 a,8,8,1010,x,3,+x a,9,9,0100,x,2,a,10,10,0111,x,2,+x+1,a,11,11,1110,x,3,+x,2,+x a,12,12,1111,x,3,+x,2,+x+1 a,13,13,1101,x,3,+x,2,+1,a,14,14,1001,x,3,+1,a,15,15,例子,(1),实数域,: R,不可约多项式,f(x) = x,2,+1,Rx/f(x),(ax+b)+(cx+d) = (a+c)x+(b+d),(ax+b)(cx+d) = acx,2,+(ad+bc)x+bd,=(ad+bc)x+(bd-ac),(mod,f(x),),Rx/f(x), C,ax+b, ai+b,求逆,g(x)=ax+b (a0),例子,(2),二元域,F,2,0+0=1,0+1=1 1+0=1,1+1=0,00=0,01=0 10=0,11=1,不可约多项式,f(x)=x,8,+x,4,+x,3,+x+1,加法,乘法,求逆,第一章,学生讲解内容,（每人选一个主题）,1,）置换密码,2,）单表代换密码,3,）多表代换密码,4,）,Vernam,密码,5,）,Playfair,密码,6,）,Hill,密码,7,）公钥密码,8,）私钥密码,谢谢大家！,结 语,