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