第2章近世代数PPT讲稿.ppt

《第2章近世代数PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第2章近世代数PPT讲稿.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章近世代数2022/10/11天津大学电子信息工程学院1第1页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院22.1 2.1 几个概念几个概念1.质数（素数）质数（素数）一个大于一个大于1 1的正整数的正整数，只能被1和它本身整除。2.合数合数一个一个大于大于1 1的正整数的正整数，除了能被1和本身整除以外，还能被其他的正整数整除。例例2-12-12，3，5，7，9，11，13，17，19都是质数；4，6，8，9，10，都是合数；这样，全体正整数又分为：全体素数和全体合数。第2页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学

2、院33.3.群群(Group)(Group)设G是非空集合(set)，并在G内定义了一种代数运算(operation)“。”，若满足下述公理：（1）具有封闭性(is closed)；（2）结合率 成立(is associative)；（3）G中有一个恒等元e 存在(exist an identity element)；（4）有逆元 存在(contain an inverse element)。称称G G构成一个群构成一个群。第3页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院4（1）加群(addition group)、乘群(multiplication gr

3、oup)（针对群中的运算）（2）群的阶（针对群中元素的个数）（3）有限群(finite group)、无限群(infinite group)（针对群中元素的个数）（4）交换群(commutative group)或阿贝尔群(Abel group)（针对群中的运算）第4页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院5例例2-22-2G1：整数全体。对加法构成群对加法构成群，无限加群；对乘法不够成群对乘法不够成群。Why?G2：实数全体。对加法构成群；除0元素之外的全体实数，对乘法构成群。单位元e=1。这两个群都是无限群。G1和G2有都是阿贝尔群阿贝尔群。群群将

4、将 和和 联系在一起？联系在一起？第5页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院64.4.域域(Field)(Field)对于非空元素集合F F，若在F中定义了加法(addition)和乘法(multiplication)两种运算，且满足下面的公理：（1）F关于加法构成阿贝尔群阿贝尔群，其加法恒等加法恒等元元记为0；（2）F中非非0 0元素全体元素全体对乘法构成阿贝尔群，其乘法恒等元（单位元）乘法恒等元（单位元）记为1。（3）加法和乘法之间满足如下分配率(distributive)：则则称称F F是一个域是一个域。第6页，共58页，编辑于2022年，星期

5、一2022/10/11天津大学电子信息工程学院7（1）域的阶（针对群中元素的个数），记为q。（2）有限域或伽逻华（Galois）域，表示为：GF(q)GF(q)。域域将将 和和 联系在一起？联系在一起？第7页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院8例例2-32-3F1：有理数全体、实数全体对加法和乘法都分别构成域，分别称为有理数域和实数域。F2：0、1两个元素模2加构成域；由于该域中只有两个元素，记为GF(2)。第8页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院9定理：定理：设p为质数，则整数全体关于p模的剩余类：0

6、，1，2，p-1，在模p的运算下（p模相加和相乘），构成p p阶有限域阶有限域GF(p)GF(p)。例例2-42-4 验证以p=3为模的剩余类全体：0，1，2构成一个有限域GF(3)。+012001211202201012000010122021第9页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院10分析：是否构成域？分析：是否构成域？A.A.对对加法加法是否构成群？除是否构成群？除0 0之外对之外对乘法乘法是否构成群？是否构成群？（1）对两种运算满足封闭性，即有a。b G；（2）满足结合率，即有(a。b)。c=a。（。（b。c）；）；（3）有恒等元（加法为0

7、，乘法为1）；（4）有逆元。即对任意a G，存在有a的逆元a-1 G，使 a。a-1=a-1。a=e。第10页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院11B.B.是否为阿贝尔群？是否为阿贝尔群？是否可交换：a。b=b。a（满足乘法、加法交换率）C.C.是否满足分配率？是否满足分配率？第11页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院125.5.循环群循环群如果一个元素一个元素 的各次幂幂 0，1，2，的全体构成了一个群，称为循环群循环群（cycle group），），元素称为生成元生成元或者本原元本原元（primit

8、ive element）。记作：G=0，1，2，其中 0=e 是单位元。可以证明，有限域GF(q)的q-1q-1个非个非0 0元素元素，在模模q q乘运算下乘运算下，可以构成一个循环群（幂群），即G上的所有非0元素可以由一个元素的各次次幂幂 0，1，2，q-1生成生成。第12页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院13例例2-52-5 q=5 的伽逻华域GF(5)=0,1,2,3,4，由5个域元素组成，其中非零元素为1,2,3,4，进行模5乘运算。为了弄清那些元素是为了弄清那些元素是本原元本原元，分别计算各元素的各次幂。由本原元可以产生所有的域元素。第

9、13页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院14GF(5)中非零元素的幂零元素的幂、阶及其逆元阶及其逆元元素各 次 幂元素的阶加法逆元乘法逆元01231111114121243（8）4333134（9）2（27）4224141（16）4（64）214（1）元素的阶（能产生域元素的个数）：（2）域元素2和3的各次幂可以生成全部非零域元素，所以2和3都是本原元。（3）元素1的各次幂只能生成元素1（阶为1），4只能生成元素1和4（阶为2），故都不是本原元（生成元）。第14页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院156

10、.6.环（环（RingRing）定义：在非空集合R中，若定义了两种代数运算加和乘，且满足：（1）集合R在加法运算下构成阿贝尔群；（2）乘法有封闭性，对于任何a,bR，有ab R；（3）乘法结合率成立，且加法和乘法之间分配率成立，即对任何a,bR，有a(b+c)=ab+ac (b+c)a=ba+ca则称称R R是一个环是一个环。第15页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院16环环将将 和和 联系在一起？联系在一起？What is the relationship with Group,Field and Ring?What is the differe

11、nce between Field and Ring?第16页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院177.7.同余和剩余类同余和剩余类定义：若两个整数a、b能被同一整数被同一整数m整除整除，余数相同余数相同，即则称a、b关于模m同余，记为由同余的概念，可以将全体整数加以分类，把余数相同的归成一类，即由共有m个剩余类。一般地讲，若模数为m，则全体整数可以按照模m划分成m类，0，1，m-1，或用0，1，2,，m-1表示，称这样的一组数为模m的剩余类。第17页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院18例例2-62-

12、6如果取m=7，则对全体整数，可如下划分：剩余类的加法和乘法运算第18页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院192.2 2.2 多项式剩余类环和域多项式剩余类环和域1.1.域上多项式的定义域上多项式的定义多项式与码字的关系：桥梁；多项式的系数表示 ；x的幂次表示 ；域上的多项式针对系数定义；例如二进制系数多项式，称为二元域GF(2)上的多项式。q进制系数的多项式，称为q元域GF(q)上的多项式。群、环、域对多项式也成立。第19页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院20域上多项式：域上多项式：GF(q)GF(

13、q)上上多项式的定义：第20页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院21(1)多项式的两要素多项式的两要素(2)多项式次数多项式次数(3)首一多项式首一多项式(4)最简首一多项式最简首一多项式(5)多项式的有限性分析多项式的有限性分析第21页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院222.2.多项式剩余类环存在定理多项式剩余类环存在定理若以有限 域域GF(q)GF(q)上上 多项式多项式为模做乘法运算，为模做乘法运算，q q为模做加运算为模做加运算，得到的多项式剩余类多项式剩余类的全体，可以构成一个交换环，称为多

14、项式剩余类环，记为多项式剩余类环，记为Rq(x)f(x)。多项式剩余类环的有限性有限性可以得到保证。系数有限性幂次的有限性第22页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院23系数模q加和模模f(x)f(x)乘运算：A(x)、B(x)是两个环元素，模q加模 f(x)乘第23页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院24多项式 f(x)的最高次幂为m，有限域为GF(q)。多项式剩余环类Rq(x)f(x)中 环元素环元素的最高次数最高次数为 ；多项式的一般形式一般形式为：这个环这个环中共有中共有 个元素？个元素？第24页

15、，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院25例例2-72-7剩余类环为Rq(x)f(x)，q=2，f(x)=x3+x+1。若A(x)=x2+x+1，B(x)=x2+1是两个多项式多项式。求A(x)B(x)构成的剩余类环最多有多少个元素？解：（1）一般多项式乘法运算）一般多项式乘法运算第25页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院26（2）用f(x)除上面的多项式，有第26页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院27得到得到，A(x)B(x)modf(x)=x2+x。由于f

16、(x)f(x)是3次多项式，因此该剩余类环的最高次幂不会超过2，一般形式由下式给出：由于环元素只有由于环元素只有3 3个系数个系数，最多的，最多的不同组合不同组合有有8 8种种，因此该剩余类环最多只有只有8 8个环元素个环元素（包括多项式和常数）（包括多项式和常数）。第27页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院282.3 2.3 多项式域和循环群多项式域和循环群1.1.既约多项式（既约多项式（Irreducible polynomials）定义定义：设 Pl(x)是次数大于0的多项式。如果除常数C和C Pl(x)之外，不能被域GF(q)上的其它多项式

17、整除，则称 f(x)是域GF(q)上的既约多项式既约多项式。第28页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院29(1)常数常数总是多项式的因子总是多项式的因子。(2)一个多项式一个多项式 f(x)是否为既约多项式与是否为既约多项式与所定义的所定义的域域有关。有关。(3)一个多项式一个多项式既约的充要条件既约的充要条件：多项式：多项式Pl(x)不能分解成两个次数低于不能分解成两个次数低于Pl(x)的多项的多项式的乘积。式的乘积。(4)完全分解完全分解：n次多项式最多能分解成次多项式最多能分解成n个个一次多项式一次多项式的乘积，被称为完全分解。的乘积，被称为

18、完全分解。(5)一次多项式一次多项式一定是既约的。一定是既约的。第29页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院302.本原多项式（本原多项式（Primary Polynomials）定义：对于有限域GF(q)上的m次既约多项式P(x)，若能被它整除的最简首一多项式最简首一多项式（xn-1）的次数为：则称这个多项式P(x)为本原多项式本原多项式。本原多项式一定是既约的；但既约多项式未必是本原的。第30页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院313.多项式循环群（多项式循环群（Cycle Group）定义定义：群内

19、的：群内的所有元素所有元素由由多项式多项式 的各次幂的各次幂构成，称为多项式循环群构成，称为多项式循环群。多项式多项式 是一个群元素，被称为循环群的生成元。例例2-82-8，1，1，2，3，4，5，构成无限循环群；若7=1，以1，1，2，3，4，5，6为周期，则称0=1，1，2，3，4，5，6为 7 7阶阶 有限循环群有限循环群。第31页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院32域存在定理域存在定理定理定理2.1若f(x)是有限域GF(q)上的m次既约次既约多项式，则GF(q)域上次数小于m的多项式的全体，在模在模q加、模加、模f(x)乘乘运算下构成一

20、个qm 阶阶有限域。有限域。称其为其为 是GF(q)的扩展域扩展域（Extension Field），记为GF(qm)。称GF(q)是GF(qm)的基域基域。第32页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院33例例2-92-9二元域GF(2)上，模2加、模x2+x+1(m=2)乘运算下构成一个扩展域扩展域：GF(22)=0,1,x,x+1，基域基域：GF(2)=0,1第33页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院34基域基域GF(q)是数域数域，有q个个域元素；扩展域扩展域GF(qm)则是多项式域多项式域，有qm

21、个个域元素；m m 个个 基域的元素对应扩展域的一个一个元素：扩展域GF(22)的元素01xx+1m(2)个域GF(2)的元素00011011第34页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院35循环群存在定理循环群存在定理定理定理2.22.2若P(x)是GF(q)上m次次本原多项式本原多项式，则GF(qm)域上幂次小于m的非0多项式的全体（共有qm-1个），在模q加、模P(x)乘运算下形成一个多项式循环多项式循环群群。在扩展域GF(qm)里，至少存在一个本原元，其各次幂能构成扩展域GF(qm)的全部非0的域元素。第35页，共58页，编辑于2022年，星期

22、一2022/10/11天津大学电子信息工程学院36总总 结结GF(q)GF(q)上多项式上多项式若为：（1）一般一般多项式多项式 f(x)，构成qm阶 。（2）既约既约多项式 Pl(x)，构成qm阶 。（3）本原本原多项式 P(x)，构成qm-1阶 。对多项式的限制越多，扩展域具备的性质也就越多。如何找到构成循环群的生成元？第36页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院372.4 2.4 循环群的生成元循环群的生成元定理定理2.32.3GF(q)上的m次本原多项式本原多项式P(x)的根根，一定是扩展域GF(qm)上的本原元本原元。证明：证明：第37页，

23、共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院38构成循环群的步骤：构成循环群的步骤：找到GF(q)上的一个m次本原多项式；取其根，并计算的各次幂得到扩展域的所有非0元素，即循环群。第38页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院392.5 2.5 域元素的性质域元素的性质本原元本原元，用用 表示，表示，各次幂可以生成扩展域GF(qm)中全部全部q qm m-1-1个非个非0 0域元素域元素；非本原元非本原元，用用 表示，表示，只能生成部分部分域元素。下面的定理回答：下面的定理回答：什么样的域元素是本原？什么样的域元素是非

24、本原？对于非本原的元素，它们的阶又是多少？第39页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院40定理定理2.42.4扩展域扩展域GF(qm)上的非零元素k 的阶阶一定是qm-1的因子，其值为：GCD表示最大公约数最大公约数（Greatest Common Divisor）。第40页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院41如果 n=qm-1，本原元；如果 n qm-1，非本原元，n 一定是qm-1的一个因子，一定能够整除qm-1。推论推论2-42-4在循环群中，n 阶域元素的n n次幂次幂恒等于1。证明：证明：第4

25、1页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院42例例2-102-10 P(x)=x4+x+1是GF(2)上的本原多项式，试用本原元的各次幂生成二元扩展域GF(24)的全部域元素全部域元素，并计算域元素的阶。解：解：第42页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院43各次幂k的多项式多项式的系数m重元素的阶15/GCD(k,15)01（0001）11（0010）1522（0100）1533（1000）54+1（0011）1552+（0110）363+2（1100）573+1（1011）15用本原多项式P(x)=x4+

26、x+1生成的循环群第43页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院44各次幂k的多项式多项式的系数m重元素的阶15/GCD(k,15)82+1（0101）1593+（1010）5102+1（0111）3113+2+（1110）15123+2+1（1111）5133+2+1（1101）15143+1（1001）15第44页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院45结论：结论：（1）本原元不是唯一的，共有8个本原元。（2）不是所有的元素都是本原元。（3）以 7 为例，可以生成15个域元素。第45页，共58页，编辑于2

27、022年，星期一2022/10/11天津大学电子信息工程学院462.6 2.6 域元素、根、最小多项式的关系域元素、根、最小多项式的关系定理定理2.52.5 扩展域GF(qm)上的所有非零域元素0，1，2，qm-2 都是GF(q)上多项式 的根，即 可完全分解为一次项的乘积。有，证明：证明：第46页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院47定理2.6扩展域GF(qm)上域元素和的q l次幂等于元素q l次幂的和，即有：i是域元素。第47页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院48定理定理2.72.7如果 是是G

28、F(q)上的p次次多项式f(x)的根根，那么 的的q l(li=1,2,l p)次幂也一定是 f(x)的根根。即：如果 是是f(x)的根的根，那么 也一定是也一定是f f(x x)的根的根；p是多项式的次数，l是小于小于p的数。证明：证明：第48页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院49费尔马费尔马(Fermat)(Fermat)定理定理：由定理2-5，GF(qm)上的任意一个域元素域元素 一定是所以有，第49页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院50由定理由定理2-7：共轭元具有相同的基底共轭元具有相同的

29、基底 q(是一个域元素，是一个域元素，q是基是基域的阶域的阶)，费马定理限制了共轭根系的个数，费马定理限制了共轭根系的个数（共有（共有m个）个）。第50页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院51根据费尔马定理，共轭元可构成循环共轭元可构成循环：一个多项式的根，可以来自多个不同的根系；如果一个多项式多项式的所有根所有根来自同一个基底为的根系，称这样的多项式为 的最小多项式的最小多项式；最小多项式在在GF(q)中一定是既约一定是既约的，本原本原元元共轭根系对应的最小多项式的次数等于最小多项式的次数等于m m。第51页，共58页，编辑于2022年，星期一2

30、022/10/11天津大学电子信息工程学院52定理2.8：GF(q)上的多项式 一定可以分解成若干个最小多项式之积，即有，li次最小多项式必然有同一个根系的同一个根系的li个个共轭元作为根(这里q=2)，其中li不会超过不会超过m m，所以，所以 i(x)=li m 。第52页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院53综合定理2.5，有上式说明，在 的qm个根中，所有 的根都来自不同的k个共轭根系。下面的例子，说明了共轭元、最小多项式和多项式 之间的关系。第53页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院54例例2

31、-11 找出由本原多项式 P(x)=x4+x+1生成的二元扩展域GF(24)上各非零元素的共轭元，并计算与这些共轭元对应的最小多最小多项式项式。解：解：第54页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院55各次幂k的多项式多项式的系数m重元素的阶15/GCD(k,15)01（0001）11（0010）1522（0100）1533（1000）54+1（0011）1552+（0110）363+2（1100）573+1（1011）15用本原多项式P(x)=x4+x+1生成的循环群第55页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程

32、学院56各次幂k的多项式多项式的系数m重元素的阶15/GCD(k,15)82+1（0101）1593+（1010）5102+1（0111）3113+2+（1110）15123+2+1（1111）5133+2+1（1101）15143+1（1001）15第56页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院57共轭元及对应的最小多项式共轭元最小多项式元素阶01(x)=x+111 2 482(x)=x4+x+1153 6 9 123(x)=x4+x3+x2+x+155 104(x)=x2+x+137 11 13 145(x)=x4+x3+115第57页，共58页，编辑于2022年，星期一2022/10/11天津大学电子信息工程学院58根据定理根据定理2-82-8第58页，共58页，编辑于2022年，星期一