密码学数学基础第十一讲-有限域课件.ppt

1、第第11讲讲 有限域有限域教师：李艳俊本讲内容本讲内容一域的特征一域的特征二有限域的结构二有限域的结构三密码学上的简单应用三密码学上的简单应用一域的特征一域的特征 若若R R是无零因子环，则其加群中所有非零元的是无零因子环，则其加群中所有非零元的阶相同，或是无限，或是一个素数。阶相同，或是无限，或是一个素数。设设R R是无零因子环，当其是无零因子环，当其加群加群中所有非零元的中所有非零元的阶无限时，阶无限时，chRchR=0=0；当此阶为素数；当此阶为素数p时，时，chRchR=p。域域F F的特征或是零，或是素数。的特征或是零，或是素数。定义定义1 1：设：设F F是域，是域，1 1是是F

2、F的单位元，若的单位元，若1 1在在(F(F，)的阶数为无穷大，则称的阶数为无穷大，则称F F的特征为的特征为0 0；若；若1 1在在(F(F，)的阶数为素数的阶数为素数p，则称，则称F F的特征为的特征为p。只含有限个元素的域称为有限域。只含有限个元素的域称为有限域。有限域的元素个数称为有限域的阶。有限域的元素个数称为有限域的阶。每个特征为零的域都是无限域。每个特征为零的域都是无限域。有限域的特征一定是素数。有限域的特征一定是素数。在特征是素数在特征是素数p的域的域F F中，下列等式成立：中，下列等式成立：(ab)p=apbp，(ab)p=apbp，a，b F F。二有限域的结构二有限域的结

3、构 有限域有限域F F中非零元组成的集合中非零元组成的集合F F*关于乘法做关于乘法做成的群称为有限域的乘法群。成的群称为有限域的乘法群。命题命题1 1：设：设F Fq是一个含有是一个含有q个元素的有限域，个元素的有限域，F Fq*=F=Fq00，则，则F Fq的乘法群的乘法群F Fq*是一个循环群。是一个循环群。定义定义2 2：设设F Fq是一个有限域，是一个有限域，F Fq*=F=Fq00，F Fq*的的生成元称为生成元称为F Fq的本原元。的本原元。命题命题2 2：设：设F Fq是一个含有是一个含有q个元素的有限域，则个元素的有限域，则F Fq中共有中共有(q1)1)个本原元。个本原元。

4、1 1有限域的乘法群有限域的乘法群例例1 1：求有限域：求有限域F F5 5=Z=Z5 5的所有本原元。的所有本原元。解：解：2 2和和3 3是是F F5 5的本原元。的本原元。例例2 2：求模：求模1414的原根。的原根。解：解：3和和11是模是模14的原根。的原根。命题命题3 3 设设F F是一个域，若是一个域，若chFchF=0=0，则，则F F含有一个含有一个与有理数域同构的子域；与有理数域同构的子域；若若chFchF=p=p，则，则F F含有一个含有一个与与Z/Z/（p p）同构的子域。）同构的子域。2.2.域的同构域的同构3 3有限域的结构有限域的结构 定理定理1 1：设：设F F

5、是一个特征为是一个特征为p的有限域，则的有限域，则F F的元的元素个数一定为素个数一定为p的一个幂的一个幂pn，n11。定理定理2 2：对任意素数：对任意素数p和任意正整数和任意正整数n，一定存在，一定存在一个含有一个含有pn个元素的有限域。个元素的有限域。命题命题4 4：设：设F Fq是一个含有是一个含有q个元素的有限域，对个元素的有限域，对任意正整数任意正整数n，F Fq上的上的n次不可约多项式一定存在。次不可约多项式一定存在。将阶为将阶为pn的有限域记作的有限域记作GF(GF(pn)，称之为，称之为pn阶的阶的GaloisGalois域。域。定理定理3 3：设：设F Fq是一个含有是一个

6、含有q个元素的有限域，设个元素的有限域，设p是一个素数，是一个素数，Z Zp=0=0，1 1，2 2，p1,1,设设f(x)是是Z Zp上的一个上的一个n次不可约多项式。若次不可约多项式。若|F|Fq|=|=pn，其中，其中n22是一个整数，则是一个整数，则F Fq与与Z Zp x/(/(f(x)同构。若同构。若|F|Fq|=|=p，则，则F Fq与与Z Zp同构。同构。设设p是任意给定的一个素数，是任意给定的一个素数，n是任一正整数。令是任一正整数。令f(x)是域是域Z Zp上一个上一个n次不可约多项式，则次不可约多项式，则Z Zp x/(/(f(x)是域，是域，Z Zp x/(/(f(x)

7、=)=a0 0a1 1xan1 1xn1 1(f(x)|)|ai Z Zp。域域Z Zp x/(/(f(x)共包含共包含pn个元素。个元素。把把a0 0a1 1xan1 1xn1 1(f(x)简记为：简记为：a0 0a1 1xan1 1xn1 1。4 4利用不可约多项式构造有限域利用不可约多项式构造有限域记记GF(GF(pn)x=Z=Zp x/(/(f(x)，则则GF(GF(pn)x=a0 0a1 1xan1 1xn1 1|ai Z Zp，其系数的加法和乘法遵从模其系数的加法和乘法遵从模p的加法和乘法，的加法和乘法，多项式的加法和乘法遵从模多项式的加法和乘法遵从模f(x)的加法和乘法。的加法和

8、乘法。例例3 3：把：把a0 0a1 1x(x2 2x1)1)简记为简记为a0 0a1 1x，则则Z Z2 2 x/(/(x2 2x1)1)的加法和乘法的运算表简化的加法和乘法的运算表简化如下：如下：0 01 1xx1 10 00 01 1xx1 11 11 10 0 x1 1xxxx1 10 01 1x1 1x1 1x1 10 00 01 1xx1 10 00 00 00 00 01 10 01 1xx1 1x0 0 xx1 11 1x1 10 0 x1 11 1x5 5有限域的表示有限域的表示设设p为素数，为素数，q=pn，GF(GF(q)*是是GF(GF(q)中非零元的中非零元的集合，则

9、（集合，则（GF(GF(q)*，）是）是q1 1阶循环群。阶循环群。将将GF(GF(pn)x=Z=Zp x/(/(f(x)简记为简记为GF(GF(pn)。设设 是是GF(GF(q)的本原元，即的本原元，即 是是GF(GF(q)*的生成元，的生成元，则则GF(GF(q)*=，2 2，q2 2，q1 1=1=1。GF(GF(q)=0)=0，1 1，2 2，q2 2。设设p是任意给定的一个素数，是任意给定的一个素数，n是任一正整数，是任一正整数，设设f(x)是域是域Z Zp上一个上一个n次不可约多项式。次不可约多项式。GF(GF(pn)=Z)=Zp x/(/(f(x)的两种表示方法：的两种表示方法：

10、（1 1）GF(GF(pn)=)=a0 0a1 1xan1 1xn1 1|ai Z Zp，i=0=0，1 1，n1 1。（2 2）设）设q=pn，是是GF(GF(q)的一个本原元，则的一个本原元，则GF(GF(q)=0)=0，1 1，2 2，q2 2。例例4 4：已知：已知x2 21 1是是Z Z3 3上的不可约多项式，利用上的不可约多项式，利用该不可约多项式构造一个该不可约多项式构造一个9 9阶有限域阶有限域GF(3GF(32 2)x，写出写出GF(3GF(32 2)x 的的9 9个元素，并判断个元素，并判断1 1x是否为是否为GF(3GF(32 2)的本原元。的本原元。1 1x是是GF(3

11、GF(32 2)的本原元。的本原元。解：解：GF(3GF(32 2)x=Z=Z3 3 x/(/(x2 21)1)=a0 0a1 1x|a0 0，a1 1 Z Z3 3=0=0，1 1，2 2，x，1 1x，2 2x，2 2x，1 12 2x，2 22 2x。练习：找出其它所有本原元。练习：找出其它所有本原元。三密码学上的简单应用三密码学上的简单应用 设设f(x)是域是域Z Z2 2上一个上一个n次不可约多项式，次不可约多项式，则则GF(2GF(2n n)x=Z=Z2 2 x/(/(f(x)=a0 0a1 1xan1 1xn1 1|ai Z Z2 2。例例5 5：设：设f(x)=)=x3 3x1

12、 1为一个为一个3 3次不可约多项次不可约多项式，则式，则GF(2GF(23 3)x=0=0，1 1，x，x1 1，x2 2，x2 21 1，x2 2x，x2 2x11。若若x为为GF(2GF(23 3)的一个本原元，则的一个本原元，则GF(2GF(23 3)x=0=0，1 1，x，x2 2，x3 3，x4 4，x5 5，x6 6。的的乘乘法法比比较较Z Z与与G GF Fnn221)(若记若记0=000=00=000=0，1=001=11=001=1，x=010=2=010=2，x1=011=31=011=3，x2 2=100=4=100=4，x2 21=101=51=101=5，x2 2x

13、=110=6=110=6，x2 2x1=111=71=111=7；则则GF(2GF(23 3)x=Z=Z2 2 x/(/(x3 3x1)1)乘法表如下：乘法表如下：1 12 23 34 45 56 67 71 11 12 23 34 45 56 67 72 22 24 46 63 31 17 75 53 33 36 65 57 74 41 12 24 44 43 37 76 62 25 51 15 55 51 14 42 27 73 36 66 66 67 71 15 53 32 24 47 77 75 52 21 16 64 43 3Z Z8 8=0=0，1 1，2 2，77乘法表乘法表1

14、12 23 34 45 56 67 71 11 12 23 34 45 56 67 72 22 24 46 60 02 24 46 63 33 36 61 14 47 72 25 54 44 40 04 40 04 40 04 45 55 52 27 74 41 16 63 36 66 64 42 20 06 64 42 27 77 76 65 54 43 32 21 1非零元素非零元素1 12 23 34 45 56 67 7在在Z Z8 8中的出现次数中的出现次数 4 48 84 412124 48 84 4在在GF(2GF(23 3)中的出现次数中的出现次数 7 77 77 77 77

15、77 77 7在在Z Z8 8中，非零元素中，非零元素2 2，4 4和和6 6无乘法逆元。无乘法逆元。在在GF(2GF(23 3)中，所有非零元素都有乘法逆元。中，所有非零元素都有乘法逆元。2 2有限域有限域GF(2GF(28 8)在在AESAES中的应用中的应用 高级加密标准（高级加密标准（AESAES）使用的有限域）使用的有限域GF(2GF(28 8)x=Z Z2 2 x/(/(m(x)，其中，其中m(x)=)=x8 8x4 4x3 3x1 1为不为不可约多项式。可约多项式。在在AESAES中，把每个字节（中，把每个字节（8 8比特）看成是有限域比特）看成是有限域GF(2GF(28 8)中

16、的元素。中的元素。字节字节b7 7b6 6b5 5b4 4b3 3b2 2b1 1b0 0对应的多项式为：对应的多项式为：b7 7x7 7b6 6x6 6b5 5x5 5b4 4x4 4b3 3x3 3b2 2x2 2b1 1xb0 0.加法：就是字节的异或运算。加法：就是字节的异或运算。两个多项式相加，结果是一个多项式，其系数是两个元素两个多项式相加，结果是一个多项式，其系数是两个元素中对应系数的模中对应系数的模2 2加加。64277642(1)(1)xxxxxxxxxx0101011110000011 1101010057834D多项式的形式：多项式的形式：二进制的形式：二进制的形式：十六

17、进制的形式：十六进制的形式：加法逆元加法逆元 对于有限域对于有限域GF(28)，选定不可约多项式，选定不可约多项式m(x)=x8+x4+x3+x+1，就可以进行以下运算。，就可以进行以下运算。642(1)xxxx的加法逆元是它本身。的加法逆元是它本身。乘法：先进行多项式相乘，再将结果模不可约多项式乘法：先进行多项式相乘，再将结果模不可约多项式m(x)=x8+x4+x3+x+1。13119865431mod()xxxxxxxxm x57 831C 例：例：6427(1)(1)mod()xxxxxxm x761xx乘法逆元乘法逆元 由于由于m(x)是不可约的，故是不可约的，故GF(28)中任一非零

18、元素都与中任一非零元素都与m(x)互素，从而有乘法逆元互素，从而有乘法逆元(即即模模m(x)的逆的逆)，这样，这样GF(28)中非零元中非零元素为除数的除法总是可以进行。素为除数的除法总是可以进行。任何系数在二元域任何系数在二元域GF(2)中并且次数小于中并且次数小于8的多项式的多项式b(x)，利用欧几里德算法可以计算利用欧几里德算法可以计算a(x)和和c(x)使得使得那么有那么有a(x)b(x)mod m(x)=1，这说明，这说明b(x)的逆元素为的逆元素为1()()mod()bxa xm x()()()()1a x b xc x m x例：用欧几里德算法求得例：用欧几里德算法求得GF(2G

19、F(28 8)中元素中元素5757的乘法逆元为的乘法逆元为BFBF。有限域有限域GF(28)上多项式计算上多项式计算323210a(x)=a x+a x+a x+a323210b(x)=b x+b x+b x+b3233221100a(x)+b(x)=(ab)x+(ab)x+(ab)x+(ab)定义定义：系数为：系数为GF(28)上的元素的多项式上的元素的多项式和和的加法为：的加法为：323210a(x)=a x+a x+a x+a323210b(x)=b x+b x+b x+bc(x)=a(x)b(x)=a(x)b(x)Mod M(x)定义定义：系数为：系数为GF(28)上的元素的多项式上的元素的多项式和和的乘法为的乘法为模模M(x)乘乘(用符号用符号 表示表示)：000321111032210322321033cbaaaacbaaaaaaaacbaaaacb4M(x)=x+1323210c(x)=c x+c x+c x+cAES中选择 ，则的系数用矩阵相乘表示如下:作业作业用GF(2)上的不可约多项式x4+x+1构造GF(24),找出一个本原元，并计算x2+x+1的逆。