信息安全數(shù)學(xué)基礎(chǔ)環(huán)和域基礎(chǔ)知識

1、信息安全數(shù)學(xué)基礎(chǔ)環(huán)和域基礎(chǔ)知識第1頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一環(huán)的定義環(huán)(Ring) : 一個非空集合S上有兩種運(yùn)算：加法“+”和乘法“”，如果這兩種運(yùn)算滿足以下性質(zhì)，就稱為環(huán)：(R, +)是一個交換群，加法單位元記為0（稱為零元）；R關(guān)于乘法“”滿足結(jié)合律: (ab) c=a (bc), 并有單位元, 記為1；分配律成立: (a+b) c=ac+bc, c (a+b)=ca+cb. 注： 0是抽象的寫法，不同于整數(shù)中的0. “+”和“”是抽象的運(yùn)算第2頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一環(huán)的例子（1）在通常的加法和乘法運(yùn)算下，Z, Q, R 和

2、 C都是環(huán)，加法單位元為0，乘法單位元為1。第3頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一環(huán)的例子（2）對任意n0，在模n加法和模n乘法下，Zn是一個環(huán)。加法單位元為0，乘法單位元為1。第4頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一環(huán)的例子 (3)多項(xiàng)式環(huán) Zx第5頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一環(huán)中的零元對于環(huán)中的任意元素a, 都有0a=a0=0一般地，0與1不相等，否則1a=a, 而0a=0，這表明環(huán)中只有一個元素，平凡情形，一般不考慮所以0關(guān)于乘法沒有可逆元第6頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一環(huán)的幾個性質(zhì)設(shè)R是一

3、個環(huán), a,b R, 有:a(-b)=(-a)b=-(ab)(-a)(-b)=ab 第7頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一交換環(huán) 類似于交換群的定義，如果一個環(huán)關(guān)于乘 法運(yùn)算具有可交換性，就稱它為交換環(huán)。第8頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一無零因子環(huán)設(shè)R是一個環(huán), 如果存在a,bR, a0, b0, 但ab=0, 那么稱R是有零因子環(huán), 否則稱R是無零因子環(huán).ab=0 a=0或b=0.第9頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一無零因子環(huán)的性質(zhì)性質(zhì)1. 設(shè)R是無零因子環(huán), 那么若a0, ab=ac, 則b=c;若a0, ba=ca,

4、 則b=c.性質(zhì)2. 設(shè)R是無零因子環(huán), 那么R中非零元的加法階相等, 或者為, 或者為素數(shù).第10頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一子環(huán)、理想和商環(huán)第11頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一子環(huán)(subring)設(shè)R是一個環(huán), S是R的非空子集, 如果S關(guān)于R的運(yùn)算也構(gòu)成環(huán), 則稱S是R的子環(huán).第12頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一理想(Ideal)設(shè)R是一個環(huán), I是R的一個子環(huán), 如果a I , rR, 有ra R, ar R, 則稱I是R的一個理想.第13頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一理想的例子

5、Fx為數(shù)域F上的一元多項(xiàng)式環(huán), I=a1x+a2x2+anxn|aiF, n N, 即I是由所有常數(shù)項(xiàng)為0的多項(xiàng)式構(gòu)成的集合, 則I是Fx的理想.第14頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一主理想由R中一個元素a生成的理想稱為主理想.第15頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一商環(huán)設(shè)I是環(huán)R的理想, 在加法商群R/I上定義如下乘法 (x+I)(y+I) = (x+y) +I 則R/I關(guān)于加法和乘法構(gòu)成一個環(huán).第16頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一環(huán)同態(tài)設(shè)R和R是兩個環(huán), f是R到R的一個映射, 如果a,bR, 均有 f(a+b)=f(

6、a)+f(b), f(ab)=f(a)f(b), 那么稱f是R到R的環(huán)同態(tài)映射. 如果f是滿射, 那么稱R和R同態(tài); 如果f是雙射,那么稱R和R同構(gòu).類似的有環(huán)同態(tài)基本定理第17頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一概念的類比群環(huán)正規(guī)子群理想循環(huán)群主理想商群商環(huán)第18頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一域的定義 域(Field) 非空集合F，若F中定義了加和乘兩種運(yùn)算，且滿足：1) F關(guān)于加法構(gòu)成阿貝爾群，加法恒等元記為02) F中所有非零元素對乘法構(gòu)成阿貝爾群，乘法恒等元記為13) 加法和乘法之間滿足分配律則F與這兩種運(yùn)算構(gòu)成域每一個非零元都是可逆元的有

7、單位元的交換環(huán)如實(shí)數(shù)域復(fù)數(shù)域有理數(shù)域第19頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一域的例子（1） 在通常的加法和乘法運(yùn)算下，Q, R 和 C 都是域。第20頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一域的例子（2） 令p是一個素數(shù)，在模p加法和模p乘法 運(yùn)算下，Zp是一個域. 也記為Fp或者GF (p).第21頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一 注意： 整數(shù)環(huán)Z不是域； 當(dāng)n是合數(shù)時，Zn不是域。 有限群、子群、商群和群的階的概念可 以直接推廣到環(huán)和域中。第22頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一域的特征F是域，其特征cha

8、r(F)定義為單位元1的加法階, 即使得 的最小自然數(shù)n，如果不存在這樣的自然數(shù)，那么記char(F) =. 性質(zhì)：如果char(F)有限，那么一定是素數(shù).第23頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一域的例子（3）第24頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一構(gòu)造方法 域上的多項(xiàng)式環(huán)不可約多項(xiàng)式第25頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一利用不可約多項(xiàng)式構(gòu)造有限域Z ZpFx Fx/f(x)Fp=Zpp為素數(shù)F為p階有限域f 為n次不可約多項(xiàng)式Fx/f(x)為pn階有限域第26頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一域上的多項(xiàng)

9、式的帶余除法 設(shè)F是一個域，f, g是Fx中的兩個多項(xiàng)式，且g不為0，類似于整數(shù)的除法： f=gq+r， 其中，q, r是Fx中的兩個多項(xiàng)式，且deg(r)deg(g). 第27頁，共48頁，2022年，5月20日，0點(diǎn)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點(diǎn)39分，星期一不可約多項(xiàng)式 定義:設(shè)F是一個域，f(x) Fx, f(x)的次數(shù)為正數(shù)，若f(x)=g(x)h(x)，其中f(x) ,h(x) Fx, 則g(x)和h(x)中必有一個為常數(shù)多項(xiàng)式,

10、 那么稱f(x)是不可約的.第29頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一 注意： 多項(xiàng)式的可約性依賴于該多項(xiàng)式定義在什么樣的代數(shù)結(jié)構(gòu)上. 一個多項(xiàng)式在一種代數(shù)結(jié)構(gòu)上不可約，但可能在另一種代數(shù)結(jié)構(gòu)上就是可約的. 第30頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一例 對于二次多項(xiàng)式f(x)=x2 - 2x+2：.（1）在復(fù)數(shù)域上可約；（2）在實(shí)數(shù)域上不可約；（3）在F3上不可約.第31頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一利用不可約多項(xiàng)式構(gòu)造域定義: Fx是域F上的多項(xiàng)式環(huán), f,g,rFx, g0, 滿足f = gq + r, deg(r)deg(

11、g), 稱r為f除以g的余式, 記為rf (mod g).考慮Fx中所有多項(xiàng)式模g(x)的余式, 將這些集合稱為Fx模g(x)的多項(xiàng)式, 記為Fx/g(x).第32頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一利用不可約多項(xiàng)式構(gòu)造域 令F是一個域，f(x)是Fx中的一個非零多項(xiàng)式，那么Fx/f(x)是一個環(huán)，當(dāng)且僅當(dāng) f(x)在F上不可約時， Fx/f(x)是一個域. 第33頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一 f(x)是Fx中的一個不可約多項(xiàng)式， 當(dāng)F是域時， Fx/f(x)是一個域. 將f(x)稱為域Fx/f(x)的定義多項(xiàng)式. 第34頁，共48頁，2022年

12、，5月20日，0點(diǎn)39分，星期一定理 令F為含有p個元素的域，f(x)是F上的n次不可約多項(xiàng)式，那么域Fx/f(x)中元素的個數(shù)是pn. Fx/f(x)是Fx中所有次數(shù)小于deg(f)=n、系數(shù)取遍F中所有p個元素的多項(xiàng)式全體構(gòu)成的集合. 共有pn個這樣的多項(xiàng)式. 第35頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一 注意：在此定理中，并沒有假設(shè)p是素數(shù)，事實(shí)上，F(xiàn)可以是任意域，稱Fx/f(x)為由基域F通過域擴(kuò)張得到的擴(kuò)域. 第36頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一Pn 階域的存在性Zp是階為p的域；對任意的有限域F和任意的正整數(shù)n，F(xiàn)x中一定存在n次不可約多

13、項(xiàng)式. 推論 對于每一個素數(shù)p和每一個正整數(shù)n，都存在一個階為pn的有限域. 第37頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一域Fpx/f(x)中結(jié)構(gòu)是很清楚的，它僅是所有次數(shù)小于n、系數(shù)在Fp的所有多項(xiàng)式的集合；在同構(gòu)的意義下，這是唯一的階為pn的有限域. 第38頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一第39頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一例：由GF(2)上的既約多項(xiàng)式p(x)= x4+x+1擴(kuò)成GF(24)4位向量形式 多項(xiàng)式形式 生成元冪形式 指數(shù)形式 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點(diǎn)39分，星期一4位向量形式 多項(xiàng)式形式 生成元冪形式 指數(shù)形式 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點(diǎn)39分，星期一例子(1)實(shí)數(shù)域: R不可約多項(xiàng)式 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點(diǎn)39分，星期一Rx/f(x) Cax+b ai+b第43頁，共48頁，2022年，5月20日，0點(diǎn)39分，星期一求逆 g(x)=ax+b (a0