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

1、信息安全数学基础环和域基础知识第1页，共48页，2022年，5月20日，0点39分，星期一环的定义环(Ring) : 一个非空集合S上有两种运算：加法“+”和乘法“”，如果这两种运算满足以下性质，就称为环：(R, +)是一个交换群，加法单位元记为0（称为零元）；R关于乘法“”满足结合律: (ab) c=a (bc), 并有单位元, 记为1；分配律成立: (a+b) c=ac+bc, c (a+b)=ca+cb. 注： 0是抽象的写法，不同于整数中的0. “+”和“”是抽象的运算第2页，共48页，2022年，5月20日，0点39分，星期一环的例子（1）在通常的加法和乘法运算下，Z, Q, R 和

2、 C都是环，加法单位元为0，乘法单位元为1。第3页，共48页，2022年，5月20日，0点39分，星期一环的例子（2）对任意n0，在模n加法和模n乘法下，Zn是一个环。加法单位元为0，乘法单位元为1。第4页，共48页，2022年，5月20日，0点39分，星期一环的例子 (3)多项式环 Zx第5页，共48页，2022年，5月20日，0点39分，星期一环中的零元对于环中的任意元素a, 都有0a=a0=0一般地，0与1不相等，否则1a=a, 而0a=0，这表明环中只有一个元素，平凡情形，一般不考虑所以0关于乘法没有可逆元第6页，共48页，2022年，5月20日，0点39分，星期一环的几个性质设R是一

3、个环, a,b R, 有:a(-b)=(-a)b=-(ab)(-a)(-b)=ab 第7页，共48页，2022年，5月20日，0点39分，星期一交换环 类似于交换群的定义，如果一个环关于乘 法运算具有可交换性，就称它为交换环。第8页，共48页，2022年，5月20日，0点39分，星期一无零因子环设R是一个环, 如果存在a,bR, a0, b0, 但ab=0, 那么称R是有零因子环, 否则称R是无零因子环.ab=0 a=0或b=0.第9页，共48页，2022年，5月20日，0点39分，星期一无零因子环的性质性质1. 设R是无零因子环, 那么若a0, ab=ac, 则b=c;若a0, ba=ca,

4、 则b=c.性质2. 设R是无零因子环, 那么R中非零元的加法阶相等, 或者为, 或者为素数.第10页，共48页，2022年，5月20日，0点39分，星期一子环、理想和商环第11页，共48页，2022年，5月20日，0点39分，星期一子环(subring)设R是一个环, S是R的非空子集, 如果S关于R的运算也构成环, 则称S是R的子环.第12页，共48页，2022年，5月20日，0点39分，星期一理想(Ideal)设R是一个环, I是R的一个子环, 如果a I , rR, 有ra R, ar R, 则称I是R的一个理想.第13页，共48页，2022年，5月20日，0点39分，星期一理想的例子

5、Fx为数域F上的一元多项式环, I=a1x+a2x2+anxn|aiF, n N, 即I是由所有常数项为0的多项式构成的集合, 则I是Fx的理想.第14页，共48页，2022年，5月20日，0点39分，星期一主理想由R中一个元素a生成的理想称为主理想.第15页，共48页，2022年，5月20日，0点39分，星期一商环设I是环R的理想, 在加法商群R/I上定义如下乘法 (x+I)(y+I) = (x+y) +I 则R/I关于加法和乘法构成一个环.第16页，共48页，2022年，5月20日，0点39分，星期一环同态设R和R是两个环, f是R到R的一个映射, 如果a,bR, 均有 f(a+b)=f(

6、a)+f(b), f(ab)=f(a)f(b), 那么称f是R到R的环同态映射. 如果f是满射, 那么称R和R同态; 如果f是双射,那么称R和R同构.类似的有环同态基本定理第17页，共48页，2022年，5月20日，0点39分，星期一概念的类比群环正规子群理想循环群主理想商群商环第18页，共48页，2022年，5月20日，0点39分，星期一域的定义 域(Field) 非空集合F，若F中定义了加和乘两种运算，且满足：1) F关于加法构成阿贝尔群，加法恒等元记为02) F中所有非零元素对乘法构成阿贝尔群，乘法恒等元记为13) 加法和乘法之间满足分配律则F与这两种运算构成域每一个非零元都是可逆元的有

7、单位元的交换环如实数域复数域有理数域第19页，共48页，2022年，5月20日，0点39分，星期一域的例子（1） 在通常的加法和乘法运算下，Q, R 和 C 都是域。第20页，共48页，2022年，5月20日，0点39分，星期一域的例子（2） 令p是一个素数，在模p加法和模p乘法 运算下，Zp是一个域. 也记为Fp或者GF (p).第21页，共48页，2022年，5月20日，0点39分，星期一 注意： 整数环Z不是域； 当n是合数时，Zn不是域。 有限群、子群、商群和群的阶的概念可 以直接推广到环和域中。第22页，共48页，2022年，5月20日，0点39分，星期一域的特征F是域，其特征cha

8、r(F)定义为单位元1的加法阶, 即使得 的最小自然数n，如果不存在这样的自然数，那么记char(F) =. 性质：如果char(F)有限，那么一定是素数.第23页，共48页，2022年，5月20日，0点39分，星期一域的例子（3）第24页，共48页，2022年，5月20日，0点39分，星期一构造方法 域上的多项式环不可约多项式第25页，共48页，2022年，5月20日，0点39分，星期一利用不可约多项式构造有限域Z ZpFx Fx/f(x)Fp=Zpp为素数F为p阶有限域f 为n次不可约多项式Fx/f(x)为pn阶有限域第26页，共48页，2022年，5月20日，0点39分，星期一域上的多项

9、式的带余除法 设F是一个域，f, g是Fx中的两个多项式，且g不为0，类似于整数的除法： f=gq+r， 其中，q, r是Fx中的两个多项式，且deg(r)deg(g). 第27页，共48页，2022年，5月20日，0点39分，星期一带余除法的例子 f(x)=x5+x4+x3+x2+x+1F2x g(x)=x3+x+1F2x q=x2+x, r=x2+1第28页，共48页，2022年，5月20日，0点39分，星期一不可约多项式 定义:设F是一个域，f(x) Fx, f(x)的次数为正数，若f(x)=g(x)h(x)，其中f(x) ,h(x) Fx, 则g(x)和h(x)中必有一个为常数多项式,

10、 那么称f(x)是不可约的.第29页，共48页，2022年，5月20日，0点39分，星期一 注意： 多项式的可约性依赖于该多项式定义在什么样的代数结构上. 一个多项式在一种代数结构上不可约，但可能在另一种代数结构上就是可约的. 第30页，共48页，2022年，5月20日，0点39分，星期一例 对于二次多项式f(x)=x2 - 2x+2：.（1）在复数域上可约；（2）在实数域上不可约；（3）在F3上不可约.第31页，共48页，2022年，5月20日，0点39分，星期一利用不可约多项式构造域定义: Fx是域F上的多项式环, f,g,rFx, g0, 满足f = gq + r, deg(r)deg(

11、g), 称r为f除以g的余式, 记为rf (mod g).考虑Fx中所有多项式模g(x)的余式, 将这些集合称为Fx模g(x)的多项式, 记为Fx/g(x).第32页，共48页，2022年，5月20日，0点39分，星期一利用不可约多项式构造域 令F是一个域，f(x)是Fx中的一个非零多项式，那么Fx/f(x)是一个环，当且仅当 f(x)在F上不可约时， Fx/f(x)是一个域. 第33页，共48页，2022年，5月20日，0点39分，星期一 f(x)是Fx中的一个不可约多项式， 当F是域时， Fx/f(x)是一个域. 将f(x)称为域Fx/f(x)的定义多项式. 第34页，共48页，2022年

12、，5月20日，0点39分，星期一定理 令F为含有p个元素的域，f(x)是F上的n次不可约多项式，那么域Fx/f(x)中元素的个数是pn. Fx/f(x)是Fx中所有次数小于deg(f)=n、系数取遍F中所有p个元素的多项式全体构成的集合. 共有pn个这样的多项式. 第35页，共48页，2022年，5月20日，0点39分，星期一 注意：在此定理中，并没有假设p是素数，事实上，F可以是任意域，称Fx/f(x)为由基域F通过域扩张得到的扩域. 第36页，共48页，2022年，5月20日，0点39分，星期一Pn 阶域的存在性Zp是阶为p的域；对任意的有限域F和任意的正整数n，Fx中一定存在n次不可约多

13、项式. 推论 对于每一个素数p和每一个正整数n，都存在一个阶为pn的有限域. 第37页，共48页，2022年，5月20日，0点39分，星期一域Fpx/f(x)中结构是很清楚的，它仅是所有次数小于n、系数在Fp的所有多项式的集合；在同构的意义下，这是唯一的阶为pn的有限域. 第38页，共48页，2022年，5月20日，0点39分，星期一第39页，共48页，2022年，5月20日，0点39分，星期一例：由GF(2)上的既约多项式p(x)= x4+x+1扩成GF(24)4位向量形式 多项式形式 生成元幂形式 指数形式 0000 0 0 - 0001 1 a0 0 0010 x a1 1 0100 x

14、2 a2 2 1000 x3 a3 3 0011 x+1 a4 4 0110 x2 +x a5 5 1100 x3 +x2 a6 6第40页，共48页，2022年，5月20日，0点39分，星期一4位向量形式 多项式形式 生成元幂形式 指数形式 1011 x3+x+1 a7 7 0101 x2+1 a8 8 1010 x3 +x a9 9 0100 x2 a10 10 0111 x2+x+1 a11 11 1110 x3+x2+x a12 12 1111 x3+x2 +x+1 a13 13 1101 x3 +x2+1 a14 14 1001 x3+1 a15 15第41页，共48页，2022年，5月20日，0点39分，星期一例子(1)实数域: R不可约多项式 f(x) = x2+1Rx/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) (mod f(x)第42页，共48页，2022年，5月20日，0点39分，星期一Rx/f(x) Cax+b ai+b第43页，共48页，2022年，5月20日，0点39分，星期一求逆 g(x)=ax+b (a0