编码理论第6章.ppt
第6章 数学理论基础6.1基本概念 6.2 群、域及环 6.2.1 群及其性质 6.2.2 子群及陪集 6.2.3 置换群及循环群 6.2.4域、环及有限域6.3 多项式环、域及群 6.3.1基本概念 6.3.2 多项式剩余类环 6.3.3 多项式域 6.3.4 有限域 中的计算 6.3.5 多项式群 6.3.6 极小多项式第6章 数学理论基础6.1 基本概念 在纠错码及密码学研究中，抽象代数已经扮演重要角色，如在线性分组码、循环码、美国高级数据加密标准AES、国际数据加密标准IDEA和椭圆曲线密码体制中，群以及域上的多项式理论等都是其理论基础。本章介绍群以及有限域上多项式等相关知识，以利于以后内容的理解。6.1 基本概念6.1.1 基本概念 如果数a能够被b整除，称b是a的一个因子因子，或称a有一个因子b，记作ba (6-1)如果b是素数，称a有素因子有素因子b。设整数n2，有整数a1,a2,an和d，并且有da1,da2,dan （6-2）那么称d为a1,a2,an公因子公因子,公因子中最大的一个称之为最大公最大公因子因子,记a、b的最大公因子为gcd(a,b)(6-3)例如gcd(36，24)=12，gcd(1008，1260，882，1134)=126。设整数，n2，有整数a1,a2,an和m，并且有a1m,a2m,anm （6-4）那么称m为a1,a2,an公倍数,公倍数中最小的一个称之为最小最小公倍数公倍数。显然，公倍数有无穷多个。记a,b的最小公倍数为lcm(a,b)(6-5)如lcm(12，18)=36，lcm(198，240，360)=7920。可以容易得到如此结果：lcm(a,b)=ab/gcd(a，b)。6.1.2 基本模运算如果a是整数，n是正整数，则定义a除以n所得的余数余数为a模n。记为a mod n (6-6)设a,b,m都是整数,如果m(a-b),则称称a和和b模模m同余同余,记为a b (mod m)(6-7)同余在数论中是一个最为基本的概念，使用了模运算来定义，a和b摸m的余数相同。例如，152(mod l3)，734(mod 23)，21-9(mod l0)。1模运算符性质(1)(a mod n)=(b mod n)等价于ab(mod n)。(2)如果n(a-b),那么ab(mod n)。(3)ab(mod n)等价ba(mod n)。(4)ab(mod n)和bc(mod n)等价于ac(mod n)。定义比n小的非负整数集合为Zn,这个集合称为剩余集剩余集或模模n的剩的剩余类余类。即Zn=0，1，(n-1)或 Zn=a Z0an-1 (6-8)设模n的剩余类中与n互素的集合为 ，则 特别是当n为素数时,有 5.模n求逆的算法。设n和u都是整数，且un，n0。若存在一个整数 ,使成立，则u模模n的逆元的逆元就是v。模n求逆的算法如下：(1)(2)(3)如果 ，则 ,转（2）步(4)如果 ，则u模n不存在逆元(5)如果 ，则u模n的逆元为6.2 群、域及环 6.2.1 群及其性质1.基本概念设G为一个非空的集合，在G内定义了一种代数运算“”，若满足4个条件：(1)有封闭性。对任意 ，有 。(2)结合律成立。对任意 。(3)有单位元e。对任意。(4)存在逆元。对任意 ,有 使 ；称 互为逆元。则称G构成一个群群。群G,有时记做G，定义了一个二元运算的集合。群中元素的个数称之为群的阶或元数群的阶或元数。如果群的元数为有限值，称为有限群有限群；否则为无限群。若群G中，对任意 ，有ab=ba，则称为Abel群群、交换群交换群、加法群加法群或可换群。例6-3 证明非空集合0,1是运算法则 的一个群，已知运算法则 是 证明：根据群的定义，非空集合0,1是的一个群。这是因为：（1）由（6-11）式可知，集合在运算法则 下具有封闭性；（2）集合0,1在运算法则 下满足结合率（3）因为 ，且有则0,1集合中存在单位元e0；(4)因为集合0，1中的元素“0”和“1”，都有则“0”和“1”都存在逆元素。“0”的逆元素就“0”本身；“1”的逆元素就“1”本身。由于在规定运算法则下，集合满足群定义中的四个条件，按群的定义，0，1集合是规定运算法则的一个群。2.群的主要特性(1)一个群单位元是唯一的，每一个群元素的逆元素也是唯一的。(2)设G是运算法则的一个群，若 ，则 (6-14)6.2.2 域、环及有限域 群是有一个二元运算的系统，环及域也是定义了两个二元运算，由于在域中对加减乘除运算都封闭，因而许多与四则运算有关的问题都涉及域的性质。1基本概念一个域域F就是一些元素的集合，具有满足下列性质的两种运算+(加法)和（乘法）。(1)F在“+”和“”下是封闭的。F中所有的a、b和c，满足下列性质：(2)交换律：(3)结合律：(4)分配律：,(b+c)a=ba+ca进一步，F中必须存在元素0和1，满足(5)a+0=a(6)a1=a(7)对F中任意a，存在加法逆元(-a)，使a+(-a)=0(8)对F中任意 ，存在乘法逆元 ，使以上性质对含有有限和无限个元素的域都成立。例如有理数全体、实数全体、复数全体对加法乘法分别构成域，分别称为有理数域、实数域和复数域。它们的元数是无穷的，故称其为无限域。域的集合元数是有限的，则称其为有限域有限域，一般用GF(p)或 表示，p表示其元数元数(阶阶)。有限域也称为Galois域域或伽罗华域（伽罗华域（Galois Field）。例如0和1两个元素按模2加和乘构成域。该域仅有两个元素，记为GF(2)。若只满足域定义中的前7条性质，则称为环环(ring)。注意环的乘法没有单位元，当然更没有逆元。其实环是一个乘法的半群。若环中有乘法单位元，则称其为有单位元环。若环的乘法满足交换律，即任意 则称其为交换环、可换环交换环、可换环。例如在普通加法乘法下：全体整数Z构成环；全体偶数构成环。在模n的加法和乘法下构成环，称为剩余类环。实系数多项式全体在多项式加法和乘法下构成环。2.有限域GF(p)中的计算有限域GF(p)定义为整数0,1,2,p-1的集合,相应的运算为模p的代数运算。如果a,b GF(p),则加法a+br(mod p)(6-41)如果a,b GF(p),则乘法abs(mod p)(6-42)令 表示GF(p)中所有非零元素的集合，可证明在GF(p)中至少存在一个元素g，使得GF(p)中任意非零元素可以表示成g的某次幂的形式，这样的元素g称为GF(p)的生成元生成元(或本原元或本原元)，的乘法逆元是 。即 (6-43)注：均是mod23结果 例6-4有限域GF(23)=O,1,2，22，5是GF(23)的生成元，5的各次幂分别如表6-1所示。表6-1GF(23)的生成元5的各次幂6.3 多项式环、域及群6.3.1 基本概念1.有限域GF(p)上的多项式 系数属于某数域的多项式，称为该数域上的多项数域上的多项式式。比如，二进制系数的多项式称为二元域GF(2)上的多项式，p进制系数的多项式称为p元域GF(p)上的多项式。域的多项式的一般形式为 如果fn0，f（x）称为n次多项式,n为多项式f(x)的阶阶(degree）,记为deg(f(x)。用 表示系数取自域GF(p)的一切多项式的集合。其中的多项式可以按通常的方式进行加法、减法和乘法运算。2.剩余 多项式的除法算法是指对 中的任意一对多项式 a(x)和 ，存在惟一的一对多项式q(x)和r(x)，分别称为商和余数，满足 其中该余数有时又称为剩余剩余，并记为 (6-46)设a(x)、b(x)和f(x)都为GF(p)上的多项式,则剩余的两个重要性质为 3.同余 令f(x)为 中的一个固定多项式,中有两个多项式g(x)和h(x),如果 g(x)-h(x)能被f(x)整除,则g(x)和h(x)关于模模f(x)同余同余,记为 (6-47)如果设 为定义在GF(2)上的多项式。因为故4.既约多项式 设f(x)是次数大于0的多项式，若除了常数、常数与本身的乘积以外，不能再被域GF(p)上的其它多项式除尽，则称f(x)为域GF(p)上的既约多项式既约多项式。次数至少为1的首一既约多项式为素多项式素多项式。所以，一个常数总是多项式的因子，f(x)是否既约与讨论的域有很大关系。5本原多项式 对于有限域GF(p)上的m次既约多项式p(x)，若能被它整除的最简单首一多项式 的次数 ，则称该多项式为本原多项式本原多项式（Primary Polynomials）。本原多项式一定既约；反之，既约多项式未必是本原的。6多项式循环群 由多项式 的各次幂所构成的群称为多项式循环群多项式循环群（Cycle Group）。多项式是群元素之一，称为该循环群的生成元生成元。6.3.2 多项式剩余类环 以数为元素可以构成群、环、域，以多项式为元素同样可以构成群、环、域。下面将讨论用多项式构成群、环、域的方法、条件和性质。某数域上多项式的集合在乘、加运算下可以构成一个多项式环，它是一个以多项式为环元素的交换环。多项式的两个要素是系数和幂次，只要其中一个有无限取值，如系数所在数域是无限域(实数、整数等)或多项式的幂次无限，则多项式环元素的数目也就无限，称之为无限环。然而在纠错码的实际使用中，码集总是有限的，对应的多项式环也应是有限环，因此必须在系数和幂次两个方面对构成环的多项式进行限制。最常用的方法就是利用模运算产生数量有限的剩余类。GF(p)上的多项式在模p加、模f(x)乘运算下，多项式剩余类的全体所构成的交换环称为多项式剩余类环多项式剩余类环，记做 显然，多项式剩余类环是靠GF(p)域保证系数有限，靠模f(x)乘保证幂次有限的。多项式运算中包含了系数间模p乘、加的数域运算。多项式剩余类环的环元素是模f(x)乘的产物，即A(x)B(x)除以f(x)的余式。余式也就是“剩余”类环名称的来历。如果f(x)的最高次幂是n，多项式剩余类环 中所有环元素的次数不高于n-1次，通式形式为：如果多项式最高次项的系数为1，则称该多项式是首一多项式首一多项式。仅包含最高次项和常数项1，且形式为 的首一多项式称为n次最简首一多项式最简首一多项式。例6-5 剩余类环 中,p=2，。若 ，是两个环元素，求 是什么元素?该剩余类环至多由多少个元素组成、它们分别是什么?解：本题的多项式系数取自 ，系数做模2加、模2乘。做一般的多项式乘法运算,然后将结果除以f(x)后取余，得：f(x)是3次多项式，即degf(x)=3，因此环元素的幂次不会超过2，环元素的通式可表示为 其中 3个系数最多可能有8种组合，即该剩余类环至多由8个域元素组成，它们正好是次数小于3的所有可能的多项式,即 与整数环存在子环一样，多项式环也存在多项式子环。如果说GF(p)上无限幂次的多项式构成一个无限环，那么任一n次多项式f(x)的一切倍式是该无限环的一个理想子环。以f(x)为模的多项式剩余类的全体构成一个有限元素的多项式剩余类环 ，这个环也可以有子环。可以证明：中的每一理想子环皆为主理想，且该主理想的生成多项式g(x)必定能整除f(x)。6.3.3 多项式域 讨论多项式域的前提是这个域必须是存在的。因此，首先以定理的形式解决多项式域的存在性问题。定理定理6-4 若f(x)是GF(p)上的n次多项式，是GF(p)域上次数小于n的多项式的全体，则次数小于n的多项式全体 构成环环，当且仅当f(x)是 上的既约多项式时，此环是域域。可以得到了一种产生伽罗瓦域的漂亮的过程!若能找到GF(p)上次数为n的一个素多项式，就可以构造一个有 个元素的伽罗瓦域。这样的域将含有的多项式作为其元素。这些多项式将由定义在GF(p)上的所有次数小于n的多项式构成。容易看到共有 个这样的多项式，它们组成了扩域GF()上的元素。若f(x)是GF(p)上的n次既约多项式，是GF(p)域上次数小于n的多项式的全体，则 在模p加、模f(x)乘运算下构成一个 阶的有限域，称为GF(p)域的扩域扩域(Extension Field)，写做GF()。称GF(p)是扩域的基域。例6-6二元域上的多项式在模2加、模 乘运算下构成一个多项式扩域 ，该扩域的基域是GF(2)=0，1。基域GF(p)是数域，由p个元素组成；扩域GF()则是多项式域,由 个元素组成。可以用n个基域元素去对应一个扩域元素，比如p=2且n=2时，扩域 的元素：0 1 x x+1 2个GF(2)元素的组合：00 01 10 11例6-7 求 和 既约多项式对应多项式域元素和GF(2)元素组合表示的域元素?解:6.3.4 有限域 中的计算 令 是GF(2)上次数为m的既约多项式。有限域GF()由GF(2)上所有次数小于m的多项式组成，即域元素通常用长度为m的二进制串表示，则加法：式中：乘法：式中 多项式是两个乘数多项式在GF(2)上被f(x)除所得的剩余。上述表示的方法称为多项式基表示。令 表示中所有非零元素的集合，可证明在中至少存在一个元素g，使得中任意非零元素可以表示成g的某次幂的形式，这样的元素g称为的生成元生成元(或本原元).例6-8用多项式基表示有限域 ,多项式 ,计算(1)1011+1001=?(2)(1101)(1001)=?解：可以验证f(x)是 上的不可约多项式，则中的元素的计算：
