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

本讲内容 一 域的特征 二 有限域的结构 三 密码学上的简单应用 一 域的特征 若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 1 4 利用不可约多项式构造有限域 记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 的加法和乘法的运算表简化 如下 01xx 1 001xx 1 110 x 1x xxx 101 x 1x 1x10 01xx 1 00000 101xx 1 x0 xx 11 x 10 x 11x 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 乘法表如下 1234567 11234567 22463175 33657412 44376251 55142736 66715324 77521643 Z8 0 1 2 7 乘法表 1234567 11234567 22460246 33614725 44040404 55274163 66420642 77654321 非零元素1234567 在Z8中的出现次数 48412484 在GF 23 中的出现次数 7 777777 在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 28 上的元素的多项式 和的加法为 定义 系数为GF 28 上的元素的多项式 和的乘法为 模M x 乘 用符号 表示 AES中选择 则 的系数用矩阵相乘表示如下 作业 用GF 2 上的不可约多项式x4 x 1构造GF 24 找出一个本原元 并计算x2 x 1的逆 。