有限域PPT学习课件.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,有限域及其应用,聂旭云,xynie,1,教师简介,聂旭云,研究方向：密码学，公钥密码算法，密码学相关代数理论,2,教学目的,掌握有限域的基本理论和基本方法,熟悉有限域的结构,了解有限域与多项式的关系,熟悉不可约多项式与多项式的分解,掌握有限域的应用与方法,能用基本的有限域理论解决和回答一些应用问题,如编码理论和密码理论中的有限域应用。,3,基本学习方法,紧扣定义，从定义出发，理解相关定理、性质,掌握各种代数结构的性质及相互之间的关系,4,考核方式,平时：,40%,，主要评价来源：考勤、课外作业,期末考试：60%,5,参考教材,教 材：,Finite Fields,Rudolf Lidl,Addison-Wesley Publishing Company,，,1997.,参考书：,代数学基础与有限域,.,林东岱 编著，高等教育出版社,.,代数和编码（第三版），万哲先，高等教育出版社，,2007,。,Groebner,基理论及其应用，刘木兰，科学出版社，,2000,。,6,7,教学内容,第一章 代数学基础（,4,学时）,1.1,群,1.2,环与理想,1.3,多项式环,1.4,域和扩域,第二章 有限域的结构（,8,学时）,2.1,有限域的特征性质,2.2,不可约多项式的根,2.3,迹，范数和基,24,单位根和割圆多项式,2.5,有限域元素的表示,第三章 有限域上的多项式（,8,学时）,3.1,多项式的阶和本原多项式,3.2,不可约多项式,3.3,不可约多项式的构造,3.4,有限域上多项式因式分解,8,教学内容（续）,第四章,Gr,bner,基理论（,6,学时）,4.1,项序的定义和分类,4.2,多项式的除法算法,4.3,域上的,Gr,bner,基定义及其计算方法,4.4,域上的既约,Gr,bner,基定义及其相关性质,第五章 有限域上的离散对数问题（,4,学时）,5.1,有限域上的离散对数问题,5.2 Shanks,算法,5.3 Pohlig-Heliman,算法,5.4 Pollardp,方法,5.5,指数演算方法,9,第六章 有限域上的椭圆曲线（,4,学时）,6.1,椭圆曲线上的群结构,6.2,椭圆曲线的射影坐标表示,6.3,椭圆曲线上的有理点,6.4,椭圆曲线密码学,第七章 有限域的应用（,6,学时）,7.1,有限域在流密码中的应用,7.2,有限域在公钥密码中的应用,7.3,有限域在编码中的应用,10,第一章 代数学基础,1.1,群、环、域基本概念,1.2,剩余类环、理想,1.3,多项式环,1.4,域与扩域,11,什么是域,F,是一个非空集合，定义了加法、乘法两个二元运算，对这两个运算封闭,加法满足：对于任意,a,b,cF,a+b=b+a,；交换律,(a+b)+c=a+(b+c),；结合律,存在,0 F,，使得,a+0=a,；有零元,存在,-a F,，使得,a+(-a)=0,；有负元,12,什么是域？（续）,乘法满足：对于任意,a,b,cF,ab=ba,；交换律,(ab)c=a(bc),；结合律,存在,e F,，使得,ae=a,；有单位元,存在,a,-1,F,，使得,aa,-1,=e,；有逆元,乘法对加法满足分配率,a(b+c)=ab+ac,13,域的例子,Q,，,R,，,C,14,群,什么是群？,集合,定义一个二元运算,二元运算满足封闭性、结合律,有单位元,有逆元,若满足交换律，则称为交换群，此时群中运算可认为是加法，也称为加群,15,域的定义简化,F是一个非空集合，定义了加法、乘法两个二元运算，对这两个运算封闭,对于加法构成交换群,对于乘法构成交换群,乘法对加法满足分配率,16,群的例子,Z,，,+,数域,K,中全体,n,阶可逆矩阵对于矩阵的乘法构成群称为,n,级一般线形群，记为,GL,n,(K);,GL,n,(K),中全体行列式为,1,的矩阵对于矩阵的乘法也构成群，称为特殊线形群，记为,SL,n,(K),。,17,环,集合,集合,+,加法,+,乘法,加法交换群,乘法满足结合律,加法和乘法满足分配率,环中乘法不一定有单位元也不一定要满足交换律,满足乘法交换律的环称为交换环,18,环的例子,全体有理数、全体实数、全体复数和全体整数集合对于普通的加法和乘法构成交换环,Z,+,n n,可逆矩阵,乘法,加法,?,n n,矩阵,乘法,加法,19,域,有单位元的交换环,非零元构成乘法交换群,20,群的阶、子群,定义,如果一个群,G,中元素的个数是无限多个，则称,G,是,无限群,；如果,G,中的元素个数是有限多个，则称,G,是,有限群,，,G,中元素的个数称为,群的阶,，记为,|,G,|,子群：,群,G,的非空子集,H,称为,G,的子群，如果对于,G,的运算，,H,本身成一个群。如果,H,为,G,的子群且,HG,，则,H,称为,G,的一个真子群。,21,元素的幂,由于群里结合律是满足的，所以元素连乘,a,1,，,a,2,，,，,a,n,有意义，它也是,G,中的一个元我们把,a,的,n,次连乘记为,a,n,，称为,a,的,n,次幂（或称乘方），即 ,我们还将,a,的逆元,a,1,的,n,次幂记为,a,n,，即,群的逆元（,a,1,）,1,=a,22,元素的阶,元素的阶,设,G,为群，,a,G,，如果存在整数,t,，使得,a,t,=1,，则这样的最小正整数,t,定义为,a,的阶，记为,o(a),。如果这样的,t,不存在，则,a,的阶定义为,。,定理,：,o(a)=m,，,a,n,=1,当且仅当,m|n,。,证明思路：,充分性显然。必要性围绕着,m,为最小正整数来证明。,23,循环群,循环群：,群,G,称为是循环的，如果存在元素,g使得对任一,h,G,都有一个整数,i,，使得,h=,g,i,，这样的元素,g,称为,G,的一个生成元。可记,G=.,24,等价关系,25,陪集、指数,陪集：,设,G,为一个群，,H,是群,G,的一个子群。集合,aH|aG,被称为群,G,中相对于子群,H,的,a-,左陪集，表示为,aH,，,a,为左陪集代表元。自然，也有右陪集,Ha,的概念。,指数：,G,可按其子群,H,的左陪集分排成一些两两不交的等价类。若这些等价类的个数有限，则称这个陪集的个数为,H,在,G,中的指数，记为,G:H,。,26,正规子群和商群,正规子群：,G,为群，,H,是,G,的子群，若 有 ，则称,H,为,G,的正规子群，记为,H G,。,商群：,如果群,G,的子群,H,是正规子群，则模,H,的陪集集合在运算,(aH)(bH)=(ab)H,下构成一个群，称为,G,关于,H,的商群，记为,G/H.,27,例子（从群的角度）,整数集,Z,：加群,nZ,，子群，正规子群,陪集,a+nZ,商群,Z,n,=0,1,.,n-1,28,Lagrange,定理、欧拉定理,（拉格朗日定理）如果,G,为一个有限群，,H,为,G,的子群，则,|H|,整除,|G|,，且,|G|=|H|G:H,，因此，如果,aG,，则,a,的阶整除,|G|,。,证明思路：通过元素个数的运算证明。,29,欧拉定理的传统证明方法,因为,30,循环群的性质,31,定理,1.15,的证明,32,33,离散对数,离散对数：,设,G,是循环群，,g,为,G,的一个生成元,。,群中的离散对数问题指得是给定群中的一个元素,h,，找到正整数,n,，使得,h=g,n,n,称为,h,（相对于生成元,g,）的离散对数，记为,n=,g,(h),34,离散对数的例子,例,1,：（,Z,，,+,）,离散对数问题是平凡的,例,2,：,Z,n,，模,n,剩余类组成的加法群，,g,为,Z,n,的一个生成元，离散对数问题为：给定,hZ,n,，求解,x,，使得,xgh mod n,用扩展的欧几里得算法很容易求解。,g,(h)=x=hg,-1,35,群同态,同态：设,f,：,GH,是群,G,到,H,的一个映射，如果,有,f(ab)=f(a)*f(b),则称,f,是,G,到,H,的,同态。,同构：若上述,f,是一一映射，则称,f,是,G,到,H,的,同构。,G,到,G,自身的同构称为,内自同构,核（,kernel),：,设,f,：,GH,是群同态映射,，,f,的核定义为,ker,f=,aG|f(a)=,1,H,，其中,1,H,是,H,中的单位元。,36,内自同构和共轭元,37,群同态基本定理,定理：,设,f,：,GH,是群,G,到群,H,上的,满同态映射,，那么,ker,f,是群的一个,正规子群,，而且,H,同构于商群,G,/ker,f,，即,G,/ker,f,H,。反之，如果,N,是,G,的正规子群，则映射,是,G,到,G/N,的满同态，且,ker,=N,证明思路：紧扣正规子群和同态的定义,38,子环与理想,子环：,环,R,的一个子集,S,称为,R,的子环，如果,S,关于环中的两种运算封闭并且在这两种运算之下形成一个环。,理想：,环,R,的一个子环,J,成为一个理想，如果对于任意,aJ,，,r R,，有,ar J,和,ra J,。,剩余类环,：,设,R,是一个交换环，而,I,是,R,的一个理想，记,R/I=a=a+I|a,R,按照陪集的运算，,R/I,构成一个环，称为,R,模,I,的剩余类环或商环。,39,例子（从环的角度）,整数集,Z,：环,nZ,，子环，理想,Z,n,：剩余类环,Z,n,中的乘法可逆元,a|(a,n)=1,40,整环、除环,一个环称为,整环,，如果它是一个有单位元的交换环且无零因子。,一个环称为,除环,，如果所有的非零元在乘法运算下构成群。,41,域的定义,交换除环称为域,42,定理：有限整环是域。,证明思路：根据域的定义，只需要证明每一个非零元都有逆元即可。,43,环同态,44,主理想与主理想整环,定义,设,X,是环,R,的非空子集，,I,1,，,I,2,，,是包含,X,的所有理想，则称它们的交是,由,X,生成的理想,，记为,(,X,),X,中的元素称为,(,X,),的,生成元素,当,X,是有限集时，称,(,X,),是,有限生成理想,由一个元素生成的理想,(,a,),称为,主理想,定义,如果一个整环上的理想都是主理想，则称为,主理想整环,45,商环、素理想和极大理想,定义,设,I,是具有单位元的交换环,R,的一个理想，,I,R,如果,ab,I,，总有,a,I,或,b,I,，则称,I,是,R,的一个,素理想,如果不存在另一个理想,A,(,A,R,),，使,I,A,，则称,I,是,R,的一个,极大理想,46,商环、素理想和极大理想,例,整数环,Z,内由素数,p,生成的理想,(,p,),是一个素理想，同时也是一个极大理想,证明,Z,内由素数,p,生成的理想,(,p,)=,mp,m,Z,如果,ab,(,p,),，则,p,ab,，于是,p,a,或,p,b,，所以,a,(,p,),或,b,(,p,),，,(,p,),是一个素理想,如果存在一个理想,(,n,),使,(,p,),(,n,),R,，则,n,p,，由于,p,是素数，则有,n,=1,或,n,=,p,n,=1,时,(,n,)=,Z,，,n,=,p,时,(,n,)=(,p,),，故,(,p,),是极大理想,47,48,49,50,51,有限域,Z,n,中若所有非零元构成交换群，则,Z,n,为域,所有与,n,互素的元素构成交换群,1n-1,都与,n,互素，则,n,为素数,对于任一素数,p,，,Z,p,为域,52,Z,p,Z,p,在模,p,的加法和乘法运算下是一个域,证明一：直接验证,Z,p,满足域的定义,证明二：证明,Z,p,是整环，有限整环是域,证明三：,Z,p,=Z/(p),，,Z,是主理想整环。,53,环的特征,定理：,F,是任意一域，那么,F,的特征或者是,0,或者是素数。,推论：有限域的特征是素数。,54,习题,设,p,是一个素数，则阶为,p,m,的群一定有一个阶为,p,的子群,给出一个环的例子，使该环,R,有一个子环,T,，而且,（,1,）,R,有单位元，,T,没有单位元,（,2,）,R,没有单位元，,T,有单位元,（,3,）,R,，,T,有相同单位元,（,4,）,R,，,T,有不同的单位元,（,5,）,R,不可交换，,T,可交换,55,1.3,多项式环,我们本节主要讨论域上的多项式环,56,定义（续）,57,多项式除法和不可约多项式,定理,58,带余除法,59,60,带余除法的例子,61,带余除法的例子,62,整除、因式和倍式,63,最小公倍式,64,辗转相除法,65,辗转相除法的例子,求,Z,2,x,中多项式,x,5,+x,4,+x,3,+x,2,+x+1,和,x,4,+x,2,+x+1,的最高公因式。,66,67,68,多项式的分解,定理,（因式分解唯一定理）,F,x,上的多项式,f,(,x,)=,a,n,x,n,+,a,n,1,x,n,1,+,a,1,x,+,a,0,可分解为,f,(,x,)=,a,n,，,(,k,1,，,k,2,，,，,k,r,0),其中,p,1,(,x,),，,，,p,r,(,x,),是两两不同的首一不可约多项式除,p,1,(,x,),，,，,p,r,(,x,),的排列次序外，上述分解是唯一的,69,多项式的分解,证明,首先证明存在这样的分解,如果,f,(,x,),不可约，则定理正确,如果,f,(,x,),可约，则存在,g,(,x,),，,h,(,x,),，使,f,(,x,)=,g,(,x,),h,(,x,),，,其中,0,deg(,g,(,x,),，,deg(,h,(,x,),deg(,f,(,x,),对,g,(,x,),，,h,(,x,),继续分解，一直可以把,f,(,x,),分解成互不相同的不可约多项式的幂的乘积,70,多项式的分解,再证这样的分解除排列次序外是唯一的设还存在另一分解：,f,(,x,)=,an,于是,由上式知,由于,p,1,(,x,),是不可约多项式，则,p,1,(,x,),整除右边某个不可约多项式不失一般性，设,p,1,(,x,),q,1,(,x,),，由于,p,1,(,x,),，,q,1,(,x,),都不可约得,p,1,(,x,)=,cq,1,(,x,)(,c,F,),，,而,p,1,(,x,),，,q,1,(,x,),都是首一多项式，所以,p,1,(,x,)=,q,1,(,x,),等式两边分别约去,p,1,(,x,),和,q,1,(,x,),，我们有,上述过程进行下去，可以得到两个分解除不可约因式排列次序外是相同的,71,域,72,1.4,域和扩张,定义,1.4.1,如果一个域,F,不再含有真子集作为,F,的子域，则称,F,为,素域,定理,1.4.1,阶为素数的有限域必为素域,证明,如果阶为素数,q,的域,F,有真子域，那么这个真子域一定是,F,构成的加法群的真子群，这个子群的阶一定是,q,的因子而素数,q,除,1,和,q,外无其他因子，因子,1,对应,0,这个子群，它不是域；因子,q,对应,F,全体可见,F,无真子域，,F,是素域,73,域的性质,引理,在特征为,p,的域中，下列子集,0,，,1,，,1+1,，,，,构成,p,阶素子域，而且这一素子域与,GF,(,p,),同构,证明,设,S,=0,，,1,，,1+1,，,，,建立,S,与,GF,(,p,),的下列映射,0,0,，,1,1,，,1+1,2,，,，,很容易看出这是一个同构映射，因此,S,是一个,p,阶有限域,74,域的性质,定理,1.4.2,1,）素数,p,阶域的特征为,p,2,）任何素数,p,阶域与,GF,(,p,),同构,证明,1,）设素数,p,阶域,F,的特征为,q,则由引理，,F,含有一个与,GF,(,q,),同构的,q,阶素子域,S,，而又由定理,1.4.1,，,F,是素域，所以,F,=,S,，,p,=,q,2,）由,1,和引理显然,由于任何素数,p,阶域都与,GF,(,p,),同构，这样我们可以用,GF,(,p,),代表任意素数,p,阶域，并且将,GF,(,p,),中的元素简单记为,0,，,1,，,2,，,，,p,1,75,76,余数定理,77,余数定理（续）,78,极小多项式,证明思路,：（,1,）利用,g,的极小性；,（,2,）构造理想,J=f(x)Kx|f(,)=0,79,扩张次数,证明思路：考虑将扩域上的元素看做是向量空间的元素，并且可由一组线性无关的基线性表出，再由基的线性无关性构造出,M,在,K,上向量空间的一组基。,80,代数扩张,证明思路：,1,）构造同态映射，使其核为,(g);,2,）利用线性无关的定义,81,定理,1.4.5,的证明,82,证明思路：构造域,L=Kx/f(x),，将扩域上的元素表示成为,K,上的模（,f(x),）的剩余类。,83,代数闭域和分裂域,84,证明思路：根据分裂域的定义,85,本章重点和难点,群、环、域的概念和相互之间的关系,正规子群和理想以及商群和剩余类环的概念、性质,同态基本定理,多项式环中的运算,86,习题,87,