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

第11讲 有限域 教师：李艳俊 本讲内容 一．域的特征 二．有限域的结构 三．密码学上的简单应用 一．域的特征 二．有限域的结构 3．有限域的结构 将阶为pn的有限域记作GF(pn)，称之为pn阶的 Galois域。 设p是任意给定的一个素数，n是任一正整数。令f(x)是域Zp上一个n次不可约多项式，则Zp[x]/(f(x))是域， Zp[x]/(f(x))={a0＋a1x＋…＋an－1xn－1＋(f(x))|ai?Zp}。 记GF(pn)[x] = Zp[x]/(f(x))， 5．有限域的表示 例4：已知x2＋1是Z3上的不可约多项式，利用 该不可约多项式构造一个9阶有限域GF(32)[x]， 写出GF(32)[x]的9个元素，并判断1＋x是否为 GF(32)的本原元。 三．密码学上的简单应用 设f(x)是域Z2上一个n次不可约多项式， 则GF(2n)[x]=Z2[x]/(f(x)) ={a0＋a1x＋…＋an－1xn－1|ai?Z2}。 若记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； Z8={0，1，2，…，7}乘法表 2．有限域GF(28)在AES中的应用 有限域GF(28)上多项式计算 作业 * * 若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. 域的同构 定理1：设F是一个特征为p的有限域，则F的元素个数一定为p的一个幂pn，n≥1。 定理2：对任意素数p和任意正整数n，一定存在一个含有pn个元素的有限域。 命题4：设Fq是一个含有q个元素的有限域，对任意正整数n，Fq上的n次不可约多项式一定存在。 定理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同构。 域Zp[x]/(f(x))共包含pn个元素。 把a0＋a1x＋…＋an－1xn－1＋(f(x))简记为： a0＋a1x＋…＋an－1xn－1。 4．利用不可约多项式构造有限域 则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)的加法和乘法的运算表简化如下： 0 1 x x＋1 x＋1 1 0 x＋1 x x x x＋1 0 1 1 x＋1 x 1 0 0 x＋1 x 1 0 ＋ x 1 x＋1 0 x＋1 1 x＋1 x 0 x x＋1 x 1 0 1 0 0 0 0 0 x＋1 x 1 0 · 设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，…，