21+代數(shù)學基礎+有限域(1)

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

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

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

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

5、44556677bbbbbbbb15 中的乘法 f(x)=x8+x4+x3+x+182F165. 本原元表示 有限域的乘法群是一個循環(huán)群. 其生成元稱為本原元(或者本原根). 17有限域的乘法群 定理定理: 有限域Fq的乘法群F*q是一個循環(huán)群. 引理1: F*q是至多只有一個d階循環(huán)子群, 其中d|(q-1). 引理2: d|n(d) = n. 我們需要如下兩條引理:18 證明: 如果 F*q, 那么#=d|(q-1).引理1: F*q是至多只有一個d階循環(huán)子群, 其中d|(q-1). 同時的所有元都是方程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, 構成S的一個完全劃分#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是一個循環(huán)群. 證明: 假設g是F*q的d階元, 那么d | (q-1). 中的d階元有(d)個. ord(gk)=d/(d,k) F*q中的d階元有(d)個. d階循環(huán)群存在即唯一 q-1d|(q-1)(d). 必須取等號定義: F*q的生成元稱為Fq的本原元本原元. F*q中的(q-1)階元有(q-1)個. 21多項式的表示vs 本原元表示 多項式表示 - 加法容易, 乘法復雜 本原元表示 - 加法