资源描述
,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第11讲 有限域,教师：李艳俊,1,本讲内容,一域的特征,二有限域的结构,三密码学上的简单应用,2,一域的特征,若R是无零因子环，则其加群中所有非零元的阶相同，或是无限，或是一个素数。,设R是无零因子环，当其,加群,中所有非零元的阶无限时，chR=0；当此阶为素数,p,时，chR=,p,。,域F的特征或是零，或是素数。,定义1：设F是域，1是F的单位元，若1在(F，)的阶数为无穷大，则称F的特征为0；若1在(F，)的阶数为素数,p,，则称F的特征为,p,。,3,只含有限个元素的域称为有限域。,有限域的元素个数称为有限域的阶。,每个特征为零的域都是无限域。,有限域的特征一定是素数。,在特征是素数,p,的域F中，下列等式成立：,(,a,b,),p,=,a,p,b,p,，,(,a,b,),p,=,a,p,b,p,，,a,，,b,F。,4,二有限域的结构,有限域F中非零元组成的集合F,*,关于乘法做成的群称为有限域的乘法群。,命题,1,：设,F,q,是一个含有,q,个元素的有限域，F,q,*,=F,q,0，则F,q,的乘法群F,q,*,是一个循环群。,定义,2,：,设,F,q,是一个有限域，F,q,*,=F,q,0，F,q,*,的生成元称为,F,q,的本原元。,命题,2,：设,F,q,是一个含有,q,个元素的有限域，则F,q,中共有,(,q,1),个本原元。,1有限域的乘法群,5,例1：求有限域F,5,=Z,5,的所有本原元。,解：2和3是F,5,的本原元。,例2：求模14的原根。,解：3和11是模14的原根。,命题3,设F是一个域，若chF=0，则F含有一个与有理数域同构的子域； 若chF=p，则F含有一个与Z/（p）同构的子域。,2. 域的同构,6,3,有限域的结构,定理1,：设F是一个特征为,p,的有限域，则F的元素个数一定为,p,的一个幂,p,n,，,n,1。,定理2,：对任意素数,p,和任意正整数,n,，一定存在一个含有,p,n,个元素的有限域。,命题4,：设F,q,是一个含有,q,个元素的有限域，对任意正整数,n,，F,q,上的,n,次不可约多项式一定存在。,7,将阶为,p,n,的有限域记作GF(,p,n,)，称之为,p,n,阶的,Galois域。,定理3,：设F,q,是一个含有,q,个元素的有限域，设,p,是一个素数，Z,p,=0，1，2，,p,1,设,f,(,x,)是Z,p,上的一个,n,次不可约多项式。若|F,q,|=,p,n,，其中,n,2是一个整数，则F,q,与Z,p,x,/(,f,(,x,)同构。若|F,q,|=,p,，则F,q,与Z,p,同构。,8,设,p,是任意给定的一个素数，,n,是任一正整数。令,f,(,x,)是域Z,p,上一个,n,次不可约多项式，则Z,p,x,/(,f,(,x,)是域，,Z,p,x,/(,f,(,x,)=,a,0,a,1,x,a,n,1,x,n,1,(,f,(,x,)|,a,i,Z,p,。,域Z,p,x,/(,f,(,x,)共包含,p,n,个元素。,把,a,0,a,1,x,a,n,1,x,n,1,(,f,(,x,)简记为：,a,0,a,1,x,a,n,1,x,n,1,。,4利用不可约多项式构造有限域,9,记GF(,p,n,),x, = Z,p,x,/(,f,(,x,)，,则GF(,p,n,),x,=,a,0,a,1,x,a,n,1,x,n,1,|,a,i,Z,p,，,其系数的加法和乘法遵从模,p,的加法和乘法，,多项式的加法和乘法遵从模,f,(,x,)的加法和乘法。,例3：把,a,0,a,1,x,(,x,2,x,1)简记为,a,0,a,1,x,，则Z,2,x,/(,x,2,x,1)的加法和乘法的运算表简化如下：,10,0,1,x,x,1,0,0,1,x,x,1,1,1,0,x,1,x,x,x,x,1,0,1,x,1,x,1,x,1,0,0,1,x,x,1,0,0,0,0,0,1,0,1,x,x,1,x,0,x,x,1,1,x,1,0,x,1,1,x,11,5有限域的表示,设,p,为素数，,q,=,p,n,，GF(,q,),*,是GF(,q,)中非零元的集合，则（GF(,q,),*,，）是,q,1阶循环群。,将GF(,p,n,),x,=Z,p,x,/(,f,(,x,)简记为GF(,p,n,)。,设,是GF(,q,)的本原元，即是GF(,q,),*,的生成元，,则GF(,q,),*,=，,2,，,q,2,，,q,1,=1。,GF(,q,)=0，1，,2,，,q,2,。,12,设,p,是任意给定的一个素数，,n,是任一正整数，,设,f,(,x,)是域Z,p,上一个,n,次不可约多项式。,GF(,p,n,)=Z,p,x,/(,f,(,x,)的两种表示方法：,（1）GF(,p,n,)=,a,0,a,1,x,a,n,1,x,n,1,|,a,i,Z,p,，,i,=0，1，,n,1。,（2）设,q,=,p,n,，,是GF(,q,)的一个本原元，则GF(,q,)=0，1，,2,，,q,2,。,13,例4：已知,x,2,1是Z,3,上的不可约多项式，利用,该不可约多项式构造一个9阶有限域GF(3,2,),x,，,写出GF(3,2,),x,的9个元素，并判断1,x,是否为,GF(3,2,)的本原元。,1,x,是GF(3,2,)的本原元。,解：GF(3,2,),x,=Z,3,x,/(,x,2,1),=,a,0,a,1,x,|,a,0,，,a,1,Z,3,=0，1，2，,x,，1,x,，2,x,，2,x,，12,x,，22,x,。,练习：找出其它所有本原元。,14,三密码学上的简单应用,设,f,(,x,)是域Z,2,上一个,n,次不可约多项式，,则GF(2,n,),x,=Z,2,x,/(,f,(,x,),=,a,0,a,1,x,a,n,1,x,n,1,|,a,i,Z,2,。,例5：设,f,(,x,)=,x,3,x,1为一个3次不可约多项式，则GF(2,3,),x,=0，1，,x,，,x,1，,x,2,，,x,2,1，,x,2,x,，,x,2,x,1。,若,x,为GF(2,3,)的一个本原元，则GF(2,3,),x,=0，1，,x,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,。,15,若记0=000=0，1=001=1，,x,=010=2，,x,1=011=3，,x,2,=100=4，,x,2,1=101=5，,x,2,x,=110=6，,x,2,x,1=111=7；,则,GF(2,3,),x,= Z,2,x,/(,x,3,x,1)乘法表如下：,1,2,3,4,5,6,7,1,1,2,3,4,5,6,7,2,2,4,6,3,1,7,5,3,3,6,5,7,4,1,2,4,4,3,7,6,2,5,1,5,5,1,4,2,7,3,6,6,6,7,1,5,3,2,4,7,7,5,2,1,6,4,3,16,Z,8,=0，1，2，7乘法表,1,2,3,4,5,6,7,1,1,2,3,4,5,6,7,2,2,4,6,0,2,4,6,3,3,6,1,4,7,2,5,4,4,0,4,0,4,0,4,5,5,2,7,4,1,6,3,6,6,4,2,0,6,4,2,7,7,6,5,4,3,2,1,17,非零元素,1,2,3,4,5,6,7,在Z,8,中的出现次数,4,8,4,12,4,8,4,在GF(2,3,)中的出现次数,7,7,7,7,7,7,7,在Z,8,中，非零元素2，4和6无乘法逆元。,在GF(2,3,)中，所有非零元素都有乘法逆元。,18,2有限域GF(2,8,)在AES中的应用,高级加密标准（AES）使用的有限域GF(2,8,),x,= Z,2,x,/(,m,(,x,)，其中,m,(,x,)=,x,8,x,4,x,3,x,1为不可约多项式。,在AES中，把每个字节（8比特）看成是有限域GF(2,8,)中的元素。,字节,b,7,b,6,b,5,b,4,b,3,b,2,b,1,b,0,对应的多项式为：,b,7,x,7,b,6,x,6,b,5,x,5,b,4,x,4,b,3,x,3,b,2,x,2,b,1,x,b,0,.,19,加法：就是字节的异或运算。,两个多项式相加，结果是一个多项式，其系数是两个元素中对应系数的模2加。,多项式的形式：,二进制的形式：,十六进制的形式：,加法逆元,对于有限域GF(2,8,) ，选定不可约多项式m(x)=x,8,+x,4,+x,3,+x+1，就可以进行以下运算。,的加法逆元是它本身。,20,乘法：先进行多项式相乘，再将结果模不可约多项式m(x)=x,8,+x,4,+x,3,+x+1。,例：,21,乘法逆元,由于m(x)是不可约的，故GF(2,8,)中任一非零元素都与m(x)互素，从而有乘法逆元(即,模m(x)的逆,)，这样GF(2,8,)中非零元素为除数的除法总是可以进行。,任何系数在二元域GF(2)中并且次数小于8的多项式b(x)，利用欧几里德算法可以计算,a,(x)和,c,(x)使得,那么有,a,(x),b,(x) mod,m,(x)= 1,，这说明,b,(x),的逆元素为,例：用欧几里德算法求得GF(2,8,)中元素57的乘法逆元为BF。,22,有限域GF(2,8,)上多项式计算,定义,：系数为GF(2,8,)上的元素的多项式,和,的加法为：,定义,：系数为GF(2,8,)上的元素的多项式,和,的乘法为,模M(x)乘(用符号,表示)：,23,AES中选择 ，则,的系数用矩阵相乘表示如下:,24,作业,用,GF,(2)上的不可约多项式,x,4,+,x,+1构造,GF,(2,4,), 找出一个本原元，并计算,x,2,+,x,+1的逆。,25,
展开阅读全文