近世代数课件

第2章近世代数简介线性分组码中最重要的一个子类---循环码(RS、BCH码)，它的结构完全建立在的基础之上，被称为代数几何码。有限域是以近世代数为基础。4/24/202312.1几个概念1.质数（素数）一个大于1的正整数，只能被1和它本身整除。2.合数一个大于1的正整数，除了能被1和本身整除以外，还能被其他的正整数整除。例2-12，3，5，7，9，11，13，17，19…都是质数；4，6，8，9，10，…都是合数；这样，全体正整数又分为：全体素数和全体合数。4/24/20232天津大学电子信息工程学院3.群(Group) 设G是非空集合(set)，并在G内定义了一种代数运算(operation)“。”，若满足下述公理：（1）具有封闭性(isclosed)；（2）结合率成立(isassociative)；（3）G中有一个恒等元e存在(existanidentityelement)；（4）有逆元存在

(containaninverseelement)。称G构成一个群。4/24/20233天津大学电子信息工程学院例2-2G1：整数全体。对加法构成群，无限加群；对乘法不够成群。Why?G2：实数全体。对加法构成群；除0元素之外的全体实数，对乘法构成群。单位元e=1。这两个群都是无限群。G1和G2有都是阿贝尔群。群将

和

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

（1）域的阶（针对群中元素的个数），记为q。（2）有限域或伽逻华（Galois）域，表示为：GF(q)。域将

和

联系在一起？4/24/20237天津大学电子信息工程学院定理：设p为质数，则整数全体关于p模的剩余类：0，1，2，…，p-1，在模p的运算下（p模相加和相乘），构成p阶有限域GF(p)。例2-4

验证以p=3为模的剩余类全体：0，1，2构成一个有限域GF(3)。

+012001211202201×0120000101220214/24/20239天津大学电子信息工程学院分析：是否构成域？对加法是否构成群？除0之外对乘法是否构成群？（1）对两种运算满足封闭性，即有a。bG；（2）满足结合率，即有(a。b)。c=a。（b。c）；（3）有恒等元（加法为0，乘法为1）； （4）有逆元。即对任意aG，存在有a的逆元a-1G，使a。a-1=a-1。a=e。

4/24/202310天津大学电子信息工程学院B.是否为阿贝尔群？是否可交换：a。b=b。a（满足乘法、加法交换率）C.是否满足分配率？4/24/202311天津大学电子信息工程学院例2-5

q=5的伽逻华域GF(5)={0,1,2,3,4}，由5个域元素组成，其中非零元素为1,2,3,4，进行模5乘运算。为了弄清那些元素是本原元，分别计算各元素的各次幂。由本原元可以产生所有的域元素。4/24/202313天津大学电子信息工程学院GF(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），故都不是本原元（生成元）。4/24/202314天津大学电子信息工程学院6.环（Ring）定义：在非空集合R中，若定义了两种代数运算加和乘，且满足：（1）集合R在加法运算下构成阿贝尔群；（2）乘法有封闭性，对于任何a,bR，有abR；（3）乘法结合率成立，且加法和乘法之间分配率成立，即对任何a,bR，有 a(b+c)=ab+ac (b+c)a=ba+ca则称R是一个环。4/24/202315天津大学电子信息工程学院7.同余和剩余类定义：若两个整数a、b能被同一整数m整除，余数相同，即则称a、b关于模m同余，记为由同余的概念，可以将全体整数加以分类，把余数相同的归成一类，即由共有m个剩余类。一般地讲，若模数为m，则全体整数可以按照模m划分成m类，0，1，…，m-1，或用{0}，{1}，{2},…，{m-1}表示，称这样的一组数为模m的剩余类。4/24/202317天津大学电子信息工程学院例2-6如果取m=7，则对全体整数，可如下划分：剩余类的加法和乘法运算4/24/202318天津大学电子信息工程学院2.2多项式剩余类环和域1.域上多项式的定义多项式与码字的关系：桥梁；多项式的系数表示

；x的幂次表示

；域上的多项式针对系数定义；例如二进制系数多项式，称为二元域GF(2)上的多项式。q进制系数的多项式，称为q元域GF(q)上的多项式。群、环、域对多项式也成立。4/24/202319天津大学电子信息工程学院(1)多项式的两要素(2)多项式次数(3)首一多项式(4)最简首一多项式(5)多项式的有限性分析4/24/202321天津大学电子信息工程学院2.多项式剩余类环存在定理若以有限域GF(q)上

多项式为模做乘法运算，q为模做加运算，得到的多项式剩余类的全体，可以构成一个交换环，称为多项式剩余类环，记为Rq(x)f(x)。多项式剩余类环的有限性可以得到保证。系数有限性幂次的有限性4/24/202322天津大学电子信息工程学院系数模q加和模f(x)乘运算：A(x)、B(x)是两个环元素，模q加模f(x)乘4/24/202323天津大学电子信息工程学院例2-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）一般多项式乘法运算4/24/202325天津大学电子信息工程学院（2）用f(x)除上面的多项式，有4/24/202326天津大学电子信息工程学院(1)常数总是多项式的因子。(2)一个多项式f(x)是否为既约多项式与所定义的域有关。(3)一个多项式既约的充要条件：多项式Pl(x)不能分解成两个次数低于Pl(x)的多项式的乘积。(4)

完全分解：n次多项式最多能分解成n个一次多项式的乘积，被称为完全分解。(5)一次多项式一定是既约的。4/24/202329天津大学电子信息工程学院2.本原多项式（PrimaryPolynomials）

定义：对于有限域GF(q)上的m次既约多项式P(x)，若能被它整除的最简首一多项式（xn-1）的次数为：则称这个多项式P(x)为本原多项式。本原多项式一定是既约的；但既约多项式未必是本原的。4/24/202330天津大学电子信息工程学院3.多项式循环群（CycleGroup）定义：群内的所有元素由多项式的各次幂构成，称为多项式循环群。多项式是一个群元素，被称为循环群的生成元。例2-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阶有限循环群。4/24/202331天津大学电子信息工程学院域存在定理定理2.1若f(x)是有限域GF(q)上的m次既约多项式，则GF(q)域上次数小于m的多项式的全体，在模q加、模f(x)乘运算下构成一个qm阶有限域。称其为是GF(q)的扩展域（ExtensionField），记为GF(qm)。称GF(q)是GF(qm)的基域。4/24/202332天津大学电子信息工程学院例2-9二元域GF(2)上，模2加、模x2+x+1(m=2)乘运算下构成一个扩展域：

GF(22)={0,1,x,x+1}，基域：GF(2)={0,1}4/24/202333天津大学电子信息工程学院基域GF(q)是数域，有q个域元素；扩展域GF(qm)则是多项式域，有qm个域元素；m个基域的元素对应扩展域的一个元素：扩展域GF(22)的元素01xx+1m(2)个域GF(2)的元素000110114/24/202334天津大学电子信息工程学院循环群存在定理定理2.2若P(x)是GF(q)上m次本原多项式，则GF(qm)域上幂次小于m的非0多项式的全体（共有qm-1个），在模q加、模P(x)乘运算下形成一个多项式循环群。在扩展域GF(qm)里，至少存在一个本原元，其各次幂能构成扩展域GF(qm)的全部非0的域元素。4/24/202335天津大学电子信息工程学院总结GF(q)上多项式若为：（1）一般多项式f

(x)，构成qm阶

。（2）既约多项式Pl(x)，构成qm阶

。（3）本原多项式P(x)，构成qm-1阶

。对多项式的限制越多，扩展域具备的性质也就越多。如何找到构成循环群的生成元？4/24/202336天津大学电子信息工程学院2.4循环群的生成元定理2.3GF(q)上的m次本原多项式P(x)的根，一定是扩展域GF(qm)上的本原元。证明： ……4/24/202337天津大学电子信息工程学院构成循环群的步骤：找到GF(q)上的一个m次本原多项式；取其根，并计算的各次幂得到扩展域的所有非0元素，即循环群。4/24/202338天津大学电子信息工程学院2.5域元素的性质本原元，用表示，各次幂可以生成扩展域GF(qm)中全部qm-1个非0域元素；非本原元，用表示，只能生成部分域元素。下面的定理回答：什么样的域元素是本原？什么样的域元素是非本原？对于非本原的元素，它们的阶又是多少？4/24/202339天津大学电子信息工程学院定理2.4扩展域GF(qm)上的非零元素{k

}的阶一定是qm-1的因子，其值为：GCD表示最大公约数（GreatestCommonDivisor）。4/24/202340天津大学电子信息工程学院如果n=qm-1，本原元；如果n<qm-1，非本原元，n一定是qm-1的一个因子，一定能够整除qm-1。推论2-4在循环群中，n阶域元素的n次幂恒等于1。证明：……4/24/202341天津大学电子信息工程学院例2-10P(x)=x4+x+1是GF(2)上的本原多项式，试用本原元的各次幂生成二元扩展域GF(24)的全部域元素，并计算域元素的阶。

解：……4/24/202342天津大学电子信息工程学院各次幂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生成的循环群4/24/202343天津大学电子信息工程学院各次幂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）154/24/202344天津大学电子信息工程学院结论：（1）本原元不是唯一的，共有8个本原元。（2）不是所有的元素都是本原元。（3）以

7为例，可以生成15个域元素。4/24/202345天津大学电子信息工程学院2.6域元素、根、最小多项式的关系定理2.5扩展域GF(qm)上的所有非零域元素0，1，2，…，qm-2都是GF(q)上多项式的根，即可完全分解为一次项的乘积。有，证明：……4/24/202346天津大学电子信息工程学院定理2.6扩展域GF(qm)上域元素和的ql次幂等于元素ql次幂的和，即有：

i是域元素。4/24/202347天津大学电子信息工程学院定理2.7如果是GF(q)上的p次多项式f(x)的根，那么的ql

(li

=1,2,…l

<p)次幂也一定是f(x)的根。即：如果是f(x)的根，那么也一定是f(x)的根；p是多项式的次数，l是小于p的数。证明：……4/24/202348天津大学电子信息工程学院费尔马(Fermat)定理：由定理2-5，GF(qm)上的任意一个域元素一定是所以有，4/24/202349天津大学电子信息工程学院由定理2-7：共轭元具有相同的基底q

(是一个域元素，q是基域的阶)，费马定理限制了共轭根系的个数（共有m个）。4/24/202350天津大学电子信息工程学院根据费尔马定理，共轭元可构成循环：一个多项式的根，可以来自多个不同的根系；如果一个多项式的所有根来自同一个基底为的根系，称这样的多项式为的最小多项式；最小多项式在GF(q)中一定是既约的，本原元共轭根系对应的最小多项式的次数等于m。4/24/202351天津大学电子信息工程学院定理2.8：GF(q)上的多项式一定可以分解成若干个最小多项式之积，即有，li次最小多项式必然有同一个根系的li个共轭元作为根(这里q=2)，其中li不会超过m，所以º

i(x)=li

m。4/24/202352天津大学电子信息工程学院综合定理2.5，有上式说明，在的qm个根中，所有的根都来自不同的k个共轭根系。下面的例子，说明了共轭元、最小多项式和多项式之间的关系。4/24/202353天津大学电子信息工程学院例2-11找出由本原多项式P(x)=x4+x+1生成的二元扩展域GF(24)上各非零元素的共轭元，并计算与