有限域

有限域(FiniteFields)信息安全实验室参考书目•《代数与编码》万哲先，科学出版社出版，华中科技大学出版社影印。•《有限域》冯克勤，走向数学丛书，湖南教育出版社。•《近世代数》熊全淹，武汉大学出版社。一、域的基本性质1.0有限域的起源•17世纪起，费尔马(Fermat,1601-1665)、欧拉(Euler,1707-1783),勒让德(Legendre,1752-1833)和高斯(Gauss,1777-1855)等大数学家研究数论得到了同余式的许多性质，实质上也就研究了p元有限域的许多性质。•第一个明确讨论任意有限域的是法国年青数学家伽罗华(Galois,1811-1832),1828年《关于五次方程的代数解法问题》，产生群的概念，1830年《关于数论》在p元有限域的基础上，利用扩张方法构造了全部可能的有限域。所以有限域通常也叫伽罗华域。•1901年，狄柯逊(Dickson)，《线性群和伽罗华域理论》，将域表示成现在的形式。1.1域的定义1()aba+bababab定义（域）:设是一个非空集合,并且在上规定了两种运算,分别叫做加法和乘法,记作＋和,对于中的任意两个元素和,与通常简记作均是中的元素(对于加法和乘法自封闭),分别叫做和的和与积.我们称对于所规定的加法和乘法是一个,如果以下运算规则成立:域FFFFFFI.1,;()I.2,()();()I.3,0,0,;()I.4,,()0;()a,ba+b=b+aa,b,ca+b+c=a+b+ca+aaa-aa+-a=对任意有加法交换律对任意有加法结合律中有一个元素把它记作具有性质:=对于一切零元对任意,中有一个元素把它记作具有性质:负元FFFF;FF11II.1,;()II.2,()();()II.3,0,,,;()II.40,,;()a,bab=baa,b,cabc=abceae=aaaaaae对任意有乘法交换律对任意有乘法结合律中有一个元素把它记作具有性质:对于一切a单位元对任意,中有一个元素把它记作具有性质:=逆元FFFF;FFIII.,().()a,b,cab+c=ab+ac对任意有乘法对加法的分配律F定义1的理解：•对于加法和乘法是自封闭的.•一个域至少有两个元素0与e.•所有元素对于加法形成交换群,所有非零元素对于乘法形成交换群.•说一个集合是域的时候，除了要指明集合本身以外，还要指明定义在该集合上的加法和乘法.33331.2.[2]{2|,}3.[-2]={-2|,}4.Z={0,1,2,...,-1},,1..(1)2.{+2|,}.(4=22,)3.Z={0,1,2,...pmababababppabab域的例子：有理数域，实数域，复数域为素数模加、模乘不是域的例子：全体整数的集合除外均没有逆集合对于乘法不封闭,例如只需证明2不是有理数的立方QRRZ.QQRCQ,-1},,mmm为合数模加、模乘.(的非平凡因子没有逆)00002(,):,.,,.定义子域扩域设是一个域而是的一个非空子集如果对于中的加法运算和乘法运算来说是一个域我们就称是的而称是的例如：扩FFFFFFFFFQRC子域域判断子域只需验证：1.对于加法和乘法是自封闭的.2.I.3和I.43.II.3和II.43():,,(Galo,is).无定义无限域与有限域设是域如果的元素个数无限就叫否则就叫或者罗FFF限域有限域伽瓦域1.2域的运算规则-11.,1)0;2);3),4)0,ea-aaaa定理设是任意一个域那么：零元是唯一的单位元是唯一的对于任意是唯一的；对于任意而是唯一的.FFF1112.,1).,,,,(())()()()()(()).2).,,,c0,,()()()(abcacbcabaaccaccbccbccbabcacbcabaaeaccaccbccbc定理设是任意一个域那么以下运算规则成立：加法消去率设是中任意三个元素如果+=+那么一定有=.证：乘法消去率设是中任意三个元素而如果=那么一定有=.证：FFF1-1).3),0=0.000(00)00,1)0=0.4),,0,000,0,3)0.cbebaaaaaaaaabababaabab对于任意证：根据可得设如果那么一定有或者.证：如果在两边同时乘以根据得FF00000000000000000-1-111,.,0.000.0,000.0000..2,0,0.0,00,aaaaeaaa系理设是个域而是的一个子域那么的零元和单位元一定都属于而且分别就是的零元和单位元.证：设0是的零元，是的零元因为，所以0=又因为所以=由此，0=，所以0=同样的方法可以证明单位元系理设是个域而那么证：假定那么与域的定FFFFFFFFFFFFa义不符.3.,1)-(-)=,2)-(+)=(-)+(-),,+)(-)+(-)=0)3)(-)=(-)=-(),,.((-)+00,(-)00)4)(-)(-)=,,3aaaaaabababababababababababaababbababab定理设是任意一个域那么以下运算规则成立：对任意.((-)+=0)对任意.((对任意对任意.(由)和1)有FFFFF-1-1-1-1-1-1-1-1-1-1-1-1(-)(-)=(-(-)))5)()=,0.()6)()=,,0,0.(=)7)(-)=-,0.(4),(-)(-)=)abababaaaaaaeababababababeaaaaaaaae对任意而对任意而对任意而由FFF1.3二项式定理1=10--1-1,,,,1)-=+(-).2)=,1.3)0=0.4)(-)=-().5)=,1.6)=,0.7)=()=(),0.ninninnnabnababnaanananaaanaeaaaaa记号：设是任意一个域为任意正整数那么我们记：对于对于FF+=01,,,,,1)(+)=+,()=().2)(+)=+.3)()()=()().4)=.=0,0.5)()=.=0=00.6)0,(+)=.1mnmnmmmnnin-iiabmnmnamanamnamnanabnanbmanbmnabaaaamnabababmnnababimn定理设是任意域我们有：当时，要求都当或时，要求如果证：）或者中至少有一个FFZ0,0;0,0;||||0,0,0||||||||mnmnmnmnmnmnmn为零；不妨设练习1331371.(1){+i|,},i=1.(2){+i|,}.(3){+2+4|,,}.2.,,(1)=0,=0;(2)=,=;(3)=0,=0.3.Z723.nnabababababcabcannaaaeaeaa－下列集合哪些是复数域的子域：设为域为正整数，下列命题是否正确，为什么？如果则如果则如果则在中计算CZQQFF有限域二、多项式和有理分式本章内容•多项式和有理分式（4学时）–域上的多项式的定义和计算–带余除法–唯一因式分解定理–余元定理–多项式的根–域的扩张–域上有理分式的定义和计算2.1域上的多项式的定义和计算0120120120120121:,(),,,(),,,,...,(,,,...,)...,iiinnnnnxiaxaxaxaxaxaxnaaaaaxaxaxaxxx定义设是一个域而是一个符号或称文字设是个非负整数则形如的式子，叫做系数属于的符号的而有限个系数属于的单项式其中是任意非负整数而的形式和＋＋＋＋就叫做系数属于的的或简称单项式多域上的多项式式.项FFFFFFF01201200()...,(),()0,.0,(),()=,().()0,(),0,0=-.niniinnfxaxaxaxaxaxfxafxafxfxnafxfxfixin设=＋＋＋＋,其中叫做的叫做的.两个多项式是指除去系数等于域中的的项以外它们同次项的系数都相等如果我们就说为记作并说是的当的所有系数都是时我们就说是仍用来代表它并规次项次项系数相等次多项式首项系数零定＊式多项式零多项F与零次多项式的区别001002012=0:[].=,=,,.()==+++...+.iinininixxxeaxaxxexxfxaxaaxaxax记号表示域上的多项式的全体所组成的集合简记作简记作FFFF多项式的加法=0=0+1+2+1+2=0=0=0(),()[],()=,()=,=max(,),==...==0,,==...==0,.()=,()=.()+()=(+).nmiiiiiinnMnnMMMiiiiiiMiiiifxgxxfxaxgxbxMnmaaanMbbbmMfxaxgxbxfxgxabx设并且令置如果如果则有：定义F多项式的乘法=0=0+1+2+1+2=0=0-=0=0(),()[],()=,()=,=+,==...==0,1,==...==0,1.()=,()=.().()=().nmiiiiiinnMnnMMMiiiiiiMiijijijfxgxxfxaxgxbxMnmaaambbbnfxaxgxbxfxgxabx设并且令置如果如果则有：定义F000000(),()[],(()+())max((),())[](().())=()+?()[]..fxgxxfxgxfxgxfxgxfxgxx设有由此可推导出：中的元素对于所定义的加法和乘法不能成为域本章将利用域上的多项多项式求式，通过和余有理分的什么时候成方法来域式立构造FF2.2带余除法00001()()()[],()0.,[]()():()=()()+(),()()...............(1)1.().():()()axbxxbxxqxrxaxqxbxrxrxbxaxaxbx定理带余除法设和是中的两个多项式而那么中有唯一的一对多项式和具有下面的性质证明：对的次数利用数学归纳法证明存在性归纳基础初始条件时结论成立.[FF0000():():()(),()2..00.(1),()()(),()()().()=(()).bxaxnaxnnbxnbxqxbxaxrxbxaxrxax]归纳假设假设时结论成立归纳证明＝时结论成立，分两种情况唯一性次数小于的多项式为带余多项式式叫做叫做用做去除所得的而叫做用去除所除法算式除式被除式商注意归纳基础的存在性记式的余得我们1212()1()2()12()1()2()()12(()()()[],()0.,(()())=(())(())(()())=((())(())).()(=1,2,...,):(()()...())bxbxbxbxbxbxbxinbxaxaxbxxbxaxaxaxaxaxaxaxaxnaxinaxaxax系理设、和都是中的多项式而那么该系理也可推广到个多项式的和与积的情形，即F)1()2()()12()1()2()()()=(())(())...(())(()()...())=((())(())...(())).bxbxnbxnbxbxbxnbxbxaxaxaxaxaxaxaxaxax带余除法的例子5422232542335324423321=,[]()=+++1,()=++1,:++1+++1++1++++1+++++1++1xaxxxxbxxxxxxxxxxxxxxxxxxxxxxx例设在中取列竖式如下F=ZZ2542232+++1=(++1)(++1)+.xxxxxxxxx所以带余除法的例子5423332542335324423322=,[]()=+++1,()=++1,:++2+++1++1++++1++2+++12222xaxxxxbxxxxxxxxxxxxxxxxxxxxxx例设在中取列竖式如下F=ZZ2542232+2+22+2+++1=(++