信息安全数学基础_环和域基础知识.ppt

信息安全数学基础 环和域 计算机科学与技术系王常远chywang128 13980688127184780948 环的定义 环 Ring 一个非空集合S上有两种运算 加法 和乘法 如果这两种运算满足以下性质 就称为环 R 是一个交换群 加法单位元记为0 称为零元 R关于乘法 满足结合律 a b c a b c 并有单位元 记为1 分配律成立 a b c a c b c c a b c a c b 注 0是抽象的写法 不同于整数中的0 和 是抽象的运算 环的例子 1 在通常的加法和乘法运算下 Z Q R和C都是环 加法单位元为0 乘法单位元为1 环的例子 2 对任意n 0 在模n加法和模n乘法下 Zn是一个环 加法单位元为0 乘法单位元为1 环的例子 3 多项式环Z x 环中的零元 对于环中的任意元素a 都有0a a0 0一般地 0与1不相等 否则1a a 而0a 0 这表明环中只有一个元素 平凡情形 一般不考虑所以0关于乘法没有可逆元 环的几个性质 设R是一个环 a b R 有 a b a b ab a b ab 交换环 类似于交换群的定义 如果一个环关于乘法运算具有可交换性 就称它为交换环 无零因子环 设R是一个环 如果存在a b R a 0 b 0 但ab 0 那么称R是有零因子环 否则称R是无零因子环 ab 0 a 0或b 0 无零因子环的性质 性质1 设R是无零因子环 那么若a 0 ab ac 则b c 若a 0 ba ca 则b c 性质2 设R是无零因子环 那么R中非零元的加法阶相等 或者为 或者为素数 子环 理想和商环 子环 subring 设R是一个环 S是R的非空子集 如果S关于R的运算也构成环 则称S是R的子环 理想 Ideal 设R是一个环 I是R的一个子环 如果 a I r R 有ra R ar R 则称I是R的一个理想 理想的例子 F x 为数域F上的一元多项式环 I a1x a2x2 anxn ai F n N 即I是由所有常数项为0的多项式构成的集合 则I是F x 的理想 主理想 由R中一个元素a生成的理想称为主理想 商环 设I是环R的理想 在加法商群R I上定义如下乘法 x I y I x y I则R I关于加法和乘法构成一个环 环同态 设R和R 是两个环 f是R到R 的一个映射 如果 a b R 均有f a b f a f b f ab f a f b 那么称f是R到R 的环同态映射 如果f是满射 那么称R和R 同态 如果f是双射 那么称R和R 同构 类似的有环同态基本定理 概念的类比 域的定义 域 Field 非空集合F 若F中定义了加和乘两种运算 且满足 1 F关于加法构成阿贝尔群 加法恒等元记为02 F中所有非零元素对乘法构成阿贝尔群 乘法恒等元记为13 加法和乘法之间满足分配律则F与这两种运算构成域每一个非零元都是可逆元的有单位元的交换环如实数域 复数域 有理数域 域的例子 1 在通常的加法和乘法运算下 Q R和C都是域 域的例子 2 令p是一个素数 在模p加法和模p乘法运算下 Zp是一个域 也记为Fp或者GF p 注意 整数环Z不是域 当n是合数时 Zn不是域 有限群 子群 商群和群的阶的概念可以直接推广到环和域中 域的特征 F是域 其特征char F 定义为单位元1的加法阶 即使得的最小自然数n 如果不存在这样的自然数 那么记char F 性质 如果char F 有限 那么一定是素数 域的例子 3 构造方法 域上的多项式环不可约多项式 利用不可约多项式构造有限域 ZZp F x F x f x Fp Zp p为素数 F为p阶有限域f为n次不可约多项式 F x f x 为pn阶有限域 域上的多项式的带余除法 设F是一个域 f g是F x 中的两个多项式 且g不为0 类似于整数的除法 f gq r 其中 q r是F x 中的两个多项式 且deg r deg g 带余除法的例子 f x x5 x4 x3 x2 x 1 F2 x g x x3 x 1 F2 x q x2 x r x2 1 不可约多项式 定义 设F是一个域 f x F x f x 的次数为正数 若f x g x h x 其中f x h x F x 则g x 和h x 中必有一个为常数多项式 那么称f x 是不可约的 注意 多项式的可约性依赖于该多项式定义在什么样的代数结构上 一个多项式在一种代数结构上不可约 但可能在另一种代数结构上就是可约的 例 对于二次多项式f x x2 2x 2 1 在复数域上可约 2 在实数域上不可约 3 在F3上不可约 利用不可约多项式构造域 定义 F x 是域F上的多项式环 f g r F x g 0 满足f gq r deg r deg g 称r为f除以g的余式 记为r f modg 考虑F x 中所有多项式模g x 的余式 将这些集合称为F x 模g x 的多项式 记为F x g x 利用不可约多项式构造域 令F是一个域 f x 是F x 中的一个非零多项式 那么F x f x 是一个环 当且仅当f x 在F上不可约时 F x f x 是一个域 f x 是F x 中的一个不可约多项式 当F是域时 F x f x 是一个域 将f x 称为域F x f x 的定义多项式 定理 令F为含有p个元素的域 f x 是F上的n次不可约多项式 那么域F x f x 中元素的个数是pn F x f x 是F x 中所有次数小于deg f n 系数取遍F中所有p个元素的多项式全体构成的集合 共有pn个这样的多项式 注意 在此定理中 并没有假设p是素数 事实上 F可以是任意域 称F x f x 为由基域F通过域扩张得到的扩域 Pn阶域的存在性 Zp是阶为p的域 对任意的有限域F和任意的正整数n F x 中一定存在n次不可约多项式 推论对于每一个素数p和每一个正整数n 都存在一个阶为pn的有限域 域Fp x f x 中结构是很清楚的 它仅是所有次数小于n 系数在Fp的所有多项式的集合 在同构的意义下 这是唯一的阶为pn的有限域 例 由GF 2 上的既约多项式p x x4 x 1扩成GF 24 4位向量形式多项式形式生成元幂形式指数形式 000000 00011a000010 xa110100 x2a221000 x3a330011x 1a440110 x2 xa551100 x3 x2a66 4位向量形式多项式形式生成元幂形式指数形式 1011x3 x 1a770101x2 1a881010 x3 xa990100 x2a10100111x2 x 1a11111110 x3 x2 xa12121111x3 x2 x 1a13131101x3 x2 1a14141001x3 1a1515 例子 1 实数域 R不可约多项式f x x2 1R x f x ax b cx d a c x b d ax b cx d acx2 ad bc x bd ad bc x bd ac modf x R x f x C ax b ai b 求逆g x ax b a 0 例子 2 二元域F