第2章 近世代数

1、1第第2 2章章 近世代数简介近世代数简介 线性分组码中最重要的一个子类-循环码循环码(RS、BCH码码)，它的结构完全建立在有限域有限域的基础之上，被称为代数几何码。代数几何码。 有限域有限域以近世代数以近世代数为基础。 近世代数的运算对象近世代数的运算对象：整数、多项式、矩阵等。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，

2、10，都是合数；这样，全体正整数又分为：全体素数和全体合数。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构成一个群构成一个群。4（1）加群( (addition group) ) 、乘群( (multiplication

3、 group) ) （针对群中的运算）（2）群的阶（针对群中元素的个数）（3）有限群( (finite group) )、无限群( (infinite group) ) （针对群中元素的个数） （4）交换群( (commutative group) )或阿贝尔群( (Abel group) ) （针对群中的运算） 5例例2-22-2 G1：整数全体。 对加法构成群对加法构成群，无限加群； 对乘法不够成群对乘法不够成群。Why? G2：实数全体。 对加法构成群； 除0元素之外的全体实数，对乘法构成群。 单位元e=1。 G1和G2有都是阿贝尔群阿贝尔群，且都是无限群。群群将将 和和 联系在一起？联

4、系在一起？64. 4. 域域 (Field)(Field) 对于非空元素集合F F，若在F中定义了加法(addition)和乘法(multiplication)两种运算，且满足下面的公理：（1）F关于加法构成阿贝尔群阿贝尔群，其加法恒等加法恒等元元记为0；（2）F中非非0 0元素全体元素全体对乘法构成阿贝尔群，其乘法恒等元（单位元）乘法恒等元（单位元）记为1。（3）加法和乘法之间满足如下分配率(distributive) ：则则称称F F是一个域是一个域。cabaacbacabcba)()(7（1）域的阶（针对群中元素的个数），记为q。（2）有限域或伽逻华（Galois）域，表示为： GF(q

5、)。域域将将 和和 联系在一起？联系在一起？8例例2-32-3 F1：有理数全体、实数全体对加法和乘法都分别构成域，分别称为有理数域和实数域。 F2：0、1两个元素模2加构成域；由于该域中只有两个元素，记为GF(2)。9 定理：定理： 设p为质数，则整数全体对p取模的剩余类：0，1，2，p-1，在模p的运算下（p模相加和相乘），构成p阶有限域阶有限域GF(p)。例例2-4 验证以p=3为模的剩余类全体：0，1，2构成一个有限域GF(3)。+012001211202201012000010122021105. 5. 循环群循环群 如果一个元素一个元素 的各次幂幂 0， 1， 2 ，的全体构成了一

6、个群，称为循环群循环群（cycle group），），元素称为生成元生成元或者本原元本原元（primitive element） 。 记作：G= 0， 1， 2 ，其中 0 = e 是单位元。 可以证明，有限域GF(q)的q-1q-1个非个非0 0元素元素，在模模q q乘运算下乘运算下，可以构成一个循环群（幂群），即G上的所有非0元素可以由一个元素的各次次幂幂 0， 1， 2 ， q-1生成生成。11例例2-52-5 q=5 的伽逻华域GF(5)=0,1,2,3,4， 非零元素为非零元素为1,2,3,4 模5乘运算。 恒等元？加法恒等元？乘法恒等元？ 为了弄清那些元素是为了弄清那些元素是本原元

7、本原元，分别计算各元素的各次幂。12GF(5)中非零元素的幂零元素的幂、阶及其逆元阶及其逆元元素各 次 幂元素的阶加法逆元乘法逆元01231111114121243（8）4333134（9）2（27）4224141（16） 4（64）214（1）元素的阶（能产生域元素的个数）：（2）2、3都是本原元；（3）1、4不是本原元（生成元）。136. 6. 环（环（RingRing） 定义：在非空集合R中，若定义了两种代数运算加和乘，且满足：（1）集合R在加法运算下构成阿贝尔群；（2）乘法有封闭性，对于任何a,bR，有ab R；（3）乘法结合率成立，且加法和乘法之间分配率成立，即对任何a,bR，有a(

8、b+c)=ab+ac (b+c)a=ba+ca则称称R R是一个环是一个环。14环环将将 和和 联系在一起？联系在一起？ What is the relationship with Group, Field and Ring? What is the difference between Field and Ring?152.2 2.2 多项式剩余类环多项式剩余类环1.1.域上多项式的定义域上多项式的定义 多项式与码字的关系：桥梁； 多项式的系数表示 ； x的幂次表示 ； 域上的多项式 针对系数定义； 例如二进制系数多项式，称为二元域GF(2)上的多项式。 q进制系数的多项式，称为q元域GF(

9、q)上的多项式。 群、环、域对多项式也成立。16域上多项式：域上多项式： GF(q)上上多项式的定义：0111.)(fxfxfxfxfnnnn),.,2, 1, 0()(niqGFfi17(1) 多项式两要素：系数和幂次多项式两要素：系数和幂次(2) 多项式幂次多项式幂次(3) 首一多项式首一多项式(4) 最简首一多项式最简首一多项式(5) 多项式的有限性分析多项式的有限性分析182. 2. 多项式剩余类环存在定理多项式剩余类环存在定理 有限有限 域域GF(q)上上 多项式多项式若以若以f( (t) )为模，对全体多项式做为模，对全体多项式做模乘模乘运算，运算，q q为模，对系数做为模，对系数

10、做模加模加运算运算，得到的得到的多项式多项式剩余类剩余类的全体，的全体，可以构成一个交换环，称为多项式剩余类环，记为多项式剩余类环，记为Rq(x)f(x)。0)(,.)(0111xffxfxfxfxfnnnn19 系数对q模加，多项式对f(x)f(x)模模乘运算： A(x)、B(x)是两个环元素，用q模加 用f(x)模乘iiniiinixbxBxaxA1010)()(和iqiinixbaxBxAmod10)()()()(modmod1010)()()(xfjiqjinjnixbaxBxA 20 若多项式 f (x) 的最高次幂n=m，有限域为GF(q)。 多项式剩余环类Rq(x)f(x)中 环

11、元素环元素的最高次数最高次数为 ； 多项式的一般形式一般形式为： 这个环这个环中共有中共有 个元素？个元素？121210.(),0,1, 2,.,1mmmmiaxaxa xaaG Fqim21例例2-62-6 剩余类环为Rq(x)f(x)，q=2，f (x)=x3+x+1。 若A(x)=x2+x+1，B(x)=x2+1是两个多项式多项式。 求（1）求对A(x)B(x) 取模的剩余多项式？ （2） A(x)B(x)构成的剩余类环最多有多少个元素？ 解：（1）多项式乘法运算）多项式乘法运算22432243( )( )(1)(1)11A xB xxxxxxxxxxxx2211111232324343

12、xxxxxxxxxxxxxxx（2）用f (x)除上面的多项式，有23 得到得到，A(x)B(x)modf(x)= x2 + x。 一般形式式：由于环元素只有由于环元素只有3 3个系数个系数，最多的，最多的不同组合不同组合有有2 23 3种种。因此该剩余类环最多只有只有8 8个环元个环元素素（包括多项式和常数）（包括多项式和常数）。10)2(2100122，、其中GFaaaaxaxa242.3 2.3 多项式域和循环群多项式域和循环群1.1.既约多项式（既约多项式（Irreducible polynomials） 定义定义：设 Pl (x)是次数大于0的多项式。如果除常数C和C Pl (x)之

13、外，不能被域GF(q)上的其它多项式整除，则称 Pl (x)是域GF(q)上的既约多项式既约多项式。25(1) 常数常数总是多项式的因子总是多项式的因子。(2) 一个多项式一个多项式 f (x) 是否为既约多项式与所是否为既约多项式与所定义的定义的域域有关。有关。(3) 一个多项式一个多项式既约的充要条件既约的充要条件：多项式：多项式Pl (x) 不能分解成两个次数低于不能分解成两个次数低于Pl (x)的多项式的乘的多项式的乘积。积。(4) 完全分解完全分解：n次多项式最多能分解成次多项式最多能分解成n个个一一次多项式次多项式的乘积，被称为完全分解。的乘积，被称为完全分解。 (5) 一次多项式

14、一次多项式一定是既约的。一定是既约的。262. 本原多项式（本原多项式（Primary Polynomials）定义：对于有限域GF(q)上的m次既约多项式P(x)，若能被它整除的最简首一多项式最简首一多项式（xn - 1）的次数为：则称这个多项式P(x)为本原多项式本原多项式。 本原多项式一定是既约的；本原多项式一定是既约的； 但既约多项式不一定是本原的。但既约多项式不一定是本原的。1mqn273. 多项式循环群（多项式循环群（Cycle Group）定义定义：群内的：群内的所有元素所有元素由由多项式多项式 的各次幂的各次幂构构成，称为多项式循环群成，称为多项式循环群。 多项式多项式 是一个

15、群元素，被称为循环群的生成元。例例2-72-7，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阶阶 有限循环群有限循环群。28域存在定理域存在定理 定理定理2.1若Pl (x)是有限域GF(q)上的m次既约次既约多项式，则GF(q)域上次数小于m的多项式的全体，在模在模q加、模加、模Pl (x)乘乘运算下构成一个qm 阶有限域。阶有限域。扩展域扩展域： GF (qm) 基基 域：域：GF (q) 29例例2-82-8 二元域GF(2)上，模2加、模x2+x+1(m=2)乘

16、运算下构成一个扩展域扩展域： GF(22)=0,1,x,x+1， 基域基域：GF(2)=0,130 基域基域GF(q)是数域数域，有q个个域元素； 扩展域扩展域GF(qm)则是多项式域多项式域，有qm个个域元素； m 个个 基域的元素对应扩展域的一个一个元素：扩展域GF(22)的元素01xx+1m (2)个域GF(2)的元素0001101131循环群存在定理循环群存在定理定理定理2.2 若P(x)是GF(q)上m次次本原多项式本原多项式，则GF(qm)域上幂次小于m的非0多项式的全体（ 共有qm-1个），在模q加、模P(x)乘运算下构成一个多项式循环群多项式循环群。 在扩展域GF(qm)里，至

17、少存在一个本原元，其各次幂能构成扩展域GF(qm)的全部非0的域元素。m012q2.、32总总 结结GF(q)上多项式上多项式若为：（1）一般一般多项式多项式 f (x) ，构成qm阶 。（2） 既约既约多项式 Pl (x)，构成qm阶 。（3）本原本原多项式 P(x)，构成qm-1阶 。 对多项式的限制越多，扩展域具备的性质也就越多。 如何找到构成循环群的生成元？332.4 2.4 循环群的生成元循环群的生成元定理定理2.32.3GF(q)上的m次本原多项式本原多项式P(x)的根根，一定是扩展域GF(qm)上的本原元本原元 。 证明：证明：34 构成循环群的步骤：构成循环群的步骤： 找到找到

18、GF(q)上的一个上的一个m次本原多项式；次本原多项式； 取其根取其根 ，并计算，并计算 的各次幂的各次幂 得到扩展域的所有非得到扩展域的所有非0元素，即循环群。元素，即循环群。m01q-2.、352.5 2.5 域元素的性质域元素的性质 本原元本原元，用用 表示，表示，各次幂可以生成扩展域GF(qm)中全部全部q qm m-1-1个非个非0 0域元素域元素； 非本原元非本原元，用用 表示，表示，只能生成部分部分域元素。 下面的定理回答：下面的定理回答： 什么样的域元素是本原元？ 什么样的域元素是非本原元？ 对于非本原元，它们的阶又是多少？36定理定理2.42.4扩展域扩展域GF(qm)上的非

19、零元素上的非零元素 k 的的阶阶一一定是定是qm-1的因子，其值为：的因子，其值为：GCD表示最大公约数最大公约数（Greatest Common Divisor）。)1,(1mmqkGCDqn37如果 n= qm-1，本原元；如果 n qm-1，非本原元， n 一定是qm-1的一个因子，一定能够整除qm-1。推论推论2-42-4在循环群中，n 阶域元素的n n次幂次幂恒等于1。证明：证明：38例例2-92-9 P(x)=x4+x+1是GF(2)上的本原多项式，试用本原元的各次幂生成二元扩展域GF(24)的全部域元素全部域元素，并计算域元素的阶。 解：解：39各次幂k的多项式多项式的系数m重元

20、素的阶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生成的循环群40各次幂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）1541 结论：结论：（1）本原元不是唯一的，共有8个本原元。

21、（2）不是所有的元素都是本原元。（3）以 7 为例，可以生成15个域元素。,.)()(,)(,)(132847661521371427717422.6 2.6 域元素、根、最小多项式的关系域元素、根、最小多项式的关系定理定理2.52.5 扩展域GF(qm)上的所有非零域元素0 ，1 ， 2 ， qm-2 都是GF(q)上多项式 的根，即 可完全分解为一次项的乘积。有， 证明：证明：11mqx11mqx).()()(122101mmqqxxxxx43定理2.6扩展域GF(qm)上域元素和的q l次幂等于元素q l次幂的和，即有： i是域元素。llqikiqiki)(1144定理定理2.72.7如

22、果 是是 GF(q) 上的 m次次多项式f (x)的根根，那么 的的 q l i (li = 1,2,l m)次幂也一定是 f (x) 的根根。 即：如果 是是f (x)的根的根，那么 也一定是也一定是f (x)的根的根； m是多项式的次数，是多项式的次数，li 是是小于小于m的数。的数。 证明：证明：liq45费尔马费尔马(Fermat)(Fermat)定理定理： 由定理2.5，GF(qm)上的任意一个域元域元素素 一定是 所以有，01111mmqqx的根，即有mq4612111,13( )1mmmqqqqqxf xx ， ，(1) 也都是不同的根（2）共有m个根，称为 的共轭元。（ ）这m

23、个根称为=的共轭根系。 由定理由定理2.7： 共轭元具有相同的基底共轭元具有相同的基底 q ( 是一个域元素，是一个域元素，q是是基域的阶基域的阶)； 费马定理限制了共轭根系的个数费马定理限制了共轭根系的个数（最多（最多m个）个）。47 根据费尔马定理，根据费尔马定理，共轭元可构成循环共轭元可构成循环： 一个多项式的根，可以来自多个不同的根系；一个多项式的根，可以来自多个不同的根系； 如果一个如果一个多项式多项式的的所有根由所有根由同一个基底为同一个基底为 q的根系的根系构成，称这样的多项式为构成，称这样的多项式为 的最小多的最小多项式项式。mmqqqq,121，48两个重要的性质： 最小多项式在在GF(q)中一定是既约一定是既约的； 本原元本原元共轭根系对应的最小多项式的最小多项式的次数一定等于次数一定等于m。反之不成立。49定理定理2.82.8：GF(q)上的多项式 一定可以分解成若干个最小多项式之积，即有， 最小多项式必然以同一个根系的同一个根系的li个个共轭元为根(这里q=2)，其中li不会超过不会超过m m