＋ 0 1 x x＋1 ＋ · 0 1 x x＋1 ＋
0 0 1 x x＋1 ＋ 0 0 0 0 0
1 1 0 x＋1 ＋ x 1 0 1 x x＋1 ＋
x x x＋1 ＋ 0 1 x 0 x x＋1 ＋ 1
x＋1 ＋ x＋1 ＋ x 1 0 x＋1 ＋ 0 x＋1 ＋ 1 x
5．有限域的表示 ]/(f( ))简记为GF(p 将GF(pn)[ ]=Zp[x]/( (x))简记为GF( n)。 GF( )[x]=Z ]/( ))简记为GF( 为素数， = GF(q) GF(q) 设p为素数，q=pn，GF( )*是GF( )中非零元的 为素数 集合， GF(q) 集合，则（GF( )*，·）是q－1阶循环群。 ） － 阶循环群。 GF(q)的本原元， GF(q) 的生成元， 设β是GF( )的本原元，即β是GF( )*的生成元， － =1}。 GF(q) ={β 则GF( )*={β，β2，…，βq－2，βq－1=1}。 ， － GF(q)={0， GF( )={0，1，β，β2，…，βq－2}。 )={0 ， －
对于有限域GF(28) ，选定不可约多项式 选定不可约多项式m(x)=x8+x4+x3+x+1 对于有限域 就可以进行以下运算。 ，就可以进行以下运算。 ①加法：就是字节的异或运算。 加法：就是字节的异或运算。 两个多项式相加，结果是一个多项式， 两个多项式相加，结果是一个多项式，其系数是两个元素 中对应系数的模2 中对应系数的模2加。 多项式的形式： 多项式的形式：
求有限域F 的所有本原元。 例1：求有限域F5=Z5的所有本原元。 解：2和3是F5的本原元。 的本原元。 例2：求模14的原根。 求模14的原根。 14的原根 是模14的原根 解：3和11是模 的原根。 和 是模 的原根。 2. 域的同构 命题3 是一个域， chF=0， 命题3 设F是一个域，若chF=0，则F含有一个 与有理数域同构的子域； chF=p， 与有理数域同构的子域； 若chF=p，则F含有一个 Z/（ 同构的子域。 与Z/（p）同构的子域。
三．密码学上的简单应用
1 GF 2n)与 2n的 法 较 ． ( Z 乘 比
次不可约多项式， 设f(x)是域Z2上一个 次不可约多项式， ( )是域Z 上一个n次不可约多项式 )[x]=Z ]/( )) ]/(f( 则GF(2n)[ ]=Z2[x]/( (x)) ={a ＋ ＋ － － ={ 0＋a1x＋…＋an－1xn－1|ai∈Z2}。 )=x 例5：设f(x)= 3＋x＋1为一个3次不可约多项 ( )= ＋ 为一个3 )[x]={0 ]={0， 式，则GF(23)[ ]={0，1，x，x＋1，x2，x2＋1， ， ＋ x2＋x，x2＋x＋1}。 ， ＋1}。 的一个本原元， 若x为GF(23)的一个本原元，则 为 )[x]={0 ]={0， GF(23)[ ]={0，1，x，x2，x3，x4，x5，x6}。 ，
非零元素
在Z8中的出现次数
在GF(23)中的出现次数
1 4 7
2 8 7
3 4 7
4 12 7ຫໍສະໝຸດ 5 4 76 8 7
7 4 7
非零元素2 无乘法逆元。 在Z8中，非零元素2，4和6无乘法逆元。 所有非零元素都有乘法逆元。 在GF(23)中，所有非零元素都有乘法逆元。
有限域GF(2 AES中的应用 2．有限域GF(28)在AES中的应用 高级加密标准（AES）使用的有限域GF(2 )[x]= 高级加密标准（AES）使用的有限域GF(28)[ ]= ]/(m( )) 其中m( )= ))， )=x Z2[x]/( (x))，其中 (x)= 8＋x4＋x3＋x＋1为不 ]/( ＋ 可约多项式。 可约多项式。 在AES中，把每个字节（8比特）看成是有限域 AES中 把每个字节（ 比特） 中的元素。 GF(28)中的元素。 字节b 对应的多项式为： 字节 7b6b5b4b3b2b1b0对应的多项式为： b7x7＋b6x6＋b5x5＋b4x4＋b3x3＋b2x2＋b1x＋b0. ＋
· 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
={0， Z8={0，1，2，…，7}乘法表 ，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
已知x 上的不可约多项式， 例4：已知 2＋1是Z3上的不可约多项式，利用 该不可约多项式构造一个9阶有限域GF(3 )[x] 该不可约多项式构造一个9阶有限域GF(32)[ ]， 写出GF(3 )[x] 个元素，并判断1 写出GF(32)[ ]的9个元素，并判断1＋x是否为 是否为 的本原元。 GF(32)的本原元。 )[x]=Z ]/( ]/(x 解：GF(32)[ ]=Z3[x]/( 2＋1) ={a }={0， ={ 0＋a1x|a0，a1∈Z3}={0，1，2，x，1＋x， | ， ， 2＋x，2x，1＋2x，2＋2x}。 ， ， ， } 的本原元。 1＋x是GF(32)的本原元。 是 练习：找出其它所有本原元。 练习：找出其它所有本原元。
GF(p )[x] ]/(f( ))， 记GF( n)[ ] = Zp[x]/( (x))， ]/( )) ]={a 则GF(pn)[ ]={ 0＋a1x＋…＋an－1xn－1|ai∈Zp}， GF( )[x]={ ＋ ＋ － － 其系数的加法和乘法遵从模p的加法和乘法， 其系数的加法和乘法遵从模 的加法和乘法， 的加法和乘法 多项式的加法和乘法遵从模f( )的加法和乘法。 多项式的加法和乘法遵从模 (x)的加法和乘法。 例3：把a0＋a1x＋(x2＋x＋1)简记为 0＋a1x， ＋ ＋1)简记为a ， 简记为 ]/(x ]/( ＋1)的加法和乘法的运算表简化 则Z2[x]/( 2＋x＋1)的加法和乘法的运算表简化 如下： 如下：
3．有限域的结构 定理1 是一个特征为p的有限域 的有限域， 定理1：设F是一个特征为 的有限域，则F的元 素个数一定为p的一个幂 的一个幂p ≥1。 素个数一定为 的一个幂 n，n≥1。 ≥1 命题4 是一个含有q个元素的有限域 个元素的有限域， 命题4：设Fq是一个含有 个元素的有限域，对 任意正整数n， 上的n次不可约多项式一定存在 次不可约多项式一定存在。 任意正整数 ，Fq上的 次不可约多项式一定存在。 定理2 对任意素数p和任意正整数 和任意正整数n， 定理2：对任意素数 和任意正整数 ，一定存在 一个含有p 个元素的有限域。 一个含有 n个元素的有限域。
只含有限个元素的域称为有限域。 只含有限个元素的域称为有限域。 有限域的元素个数称为有限域的阶。 有限域的元素个数称为有限域的阶。 每个特征为零的域都是无限域。 每个特征为零的域都是无限域。 有限域的特征一定是素数。 有限域的特征一定是素数。 在特征是素数p的域F 下列等式成立： 在特征是素数 的域F中，下列等式成立： 的域 (a＋b)p=ap＋bp， ＋ ) (a－b)p=ap－bp，∀a，b∈F。 － ) ， ∈
是任意给定的一个素数， 是任一正整数 是任一正整数， 设p是任意给定的一个素数，n是任一正整数， 是任意给定的一个素数 次不可约多项式。 设f(x)是域Zp上一个 次不可约多项式。 ( )是域Z 上一个n次不可约多项式 GF(p ]/(f( ))的两种表示方法 GF( n)=Zp[x]/( (x))的两种表示方法： ]/( ))的两种表示方法： GF(p )={a =0， （1）GF( n)={ 0＋a1x＋…＋an－1xn－1|ai∈Zp，i=0， ＋ ＋ － － =0 1，…，n－1}。 ， －1}。 GF(q)的一个本原元， （2）设q=pn，β是GF( )的一个本原元，则 = GF(q)={0 )={0， GF( )={0，1，β，β2，…，βq－2}。 ， －
若记0=000=0，1=001=1， =010=2 =010=2， ＋ 若记0=000=0，1=001=1，x=010=2，x＋ 0=000=0 1=011=3， =100=4， 1=101=5， 1=011=3，x2=100=4，x2＋1=101=5，x2＋ x=110=6，x2＋x＋1=111=7； =110=6， =110=6 ＋1=111=7； )[x]= ]/(x 乘法表如下： 则GF(23)[ ]= Z2[x]/( 3＋x＋1)乘法表如下： ]/( ＋1)乘法表如下
4．利用不可约多项式构造有限域
是任意给定的一个素数， 是任一正整数 是任一正整数。 ( )是域Z 设p是任意给定的一个素数，n是任一正整数。令f(x)是域Zp 是任意给定的一个素数 上一个n次不可约多项式， ]/(f( ))是域 上一个 次不可约多项式，则Zp[x]/( (x))是域， 次不可约多项式 ]/( ))是域， ]/(f( ))={a ))|a Zp[x]/( (x))={ 0＋a1x＋…＋an－1xn－1＋(f(x))| i∈Zp}。 ]/( ))={ ＋ ＋ － － ( ))| ]/(f( ))共包含 域Zp[x]/( (x))共包含 n个元素。 ]/( ))共包含p 个元素。 ))简记为 把a0＋a1x＋…＋an－1xn－1＋(f(x))简记为： ＋ ＋ － － ( ))简记为： a0＋a1x＋…＋an－1xn－1。 ＋ ＋ － －
第11讲 有限域 讲
教师：李艳俊
本讲内容
一．域的特征 二．有限域的结构 三．密码学上的简单应用
一．域的特征
若R是无零因子环，则其加群中所有非零元的 是无零因子环， 阶相同，或是无限，或是一个素数。 阶相同，或是无限，或是一个素数。 是无零因子环，当其加群 加群中所有非零元的 设R是无零因子环，当其加群中所有非零元的 阶无限时，chR=0；当此阶为素数p时 chR=p。 阶无限时，chR=0；当此阶为素数 时，chR= 。 定义1 是域， 的单位元， (F，＋ ，＋) 定义1：设F是域，1是F的单位元，若1在(F，＋) 的阶数为无穷大，则称F的特征为0 (F，＋ ，＋) 的阶数为无穷大，则称F的特征为0；若1在(F，＋) 的阶数为素数p，则称F的特征为p。 的阶数为素数 ，则称F的特征为 。 域F的特征或是零，或是素数。 的特征或是零，或是素数。