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

第11講 有限域,教師：李艷俊,本講內(nèi)容,一域的特征 二有限域的結(jié)構(gòu) 三密碼學(xué)上的簡單應(yīng)用,一域的特征,若R是無零因子環(huán)，則其加群中所有非零元的階相同，或是無限，或是一個素數(shù)。,設(shè)R是無零因子環(huán)，當(dāng)其加群中所有非零元的階無限時，chR=0；當(dāng)此階為素數(shù)p時，chR=p。,域F的特征或是零，或是素數(shù)。,定義1：設(shè)F是域，1是F的單位元，若1在(F，)的階數(shù)為無窮大，則稱F的特征為0；若1在(F，)的階數(shù)為素數(shù)p，則稱F的特征為p。,只含有限個元素的域稱為有限域。,有限域的元素個數(shù)稱為有限域的階。,每個特征為零的域都是無限域。,有限域的特征一定是素數(shù)。,在特征是素數(shù)p的域F中，下列等式成立：,(ab)p=apbp，,(ab)p=apbp，a，bF。,二有限域的結(jié)構(gòu),有限域F中非零元組成的集合F*關(guān)于乘法做成的群稱為有限域的乘法群。,命題1：設(shè)Fq是一個含有q個元素的有限域，F(xiàn)q*=Fq0，則Fq的乘法群Fq*是一個循環(huán)群。,定義2：設(shè)Fq是一個有限域，F(xiàn)q*=Fq0，F(xiàn)q*的生成元稱為Fq的本原元。,命題2：設(shè)Fq是一個含有q個元素的有限域，則Fq中共有(q1)個本原元。,1有限域的乘法群,例1：求有限域F5=Z5的所有本原元。,解：2和3是F5的本原元。,例2：求模14的原根。,解：3和11是模14的原根。,命題3 設(shè)F是一個域，若chF=0，則F含有一個與有理數(shù)域同構(gòu)的子域； 若chF=p，則F含有一個與Z/（p）同構(gòu)的子域。,2. 域的同構(gòu),3有限域的結(jié)構(gòu),定理1：設(shè)F是一個特征為p的有限域，則F的元素個數(shù)一定為p的一個冪pn，n1。,定理2：對任意素數(shù)p和任意正整數(shù)n，一定存在一個含有pn個元素的有限域。,命題4：設(shè)Fq是一個含有q個元素的有限域，對任意正整數(shù)n，F(xiàn)q上的n次不可約多項式一定存在。,將階為pn的有限域記作GF(pn)，稱之為pn階的 Galois域。,定理3：設(shè)Fq是一個含有q個元素的有限域，設(shè)p是一個素數(shù)，Zp=0，1，2，p1,設(shè)f(x)是Zp上的一個n次不可約多項式。若|Fq|=pn，其中n2是一個整數(shù)，則Fq與Zpx/(f(x)同構(gòu)。若|Fq|=p，則Fq與Zp同構(gòu)。,設(shè)p是任意給定的一個素數(shù)，n是任一正整數(shù)。令f(x)是域Zp上一個n次不可約多項式，則Zpx/(f(x)是域， Zpx/(f(x)=a0a1xan1xn1(f(x)|aiZp。,域Zpx/(f(x)共包含pn個元素。,把a0a1xan1xn1(f(x)簡記為： a0a1xan1xn1。,4利用不可約多項式構(gòu)造有限域,記GF(pn)x = Zpx/(f(x)，,則GF(pn)x=a0a1xan1xn1|aiZp， 其系數(shù)的加法和乘法遵從模p的加法和乘法， 多項式的加法和乘法遵從模f(x)的加法和乘法。,例3：把a0a1x(x2x1)簡記為a0a1x，則Z2x/(x2x1)的加法和乘法的運算表簡化如下：,5有限域的表示,設(shè)p為素數(shù)，q=pn，GF(q)*是GF(q)中非零元的集合，則（GF(q)*，）是q1階循環(huán)群。,將GF(pn)x=Zpx/(f(x)簡記為GF(pn)。,設(shè)是GF(q)的本原元，即是GF(q)*的生成元， 則GF(q)*=，2，q2，q1=1。,GF(q)=0，1，2，q2。,設(shè)p是任意給定的一個素數(shù)，n是任一正整數(shù)， 設(shè)f(x)是域Zp上一個n次不可約多項式。,GF(pn)=Zpx/(f(x)的兩種表示方法：,（1）GF(pn)=a0a1xan1xn1|aiZp，i=0，1，n1。,（2）設(shè)q=pn，是GF(q)的一個本原元，則GF(q)=0，1，2，q2。,例4：已知x21是Z3上的不可約多項式，利用 該不可約多項式構(gòu)造一個9階有限域GF(32)x， 寫出GF(32)x的9個元素，并判斷1x是否為 GF(32)的本原元。,1x是GF(32)的本原元。,解：GF(32)x=Z3x/(x21) =a0a1x|a0，a1Z3=0，1，2，x，1x，2x，2x，12x，22x。,練習(xí)：找出其它所有本原元。,三密碼學(xué)上的簡單應(yīng)用,設(shè)f(x)是域Z2上一個n次不可約多項式， 則GF(2n)x=Z2x/(f(x) =a0a1xan1xn1|aiZ2。,例5：設(shè)f(x)=x3x1為一個3次不可約多項式，則GF(23)x=0，1，x，x1，x2，x21，x2x，x2x1。,若x為GF(23)的一個本原元，則GF(23)x=0，1，x，x2，x3，x4，x5，x6。,若記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)乘法表如下：,Z8=0，1，2，7乘法表,在Z8中，非零元素2，4和6無乘法逆元。,在GF(23)中，所有非零元素都有乘法逆元。,2有限域GF(28)在AES中的應(yīng)用,高級加密標(biāo)準(zhǔn)（AES）使用的有限域GF(28)x= Z2x/(m(x)，其中m(x)=x8x4x3x1為不可約多項式。,在AES中，把每個字節(jié)（8比特）看成是有限域GF(28)中的元素。,字節(jié)b7b6b5b4b3b2b1b0對應(yīng)的多項式為：,b7x7b6x6b5x5b4x4b3x3b2x2b1xb0.,加法：就是字節(jié)的異或運算。,兩個多項式相加，結(jié)果是一個多項式，其系數(shù)是兩個元素中對應(yīng)系數(shù)的模2加。,多項式的形式：,二進(jìn)制的形式：,十六進(jìn)制的形式：,加法逆元,對于有限域GF(28) ，選定不可約多項式m(x)=x8+x4+x3+x+1，就可以進(jìn)行以下運算。,的加法逆元是它本身。,乘法：先進(jìn)行多項式相乘，再將結(jié)果模不可約多項式m(x)=x8+x4+x3+x+1。,例：,乘法逆元,由于m(x)是不可約的，故GF(28)中任一非零元素都與m(x)互素，從而有乘法逆元(即模m(x)的逆)，這樣GF(28)中非零元素為除數(shù)的除法總是可以進(jìn)行。,任何系數(shù)在二元域GF(2)中并且次數(shù)小于8的多項式b(x)，利用歐幾里德算法可以計算a(x)和c(x)使得,那么有a(x