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

《密码学数学基础第十一讲-有限域.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本讲内容一．域的特征二．有限域的结构三．密码学上的简单应用一．域的特征若R是无零因子环，则其加群中所有非零元的阶相同，或是无限，或是一个素数。设R是无零因子环，当其加群中所有非零元的阶无限时，chR=0；当此阶为素数p时，chR=p。域F的特征或是零，或是素数。定义1：设F是域，1是F的单位元，若1在(F，＋)的阶数为无穷大，则称F的特征为0；若1在(F，＋)的阶数为素数p，则称F的特征为p。只含有限个元素的域称为有限域。有限域的元素个数称为有限域的阶。每个特征为零的域都是无限域。有限域的特征一定是素数

2、。在特征是素数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、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阶的

4、Galois域。定理3：设Fq是一个含有q个元素的有限域，设p是一个素数，Zp={0，1，2，…，p－1},设f(x)是Zp上的一个n次不可约多项式。若

5、Fq

6、=pn，其中n≥2是一个整数，则Fq与Zp[x]/(f(x))同构。若

7、Fq

8、=p，则Fq与Zp同构。设p是任意给定的一个素数，n是任一正整数。令f(x)是域Zp上一个n次不可约多项式，则Zp[x]/(f(x))是域，Zp[x]/(f(x))={a0＋a1x＋…＋an－1xn－1＋(f(x))

9、aiZp}。域Zp[x]/(f(x))共包含pn个

10、元素。把a0＋a1x＋…＋an－1xn－1＋(f(x))简记为：a0＋a1x＋…＋an－1xn－1。4．利用不可约多项式构造有限域记GF(pn)[x]=Zp[x]/(f(x))，则GF(pn)[x]={a0＋a1x＋…＋an－1xn－1

11、aiZp}，其系数的加法和乘法遵从模p的加法和乘法，多项式的加法和乘法遵从模f(x)的加法和乘法。例3：把a0＋a1x＋(x2＋x＋1)简记为a0＋a1x，则Z2[x]/(x2＋x＋1)的加法和乘法的运算表简化如下：＋01xx＋1001xx＋1110x＋1xxxx＋1

12、01x＋1x＋1x10·01xx＋100000101xx＋1x0xx＋11x＋10x＋11x5．有限域的表示设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次不

13、可约多项式。GF(pn)=Zp[x]/(f(x))的两种表示方法：（1）GF(pn)={a0＋a1x＋…＋an－1xn－1

14、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)

15、={a0＋a1x

16、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

17、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(2