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

第11讲 有限域,教师：李艳俊,本讲内容,一．域的特征 二．有限域的结构 三．密码学上的简单应用,一．域的特征,若R是无零因子环，则其加群中所有非零元的阶相同，或是无限，或是一个素数设R是无零因子环，当其加群中所有非零元的阶无限时，chR=0；当此阶为素数p时，chR=p域F的特征或是零，或是素数定义1：设F是域，1是F的单位元，若1在(F，＋)的阶数为无穷大，则称F的特征为0；若1在(F，＋)的阶数为素数p，则称F的特征为p只含有限个元素的域称为有限域有限域的元素个数称为有限域的阶每个特征为零的域都是无限域有限域的特征一定是素数在特征是素数p的域F中，下列等式成立：,(a＋b)p=ap＋bp，,(a－b)p=ap－bp，a，bF二．有限域的结构,有限域F中非零元组成的集合F*关于乘法做成的群称为有限域的乘法群命题1：设Fq是一个含有q个元素的有限域，Fq*=Fq\{0}，则Fq的乘法群Fq*是一个循环群定义2：设Fq是一个有限域，Fq*=Fq\{0}，Fq*的生成元称为Fq的本原元命题2：设Fq是一个含有q个元素的有限域，则Fq中共有(q－1)个本原元1．有限域的乘法群,例1：求有限域F5=Z5的所有本原元。

解：2和3是F5的本原元例2：求模14的原根解：3和11是模14的原根命题3 设F是一个域，若chF=0，则F含有一个与有理数域同构的子域； 若chF=p，则F含有一个与Z/（p）同构的子域2. 域的同构,3．有限域的结构,定理1：设F是一个特征为p的有限域，则F的元素个数一定为p的一个幂pn，n≥1定理2：对任意素数p和任意正整数n，一定存在一个含有pn个元素的有限域命题4：设Fq是一个含有q个元素的有限域，对任意正整数n，Fq上的n次不可约多项式一定存在将阶为pn的有限域记作GF(pn)，称之为pn阶的 Galois域定理3：设Fq是一个含有q个元素的有限域，设p是一个素数，Zp={0，1，2，…，p－1},设f(x)是Zp上的一个n次不可约多项式若|Fq|=pn，其中n≥2是一个整数，则Fq与Zp[x]/(f(x))同构若|Fq|=p，则Fq与Zp同构设p是任意给定的一个素数，n是任一正整数令f(x)是域Zp上一个n次不可约多项式，则Zp[x]/(f(x))是域， Zp[x]/(f(x))={a0＋a1x＋…＋an－1xn－1＋(f(x))|aiZp}域Zp[x]/(f(x))共包含pn个元素。

把a0＋a1x＋…＋an－1xn－1＋(f(x))简记为： a0＋a1x＋…＋an－1xn－14．利用不可约多项式构造有限域,记GF(pn)[x] = Zp[x]/(f(x))，,则GF(pn)[x]={a0＋a1x＋…＋an－1xn－1|aiZp}， 其系数的加法和乘法遵从模p的加法和乘法， 多项式的加法和乘法遵从模f(x)的加法和乘法例3：把a0＋a1x＋(x2＋x＋1)简记为a0＋a1x，则Z2[x]/(x2＋x＋1)的加法和乘法的运算表简化如下：,5．有限域的表示,设p为素数，q=pn，GF(q)*是GF(q)中非零元的集合，则（GF(q)*，·）是q－1阶循环群将GF(pn)[x]=Zp[x]/(f(x))简记为GF(pn)设是GF(q)的本原元，即是GF(q)*的生成元， 则GF(q)*={，2，…，q－2，q－1=1}GF(q)={0，1，，2，…，q－2}设p是任意给定的一个素数，n是任一正整数， 设f(x)是域Zp上一个n次不可约多项式GF(pn)=Zp[x]/(f(x))的两种表示方法：,（1）GF(pn)={a0＋a1x＋…＋an－1xn－1|aiZp，i=0，1，…，n－1}。

2）设q=pn，是GF(q)的一个本原元，则GF(q)={0，1，，2，…，q－2}例4：已知x2＋1是Z3上的不可约多项式，利用 该不可约多项式构造一个9阶有限域GF(32)[x]， 写出GF(32)[x]的9个元素，并判断1＋x是否为 GF(32)的本原元1＋x是GF(32)的本原元解：GF(32)[x]=Z3[x]/(x2＋1) ={a0＋a1x|a0，a1Z3}={0，1，2，x，1＋x，2＋x，2x，1＋2x，2＋2x}练习：找出其它所有本原元三．密码学上的简单应用,设f(x)是域Z2上一个n次不可约多项式， 则GF(2n)[x]=Z2[x]/(f(x)) ={a0＋a1x＋…＋an－1xn－1|aiZ2}例5：设f(x)=x3＋x＋1为一个3次不可约多项式，则GF(23)[x]={0，1，x，x＋1，x2，x2＋1，x2＋x，x2＋x＋1}若x为GF(23)的一个本原元，则GF(23)[x]={0，1，x，x2，x3，x4，x5，x6}若记0=000=0，1=001=1，x=010=2，x＋1=011=3，x2=100=4，x2＋1=101=5，x2＋x=110=6，x2＋x＋1=111=7；,则GF(23)[x]= Z2[x]/(x3＋x＋1)乘法表如下：,Z8={0，1，2，…，7}乘法表,在Z8中，非零元素2，4和6无乘法逆元。

在GF(23)中，所有非零元素都有乘法逆元2．有限域GF(28)在AES中的应用,高级加密标准（AES）使用的有限域GF(28)[x]= Z2[x]/(m(x))，其中m(x)=x8＋x4＋x3＋x＋1为不可约多项式在AES中，把每个字节（8比特）看成是有限域GF(28)中的元素字节b7b6b5b4b3b2b1b0对应的多项式为：,b7x7＋b6x6＋b5x5＋b4x4＋b3x3＋b2x2＋b1x＋b0.,①加法：就是字节的异或运算两个多项式相加，结果是一个多项式，其系数是两个元素中对应系数的模2加多项式的形式：,二进制的形式：,十六进制的形式：,②加法逆元,对于有限域GF(28) ，选定不可约多项式m(x)=x8+x4+x3+x+1，就可以进行以下运算的加法逆元是它本身③乘法：先进行多项式相乘，再将结果模不可约多项式m(x)=x8+x4+x3+x+1例：,④乘法逆元,由于m(x)是不可约的，故GF(28)中任一非零元素都与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)的逆元素为,例：用欧几里德算法求得GF(28)中元素57的乘法逆元为BF。

有限域GF(28)上多项式计算,作业,用GF(2)上的不可约多项式x4+x+1构造GF(24), 找出一个本原元，并计算x2+x+1的逆。