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

-,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中，下列等式成立：,(ab)p=apbp，,(ab)p=apbp，a，bF。,-,4,二有限域的结构,有限域F中非零元组成的集合F*关于乘法做成的群称为有限域的乘法群。,命题1：设Fq是一个含有q个元素的有限域，Fq*=Fq0，则Fq的乘法群Fq*是一个循环群。,定义2：设Fq是一个有限域，Fq*=Fq0，Fq*的生成元称为Fq的本原元。,命题2：设Fq是一个含有q个元素的有限域，则Fq中共有(q1)个本原元。,1有限域的乘法群,-,5,例1：求有限域F5=Z5的所有本原元。,解：2和3是F5的本原元。,例2：求模14的原根。,解：3和11是模14的原根。,命题3设F是一个域，若chF=0，则F含有一个与有理数域同构的子域；若chF=p，则F含有一个与Z/（p）同构的子域。,2.域的同构,-,6,3有限域的结构,定理1：设F是一个特征为p的有限域，则F的元素个数一定为p的一个幂pn，n1。,定理2：对任意素数p和任意正整数n，一定存在一个含有pn个元素的有限域。,命题4：设Fq是一个含有q个元素的有限域，对任意正整数n，Fq上的n次不可约多项式一定存在。,-,7,将阶为pn的有限域记作GF(pn)，称之为pn阶的Galois域。,定理3：设Fq是一个含有q个元素的有限域，设p是一个素数，Zp=0，1，2，p1,设f(x)是Zp上的一个n次不可约多项式。若|Fq|=pn，其中n2是一个整数，则Fq与Zpx/(f(x)同构。若|Fq|=p，则Fq与Zp同构。,-,8,设p是任意给定的一个素数，n是任一正整数。令f(x)是域Zp上一个n次不可约多项式，则Zpx/(f(x)是域，Zpx/(f(x)=a0a1xan1xn1(f(x)|aiZp。,域Zpx/(f(x)共包含pn个元素。,把a0a1xan1xn1(f(x)简记为：a0a1xan1xn1。,4利用不可约多项式构造有限域,-,9,记GF(pn)x=Zpx/(f(x)，,则GF(pn)x=a0a1xan1xn1|aiZp，其系数的加法和乘法遵从模p的加法和乘法，多项式的加法和乘法遵从模f(x)的加法和乘法。,例3：把a0a1x(x2x1)简记为a0a1x，则Z2x/(x2x1)的加法和乘法的运算表简化如下：,-,10,-,11,5有限域的表示,设p为素数，q=pn，GF(q)*是GF(q)中非零元的集合，则（GF(q)*，）是q1阶循环群。,将GF(pn)x=Zpx/(f(x)简记为GF(pn)。,设是GF(q)的本原元，即是GF(q)*的生成元，则GF(q)*=，2，q2，q1=1。,GF(q)=0，1，2，q2。,-,12,设p是任意给定的一个素数，n是任一正整数，设f(x)是域Zp上一个n次不可约多项式。,GF(pn)=Zpx/(f(x)的两种表示方法：,（1）GF(pn)=a0a1xan1xn1|aiZp，i=0，1，n1。,（2）设q=pn，是GF(q)的一个本原元，则GF(q)=0，1，2，q2。,-,13,例4：已知x21是Z3上的不可约多项式，利用该不可约多项式构造一个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。,练习：找出其它所有本原元。,-,14,三密码学上的简单应用,设f(x)是域Z2上一个n次不可约多项式，则GF(2n)x=Z2x/(f(x)=a0a1xan1xn1|aiZ2。,例5：设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。,-,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)乘法表如下：,-,16,Z8=0，1，2，7乘法表,-,17,在Z8中，非零元素2，4和6无乘法逆元。,在GF(23)中，所有非零元素都有乘法逆元。,-,18,2有限域GF(28)在AES中的应用,高级加密标准（AES）使用的有限域GF(28)x=Z2x/(m(x)，其中m(x)=x8x4x3x1为不可约多项式。,在AES中，把每个字节（8比特）看成是有限域GF(28)中的元素。,字节b7b6b5b4b3b2b1b0对应的多项式为：,b7x7b6x6b5x5b4x4b3x3b2x2b1xb0.,-,19,加法：就是字节的异或运算。,两个多项式相加，结果是一个多项式，其系数是两个元素中对应系数的模2加。,多项式的形式：,二进制的形式：,十六进制的形式：,加法逆元,对于有限域GF(28)，选定不可约多项式m(x)=x8+x4+x3+x+1，就可以进行以下运算。,的加法逆元是它本身。,-,20,乘法：先进行多项式相乘，再将结果模不可约多项式m(x)=x8+x4+x3+x+1。,例：,-,21,乘法逆元,由于m(x)是不可约的，故GF(28)中任一非零元素都与m(x)互素，从而有乘法逆元(即模m(x)的逆)，这样GF(28)中非零元素为除数的除法总是可以进行。,任何系数在二元域GF(2)中并且次数小于8的多项式b(x)，利用欧几里德算法可以计算a(x)和c(x)使得,那么有a(x)b(x)mod