21+代數(shù)學(xué)基礎(chǔ)+有限域(1)

1、1有限域的表示2有限域的表示 1. 多項(xiàng)式表示 2. N比特的字符表示 3. 向量空間中的基表示 4. 本原元表示31.多項(xiàng)式表示 二元域F2； 多項(xiàng)式f(x)=x8+x4+x3+x+1在F2上不可約； F2x/f(x)上模f(x)的所有多項(xiàng)式集合構(gòu)成一個(gè)含有28個(gè)元素的域.4 域中元素是F2上所有次數(shù)小于8的多項(xiàng)式，可以寫(xiě)成下面的形式： 將每個(gè)元素都可以簡(jiǎn)寫(xiě)為一個(gè)長(zhǎng)度為8的比特串： 即一個(gè)字節(jié)。70,201223344556677iFbbxbxbxbxbxbxbxbi其中，01234567bbbbbbbb5 在16進(jìn)制編碼中，用一個(gè)字符表示一個(gè)長(zhǎng)度為4的比特串，那么一個(gè)字節(jié)可以表示成兩個(gè)16

2、進(jìn)制的字符。 也就是說(shuō)，F(xiàn)28上的任一元素都可以看作區(qū)間00, FF上的一個(gè)字節(jié)。例如：字節(jié)01010111(57)對(duì)應(yīng)的元素為：1246xxxx62.N比特二元域 對(duì)于已知的8次不可約多項(xiàng)式f，我們可以將域F2x/f(x)看作由8個(gè)比特排列所構(gòu)成的28=256個(gè)元素構(gòu)成的域。 一般地，我們可以將域F2x/f(x)看作由deg(f)個(gè)比特排列所構(gòu)成的含有2deg(f)個(gè)元素構(gòu)成的域，將這個(gè)域稱為N比特二元域。 N比特二元域在編碼學(xué)和密碼學(xué)中都有很多應(yīng)用，AES就是在8比特二元域上實(shí)現(xiàn)的。7 在N比特二元域中，加法運(yùn)算即為比特之間的模2加法，與定義多項(xiàng)式f無(wú)關(guān)，但是乘法運(yùn)算與f有關(guān).8域中不可約

3、多項(xiàng)式的根 令F是一個(gè)有限域，f(x)是F上的一個(gè)n次不可約多項(xiàng)式； 類似于數(shù)域的擴(kuò)張，可以將域F擴(kuò)張，使得f(x)在擴(kuò)張后的域上有n個(gè)根. 分別記為 f(x)在F上不可約，這n個(gè)根都不在F中. 110,n9定理103.向量空間中基表示令 F 是有限域，)(xf是 F 上的一個(gè) n 次不可約多項(xiàng)式，是)(xf=0 的任一根，元素12, 1n稱為 F 上的一組基。 定義 多項(xiàng)式基11向量空間v由線性代數(shù)的知識(shí)，n個(gè)線性無(wú)關(guān)的元素可以張成一個(gè)n維向量空間. 向量空間 設(shè)V 是一個(gè)加群， F 是一個(gè)域，對(duì)任何F，V，定義一個(gè)元素V，如果對(duì)于任意VvuF,，運(yùn)算都滿足以下性質(zhì)： (1) vuvu )(

4、; (2) uuu)(; (3) )()(uu; (4) vv 1. 則稱V 是域 F 上的一個(gè)向量空間或線性空間。 12定理令 F 是有限域，)(xf是 F 上的一個(gè) n 次不可約多項(xiàng)式，是)(xf=0 的任一根，則元素12, 1n構(gòu)成 F 上的一組基，該組基張成的向量空間,|121010Frrrrrnniii是一個(gè)階為nF)(#的有限域。 13例 域F2814 這兩個(gè)域都含有28個(gè)元素，同構(gòu). 類似地，后一種表示法也可以用一個(gè)字節(jié)來(lái)表示. 通過(guò)這一節(jié)的學(xué)習(xí)，82F 也是 256 階域，可以用下面的空間來(lái)表示： )70(2iFbi其中，是方程01)(348xxxxxf的一個(gè)根。 012233

5、44556677bbbbbbbb15 中的乘法 f(x)=x8+x4+x3+x+182F165. 本原元表示 有限域的乘法群是一個(gè)循環(huán)群. 其生成元稱為本原元(或者本原根). 17有限域的乘法群 定理定理: 有限域Fq的乘法群F*q是一個(gè)循環(huán)群. 引理1: F*q是至多只有一個(gè)d階循環(huán)子群, 其中d|(q-1). 引理2: d|n(d) = n. 我們需要如下兩條引理:18 證明: 如果 F*q, 那么#=d|(q-1).引理1: F*q是至多只有一個(gè)d階循環(huán)子群, 其中d|(q-1). 同時(shí)的所有元都是方程xd-1=0的根. F*q的所有元都是是方程xq-1-1=0的根. 由于Fq x是唯一

6、分解環(huán), 得證.19引理2: d|n(d) = n. 證明: S=1,2,nSd=x | 1x n, gcd(x, n) = dSd, d|n, 構(gòu)成S的一個(gè)完全劃分#Sd = #x | 1x n, gcd(x, n) = d = #x/d | 1x/d n/d, gcd(x/d, n/d) = 1 = #y | 1y n/d, gcd(y, n/d) = 1 =(n/d)20定理: F*q是一個(gè)循環(huán)群. 證明: 假設(shè)g是F*q的d階元, 那么d | (q-1). 中的d階元有(d)個(gè). ord(gk)=d/(d,k) F*q中的d階元有(d)個(gè). d階循環(huán)群存在即唯一 q-1d|(q-1)(d). 必須取等號(hào)定義: F*q的生成元稱為Fq的本原元本原元. F*q中的(q-1)階元有(q-1)個(gè). 21多項(xiàng)式的表示vs 本原元表示 多項(xiàng)式表示 - 加法容易, 乘法復(fù)雜 本原元表示 - 加法