密碼學(xué)數(shù)學(xué)基礎(chǔ)第十一講有限域

1、第11講 有限域教師：李艷俊1本講內(nèi)容一域的特征二有限域的結(jié)構(gòu)三密碼學(xué)上的簡(jiǎn)單應(yīng)用2一域的特征 若R是無(wú)零因子環(huán)，則其加群中所有非零元的階相同，或是無(wú)限，或是一個(gè)素?cái)?shù)。 設(shè)R是無(wú)零因子環(huán)，當(dāng)其加群中所有非零元的階無(wú)限時(shí)，chR=0；當(dāng)此階為素?cái)?shù)p時(shí)，chR=p。域F的特征或是零，或是素?cái)?shù)。 定義1：設(shè)F是域，1是F的單位元，若1在(F，)的階數(shù)為無(wú)窮大，則稱F的特征為0；若1在(F，)的階數(shù)為素?cái)?shù)p，則稱F的特征為p。3只含有限個(gè)元素的域稱為有限域。有限域的元素個(gè)數(shù)稱為有限域的階。每個(gè)特征為零的域都是無(wú)限域。有限域的特征一定是素?cái)?shù)。在特征是素?cái)?shù)p的域F中，下列等式成立：(ab)p=apbp，(

2、ab)p=apbp，a，bF。4二有限域的結(jié)構(gòu) 有限域F中非零元組成的集合F*關(guān)于乘法做成的群稱為有限域的乘法群。 命題1：設(shè)Fq是一個(gè)含有q個(gè)元素的有限域，F(xiàn)q*=Fq0，則Fq的乘法群Fq*是一個(gè)循環(huán)群。 定義2：設(shè)Fq是一個(gè)有限域，F(xiàn)q*=Fq0，F(xiàn)q*的生成元稱為Fq的本原元。 命題2：設(shè)Fq是一個(gè)含有q個(gè)元素的有限域，則Fq中共有(q1)個(gè)本原元。1有限域的乘法群5例1：求有限域F5=Z5的所有本原元。 解：2和3是F5的本原元。 例2：求模14的原根。 解：3和11是模14的原根。 命題3 設(shè)F是一個(gè)域，若chF=0，則F含有一個(gè)與有理數(shù)域同構(gòu)的子域； 若chF=p，則F含有一個(gè)與

3、Z/（p）同構(gòu)的子域。2. 域的同構(gòu)63有限域的結(jié)構(gòu) 定理1：設(shè)F是一個(gè)特征為p的有限域，則F的元素個(gè)數(shù)一定為p的一個(gè)冪pn，n1。 定理2：對(duì)任意素?cái)?shù)p和任意正整數(shù)n，一定存在一個(gè)含有pn個(gè)元素的有限域。 命題4：設(shè)Fq是一個(gè)含有q個(gè)元素的有限域，對(duì)任意正整數(shù)n，F(xiàn)q上的n次不可約多項(xiàng)式一定存在。7 將階為pn的有限域記作GF(pn)，稱之為pn階的Galois域。 定理3：設(shè)Fq是一個(gè)含有q個(gè)元素的有限域，設(shè)p是一個(gè)素?cái)?shù)，Zp=0，1，2，p1,設(shè)f(x)是Zp上的一個(gè)n次不可約多項(xiàng)式。若|Fq|=pn，其中n2是一個(gè)整數(shù)，則Fq與Zpx/(f(x)同構(gòu)。若|Fq|=p，則Fq與Zp同構(gòu)。

4、8設(shè)p是任意給定的一個(gè)素?cái)?shù)，n是任一正整數(shù)。令f(x)是域Zp上一個(gè)n次不可約多項(xiàng)式，則Zpx/(f(x)是域， Zpx/(f(x)=a0a1xan1xn1(f(x)|aiZp。域Zpx/(f(x)共包含pn個(gè)元素。把a(bǔ)0a1xan1xn1(f(x)簡(jiǎn)記為： a0a1xan1xn1。4利用不可約多項(xiàng)式構(gòu)造有限域9記GF(pn)x = Zpx/(f(x)，則GF(pn)x=a0a1xan1xn1|aiZp，其系數(shù)的加法和乘法遵從模p的加法和乘法，多項(xiàng)式的加法和乘法遵從模f(x)的加法和乘法。 例3：把a(bǔ)0a1x(x2x1)簡(jiǎn)記為a0a1x，則Z2x/(x2x1)的加法和乘法的運(yùn)算表簡(jiǎn)化如下：10

5、01xx1001xx1110 x1xxxx101x1x1x1001xx100000101xx1x0 xx11x10 x11x115有限域的表示設(shè)p為素?cái)?shù)，q=pn，GF(q)*是GF(q)中非零元的集合，則（GF(q)*，）是q1階循環(huán)群。將GF(pn)x=Zpx/(f(x)簡(jiǎn)記為GF(pn)。設(shè)是GF(q)的本原元，即是GF(q)*的生成元，則GF(q)*=，2，q2，q1=1。GF(q)=0，1，2，q2。12設(shè)p是任意給定的一個(gè)素?cái)?shù)，n是任一正整數(shù)，設(shè)f(x)是域Zp上一個(gè)n次不可約多項(xiàng)式。GF(pn)=Zpx/(f(x)的兩種表示方法： （1）GF(pn)=a0a1xan1xn1|ai

6、Zp，i=0，1，n1。（2）設(shè)q=pn，是GF(q)的一個(gè)本原元，則GF(q)=0，1，2，q2。13例4：已知x21是Z3上的不可約多項(xiàng)式，利用該不可約多項(xiàng)式構(gòu)造一個(gè)9階有限域GF(32)x，寫(xiě)出GF(32)x的9個(gè)元素，并判斷1x是否為GF(32)的本原元。1x是GF(32)的本原元。解：GF(32)x=Z3x/(x21)=a0a1x|a0，a1Z3=0，1，2，x，1x，2x，2x，12x，22x。 練習(xí)：找出其它所有本原元。14三密碼學(xué)上的簡(jiǎn)單應(yīng)用 設(shè)f(x)是域Z2上一個(gè)n次不可約多項(xiàng)式，則GF(2n)x=Z2x/(f(x)=a0a1xan1xn1|aiZ2。 例5：設(shè)f(x)=x

7、3x1為一個(gè)3次不可約多項(xiàng)式，則GF(23)x=0，1，x，x1，x2，x21，x2x，x2x1。 若x為GF(23)的一個(gè)本原元，則GF(23)x=0，1，x，x2，x3，x4，x5，x6。15 若記0=000=0，1=001=1，x=010=2，x1=011=3，x2=100=4，x21=101=5，x2x=110=6，x2x1=111=7；則GF(23)x= Z2x/(x3x1)乘法表如下：12345671123456722463175336574124437625155142736667153247752164316Z8=0，1，2，7乘法表1234567112345672246024

8、6336147254404040455274163664206427765432117非零元素1234567在Z8中的出現(xiàn)次數(shù) 48412484在GF(23)中的出現(xiàn)次數(shù) 7777777在Z8中，非零元素2，4和6無(wú)乘法逆元。在GF(23)中，所有非零元素都有乘法逆元。182有限域GF(28)在AES中的應(yīng)用 高級(jí)加密標(biāo)準(zhǔn)（AES）使用的有限域GF(28)x= Z2x/(m(x)，其中m(x)=x8x4x3x1為不可約多項(xiàng)式。 在AES中，把每個(gè)字節(jié)（8比特）看成是有限域GF(28)中的元素。字節(jié)b7b6b5b4b3b2b1b0對(duì)應(yīng)的多項(xiàng)式為：b7x7b6x6b5x5b4x4b3x3b2x2b

9、1xb0.19加法：就是字節(jié)的異或運(yùn)算。 兩個(gè)多項(xiàng)式相加，結(jié)果是一個(gè)多項(xiàng)式，其系數(shù)是兩個(gè)元素中對(duì)應(yīng)系數(shù)的模2加。 多項(xiàng)式的形式：二進(jìn)制的形式：十六進(jìn)制的形式：加法逆元 對(duì)于有限域GF(28) ，選定不可約多項(xiàng)式m(x)=x8+x4+x3+x+1，就可以進(jìn)行以下運(yùn)算。的加法逆元是它本身。20 乘法：先進(jìn)行多項(xiàng)式相乘，再將結(jié)果模不可約多項(xiàng)式m(x)=x8+x4+x3+x+1。 例：21乘法逆元 由于m(x)是不可約的，故GF(28)中任一非零元素都與m(x)互素，從而有乘法逆元(即模m(x)的逆)，這樣GF(28)中非零元素為除數(shù)的除法總是可以進(jìn)行。 任何系數(shù)在二元域GF(2)中并且次數(shù)小于8的多項(xiàng)式b(x)，利用歐幾里德算法可以計(jì)算a(x)和c(x)使得那么有a(x)b(x) mod m(x)= 1，這說(shuō)明b(x)的逆元素為例：用歐幾里德算法求得GF(28)中元素57的乘法逆元為BF。22有限域GF(28)上多項(xiàng)式