有限域PPT学习课件

有限域及其应用,聂旭云xynie,1,教师简介,聂旭云研究方向：密码学，公钥密码算法，密码学相关代数理论,2,教学目的,掌握有限域的基本理论和基本方法,熟悉有限域的结构了解有限域与多项式的关系,熟悉不可约多项式与多项式的分解掌握有限域的应用与方法,能用基本的有限域理论解决和回答一些应用问题,如编码理论和密码理论中的有限域应用。,3,基本学习方法,紧扣定义，从定义出发，理解相关定理、性质掌握各种代数结构的性质及相互之间的关系,4,考核方式,平时：40%，主要评价来源：考勤、课外作业期末考试：60%,5,参考教材,教材：FiniteFields,RudolfLidl,Addison-WesleyPublishingCompany，1997.参考书：代数学基础与有限域.林东岱编著，高等教育出版社.代数和编码（第三版），万哲先，高等教育出版社，2007。Groebner基理论及其应用，刘木兰，科学出版社，2000。,6,7,教学内容,第一章代数学基础（4学时）1.1群1.2环与理想1.3多项式环1.4域和扩域第二章有限域的结构（8学时）2.1有限域的特征性质2.2不可约多项式的根2.3迹，范数和基2.4单位根和割圆多项式2.5有限域元素的表示第三章有限域上的多项式（8学时）3.1多项式的阶和本原多项式3.2不可约多项式3.3不可约多项式的构造3.4有限域上多项式因式分解,8,教学内容（续）,第四章Grbner基理论（6学时）4.1项序的定义和分类4.2多项式的除法算法4.3域上的Grbner基定义及其计算方法4.4域上的既约Grbner基定义及其相关性质第五章有限域上的离散对数问题（4学时）5.1有限域上的离散对数问题5.2Shanks算法5.3Pohlig-Heliman算法5.4Pollardp方法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,cFa+b=b+a；交换律(a+b)+c=a+(b+c)；结合律存在0F，使得a+0=a；有零元存在-aF，使得a+(-a)=0；有负元,12,什么是域？（续）,乘法满足：对于任意a,b,cFab=ba；交换律(ab)c=a(bc)；结合律存在eF，使得ae=a；有单位元存在a-1F，使得aa-1=e；有逆元乘法对加法满足分配率a(b+c)=ab+ac,13,域的例子,Q，R，C,14,群,什么是群？集合定义一个二元运算二元运算满足封闭性、结合律有单位元有逆元若满足交换律，则称为交换群，此时群中运算可认为是加法，也称为加群,15,域的定义简化,F是一个非空集合，定义了加法、乘法两个二元运算，对这两个运算封闭对于加法构成交换群对于乘法构成交换群乘法对加法满足分配率,16,群的例子,Z，+数域K中全体n阶可逆矩阵对于矩阵的乘法构成群称为n级一般线形群，记为GLn(K);GLn(K)中全体行列式为1的矩阵对于矩阵的乘法也构成群，称为特殊线形群，记为SLn(K)。,17,环,集合集合+加法+乘法加法交换群乘法满足结合律加法和乘法满足分配率环中乘法不一定有单位元也不一定要满足交换律满足乘法交换律的环称为交换环,18,环的例子,全体有理数、全体实数、全体复数和全体整数集合对于普通的加法和乘法构成交换环Z,+,nn可逆矩阵,乘法,加法?nn矩阵,乘法,加法,19,域,有单位元的交换环非零元构成乘法交换群,20,群的阶、子群,定义如果一个群G中元素的个数是无限多个，则称G是无限群；如果G中的元素个数是有限多个，则称G是有限群，G中元素的个数称为群的阶，记为|G|,子群：群G的非空子集H称为G的子群，如果对于G的运算，H本身成一个群。如果H为G的子群且HG，则H称为G的一个真子群。,21,元素的幂,由于群里结合律是满足的，所以元素连乘a1，a2，an有意义，它也是G中的一个元我们把a的n次连乘记为an，称为a的n次幂（或称乘方），即我们还将a的逆元a1的n次幂记为an，即群的逆元（a1）1=a,22,元素的阶,元素的阶设G为群，aG，如果存在整数t，使得at=1，则这样的最小正整数t定义为a的阶，记为o(a)。如果这样的t不存在，则a的阶定义为。定理：o(a)=m，an=1当且仅当m|n。证明思路：充分性显然。必要性围绕着m为最小正整数来证明。,23,循环群,循环群：群G称为是循环的，如果存在元素g，使得对任一hG都有一个整数i，使得h=gi，这样的元素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的正规子群，记为HG。商群：如果群G的子群H是正规子群，则模H的陪集集合在运算(aH)(bH)=(ab)H下构成一个群，称为G关于H的商群，记为G/H.,27,例子（从群的角度）,整数集Z：加群nZ，子群，正规子群陪集a+nZ商群Zn=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=gnn称为h（相对于生成元g）的离散对数，记为n=g(h),34,离散对数的例子,例1：（Z，+）离散对数问题是平凡的例2：Zn，模n剩余类组成的加法群，g为Zn的一个生成元，离散对数问题为：给定hZn，求解x，使得xghmodn用扩展的欧几里得算法很容易求解。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的核定义为kerf=aG|f(a)=1H，其中1H是H中的单位元。,36,内自同构和共轭元,37,群同态基本定理,定理：设f：GH是群G到群H上的满同态映射，那么kerf是群的一个正规子群，而且H同构于商群G/kerf，即G/kerfH。反之，如果N是G的正规子群，则映射是G到G/N的满同态，且ker=N证明思路：紧扣正规子群和同态的定义,38,子环与理想,子环：环R的一个子集S称为R的子环，如果S关于环中的两种运算封闭并且在这两种运算之下形成一个环。理想：环R的一个子环J成为一个理想，如果对于任意aJ，rR，有arJ和raJ。剩余类环：设R是一个交换环，而I是R的一个理想，记R/I=a=a+I|aR按照陪集的运算，R/I构成一个环，称为R模I的剩余类环或商环。,39,例子（从环的角度）,整数集Z：环nZ，子环，理想Zn：剩余类环Zn中的乘法可逆元a|(a,n)=1,40,整环、除环,一个环称为整环，如果它是一个有单位元的交换环且无零因子。一个环称为除环，如果所有的非零元在乘法运算下构成群。,41,域的定义,交换除环称为域,42,定理：有限整环是域。证明思路：根据域的定义，只需要证明每一个非零元都有逆元即可。,43,环同态,44,主理想与主理想整环,定义设X是环R的非空子集，I1，I2，是包含X的所有理想，则称它们的交是由X生成的理想，记为(X)X中的元素称为(X)的生成元素当X是有限集时，称(X)是有限生成理想由一个元素生成的理想(a)称为主理想定义如果一个整环上的理想都是主理想，则称为主理想整环,45,商环、素理想和极大理想,定义设I是具有单位元的交换环R的一个理想，IR如果abI，总有aI或bI，则称I是R的一个素理想如果不存在另一个理想A(AR)，使IA，则称I是R的一个极大理想,46,商环、素理想和极大理想,例整数环Z内由素数p生成的理想(p)是一个素理想，同时也是一个极大理想证明Z内由素数p生成的理想(p)=mpmZ如果ab(p)，则pab，于是pa或pb，所以a(p)或b(p)，(p)是一个素理想如果存在一个理想(n)使(p)(n)R，则np，由于p是素数，则有n=1或n=pn=1时(n)=Z，n=p时(n)=(p)，故(p)是极大理想,47,48,49,50,51,有限域,Zn中若所有非零元构成交换群，则Zn为域所有与n互素的元素构成交换群1n-1都与n互素，则n为素数对于任一素数p，Zp为域,52,Zp,Zp在模p的加法和乘法运算下是一个域证明一：直接验证Zp满足域的定义证明二：证明Zp是整环，有限整环是域证明三：Zp=Z/(p)，Z是主理想整环。,53,环的特征,定理：F是任意一域，那么F的特征或者是0或者是素数。推论：有限域的特征是素数。,54,习题,设p是一个素数，则阶为pm的群一定有一个阶为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,辗转相除法的例子,求Z2x中多项式x5+x4+x3+x2+x+1和x4+x2+x+1的最高公因式。,66,67,68,多项式的分解,定理（因式分解唯一定理）Fx上的多项式f(x)=anxn+an1xn1+a1x+a0可分解为f(x)=an，(k1，k2，kr0)其中p1(x)，pr(x)是两两不同的首一不可约多项式除p1(x)，pr(x)的排列次序外，上述分解是唯一的,69,多项式的分解,证明首先证明存在这样的分解如果f(x)不可约，则定理正确如果f(x)可约，则存在g(x)，h(x)，使f(x)=g(x)h(x)，其中0deg(g(x)，deg(h(x)deg(f(x)对g(x)，h(x)继续分解，一直可以把f(x)分解成互不相同的不可约多项式的幂的乘积,70,多项式的分解,再证这样的分解除排列次序外是唯一的设还存在另一分解：f(x)=an于是由上式知由于p1(x)是不可约多项式，则p1(x)整除右边某个不可约多项式不失一般性，设p1(x)q1(x)，由于p1(x)，q1(x)都不可约得p1(x)=cq1(x)(cF)，而p1(x)，q1(x)都是首一多项式，所以p1(x)=q1(x)等式两边分别约去p1(x)和q1(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)的下列映射00，11，1+12，很容易看出这是一个同构映射，因此S是一个p阶有限域,74,域的性质,定理1.4.21）素数p阶域的特征为p2）任何素数p阶域与GF(p)同构证明1）设素数p阶域F的特征为q则由引理，F含有一个与GF(q)同构的q阶素子域S，而又由定理1.4.1，F是素域，所以F=S，p=q2）由1和引理显然由于任何素数p阶域都与GF(p)同构，这样我们可以用GF(p)代表任意素数p阶域，并且将GF(p)中的元素简单记为0，1，2，p1,75,76,余数定理,77,余数定理（续）,78,极小多项式,证明思路：（1）利用g的极小性；（2）构造理想J=f(x)Kx|f()=0,79