信息安全數(shù)學(xué)基礎(chǔ)環(huán)和域基礎(chǔ)知識(shí)第一頁(yè)，共四十八頁(yè)，編輯于2023年，星期六環(huán)的定義環(huán)(Ring)

:一個(gè)非空集合S上有兩種運(yùn)算：加法“+”和乘法“°”，如果這兩種運(yùn)算滿足以下性質(zhì)，就稱為環(huán)：(R,+)是一個(gè)交換群，加法單位元記為0（稱為零元）；R關(guān)于乘法“°”滿足結(jié)合律:(a°b)°c=a°(b°c),并有單位元,記為1；分配律成立:(a+b)°c=a°c+b°c,c°(a+b)=c°a+c°b.注：0是抽象的寫法，不同于整數(shù)中的0.

“+”和“°”是抽象的運(yùn)算第二頁(yè)，共四十八頁(yè)，編輯于2023年，星期六環(huán)的例子（1）在通常的加法和乘法運(yùn)算下，Z,Q,R和C都是環(huán)，加法單位元為0，乘法單位元為1。第三頁(yè)，共四十八頁(yè)，編輯于2023年，星期六環(huán)的例子（2）對(duì)任意n>0，在模n加法和模n乘法下，Zn是一個(gè)環(huán)。加法單位元為0，乘法單位元為1。第四頁(yè)，共四十八頁(yè)，編輯于2023年，星期六環(huán)的例子(3)多項(xiàng)式環(huán)Z[x]第五頁(yè)，共四十八頁(yè)，編輯于2023年，星期六環(huán)中的零元對(duì)于環(huán)中的任意元素a,都有0a=a0=0一般地，0與1不相等，否則1a=a,而0a=0，這表明環(huán)中只有一個(gè)元素，平凡情形，一般不考慮所以0關(guān)于乘法沒有可逆元第六頁(yè)，共四十八頁(yè)，編輯于2023年，星期六環(huán)的幾個(gè)性質(zhì)設(shè)R是一個(gè)環(huán),?a,b∈R,有:a(-b)=(-a)b=-(ab)(-a)(-b)=ab

第七頁(yè)，共四十八頁(yè)，編輯于2023年，星期六交換環(huán)

類似于交換群的定義，如果一個(gè)環(huán)關(guān)于乘法運(yùn)算具有可交換性，就稱它為交換環(huán)。第八頁(yè)，共四十八頁(yè)，編輯于2023年，星期六無(wú)零因子環(huán)設(shè)R是一個(gè)環(huán),如果存在a,b∈R,a≠0,b≠0,但ab=0,那么稱R是有零因子環(huán),否則稱R是無(wú)零因子環(huán).ab=0?a=0或b=0.第九頁(yè)，共四十八頁(yè)，編輯于2023年，星期六無(wú)零因子環(huán)的性質(zhì)性質(zhì)1.設(shè)R是無(wú)零因子環(huán),那么若a≠0,ab=ac,則b=c;若a≠0,ba=ca,則b=c.性質(zhì)2.設(shè)R是無(wú)零因子環(huán),那么R中非零元的加法階相等,或者為∞,或者為素?cái)?shù).第十頁(yè)，共四十八頁(yè)，編輯于2023年，星期六子環(huán)、理想和商環(huán)第十一頁(yè)，共四十八頁(yè)，編輯于2023年，星期六子環(huán)(subring)設(shè)R是一個(gè)環(huán),S是R的非空子集,如果S關(guān)于R的運(yùn)算也構(gòu)成環(huán),則稱S是R的子環(huán).第十二頁(yè)，共四十八頁(yè)，編輯于2023年，星期六理想(Ideal)設(shè)R是一個(gè)環(huán),I是R的一個(gè)子環(huán),

如果?a∈I,

r∈R,有ra∈R,ar∈R,則稱I是R的一個(gè)理想.第十三頁(yè)，共四十八頁(yè)，編輯于2023年，星期六理想的例子F[x]為數(shù)域F上的一元多項(xiàng)式環(huán),I={a1x+a2x2+…+anxn|ai∈F,n∈N},

即I是由所有常數(shù)項(xiàng)為0的多項(xiàng)式構(gòu)成的集合,

則I是F[x]的理想.第十四頁(yè)，共四十八頁(yè)，編輯于2023年，星期六主理想由R中一個(gè)元素a生成的理想稱為主理想.第十五頁(yè)，共四十八頁(yè)，編輯于2023年，星期六商環(huán)設(shè)I是環(huán)R的理想,在加法商群R/I上定義如下乘法(x+I)(y+I)=(x+y)+I

則R/I關(guān)于加法和乘法構(gòu)成一個(gè)環(huán).第十六頁(yè)，共四十八頁(yè)，編輯于2023年，星期六環(huán)同態(tài)設(shè)R和R’是兩個(gè)環(huán),f是R到R’的一個(gè)映射,如果?a,b∈R,均有f(a+b)=f(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)基本定理第十七頁(yè)，共四十八頁(yè)，編輯于2023年，星期六概念的類比群環(huán)正規(guī)子群理想循環(huán)群主理想商群商環(huán)第十八頁(yè)，共四十八頁(yè)，編輯于2023年，星期六域的定義

域(Field)

非空集合F，若F中定義了加和乘兩種運(yùn)算，且滿足：1)F關(guān)于加法構(gòu)成阿貝爾群，加法恒等元記為02)F中所有非零元素對(duì)乘法構(gòu)成阿貝爾群，乘法恒等元記為13)加法和乘法之間滿足分配律則F與這兩種運(yùn)算構(gòu)成域每一個(gè)非零元都是可逆元的有單位元的交換環(huán)如實(shí)數(shù)域\復(fù)數(shù)域\有理數(shù)域第十九頁(yè)，共四十八頁(yè)，編輯于2023年，星期六域的例子（1）

在通常的加法和乘法運(yùn)算下，Q,R和C

都是域。第二十頁(yè)，共四十八頁(yè)，編輯于2023年，星期六域的例子（2）

令p是一個(gè)素?cái)?shù)，在模p加法和模p乘法運(yùn)算下，Zp是一個(gè)域.

也記為Fp或者GF(p).第二十一頁(yè)，共四十八頁(yè)，編輯于2023年，星期六

注意：整數(shù)環(huán)Z不是域；當(dāng)n是合數(shù)時(shí)，Zn不是域。有限群、子群、商群和群的階的概念可以直接推廣到環(huán)和域中。第二十二頁(yè)，共四十八頁(yè)，編輯于2023年，星期六域的特征F是域，其特征char(F)定義為單位元1的加法階,即使得的最小自然數(shù)n，如果不存在這樣的自然數(shù)，那么記char(F)=∞.性質(zhì)：如果char(F)有限，那么一定是素?cái)?shù).第二十三頁(yè)，共四十八頁(yè)，編輯于2023年，星期六域的例子（3）第二十四頁(yè)，共四十八頁(yè)，編輯于2023年，星期六構(gòu)造方法

域上的多項(xiàng)式環(huán)不可約多項(xiàng)式第二十五頁(yè)，共四十八頁(yè)，編輯于2023年，星期六利用不可約多項(xiàng)式構(gòu)造有限域ZZpF[x]F[x]/f(x)Fp=Zpp為素?cái)?shù)F為p階有限域f為n次不可約多項(xiàng)式F[x]/f(x)為pn階有限域第二十六頁(yè)，共四十八頁(yè)，編輯于2023年，星期六域上的多項(xiàng)式的帶余除法

設(shè)F是一個(gè)域，f,g是F[x]中的兩個(gè)多項(xiàng)式，且g不為0，類似于整數(shù)的除法：

f=gq+r，其中，q,r是F[x]中的兩個(gè)多項(xiàng)式，且deg(r)<deg(g).第二十七頁(yè)，共四十八頁(yè)，編輯于2023年，星期六帶余除法的例子

f(x)=x5+x4+x3+x2+x+1∈F2[x]g(x)=x3+x+1∈F2[x]q=x2+x,r=x2+1第二十八頁(yè)，共四十八頁(yè)，編輯于2023年，星期六不可約多項(xiàng)式

定義:設(shè)F是一個(gè)域，f(x)∈F[x],f(x)的次數(shù)為正數(shù)，若f(x)=g(x)h(x)，其中f(x),h(x)∈F[x],則g(x)和h(x)中必有一個(gè)為常數(shù)多項(xiàng)式,那么稱f(x)是不可約的.第二十九頁(yè)，共四十八頁(yè)，編輯于2023年，星期六

注意：多項(xiàng)式的可約性依賴于該多項(xiàng)式定義在什么樣的代數(shù)結(jié)構(gòu)上.一個(gè)多項(xiàng)式在一種代數(shù)結(jié)構(gòu)上不可約，但可能在另一種代數(shù)結(jié)構(gòu)上就是可約的.第三十頁(yè)，共四十八頁(yè)，編輯于2023年，星期六例

對(duì)于二次多項(xiàng)式f(x)=x2-2x+2：.（1）在復(fù)數(shù)域上可約；（2）在實(shí)數(shù)域上不可約；（3）在F3上不可約.第三十一頁(yè)，共四十八頁(yè)，編輯于2023年，星期六利用不可約多項(xiàng)式構(gòu)造域定義:F[x]是域F上的多項(xiàng)式環(huán),f,g,r∈F[x],g≠0,滿足f=gq+r,deg(r)<deg(g),稱r為f除以g的余式,記為r≡f(modg).考慮F[x]中所有多項(xiàng)式模g(x)的余式,將這些集合稱為F[x]模g(x)的多項(xiàng)式,記為F[x]/g(x).第三十二頁(yè)，共四十八頁(yè)，編輯于2023年，星期六利用不可約多項(xiàng)式構(gòu)造域

令F是一個(gè)域，f(x)是F[x]中的一個(gè)非零多項(xiàng)式，那么F[x]/f(x)是一個(gè)環(huán)，當(dāng)且僅當(dāng)f(x)在F上不可約時(shí)，F(xiàn)[x]/f(x)是一個(gè)域.第三十三頁(yè)，共四十八頁(yè)，編輯于2023年，星期六

f(x)是F[x]中的一個(gè)不可約多項(xiàng)式，當(dāng)F是域時(shí)，F(xiàn)[x]/f(x)是一個(gè)域.將f(x)稱為域F[x]/f(x)的定義多項(xiàng)式.第三十四頁(yè)，共四十八頁(yè)，編輯于2023年，星期六定理

令F為含有p個(gè)元素的域，f(x)是F上的n次不可約多項(xiàng)式，那么域F[x]/f(x)中元素的個(gè)數(shù)是pn.F[x]/f(x)是F[x]中所有次數(shù)小于deg(f)=n、系數(shù)取遍F中所有p個(gè)元素的多項(xiàng)式全體構(gòu)成的集合.共有pn個(gè)這樣的多項(xiàng)式.第三十五頁(yè)，共四十八頁(yè)，編輯于2023年，星期六

注意：在此定理中，并沒有假設(shè)p是素?cái)?shù)，事實(shí)上，F(xiàn)可以是任意域，稱F[x]/f(x)為由基域F通過(guò)域擴(kuò)張得到的擴(kuò)域.第三十六頁(yè)，共四十八頁(yè)，編輯于2023年，星期六Pn階域的存在性Zp是階為p的域；對(duì)任意的有限域F和任意的正整數(shù)n，F(xiàn)[x]中一定存在n次不可約多項(xiàng)式.

推論

對(duì)于每一個(gè)素?cái)?shù)p和每一個(gè)正整數(shù)n，都存在一個(gè)階為pn的有限域.第三十七頁(yè)，共四十八頁(yè)，編輯于2023年，星期六域Fp[x]/f(x)中結(jié)構(gòu)是很清楚的，它僅是所有次數(shù)小于n、系數(shù)在Fp的所有多項(xiàng)式的集合；在同構(gòu)的意義下，這是唯一的階為pn的有限域.第三十八頁(yè)，共四十八頁(yè)，編輯于2023年，星期六第三十九頁(yè)，共四十八頁(yè)，編輯于2023年，星期六例：由GF(2)上的既約多項(xiàng)式p(x)=x4+x+1擴(kuò)成GF(24)4位向量形式多項(xiàng)式形式生成元冪形式指數(shù)形式

000000-∞00011a000010xa110100x2

a2

21000x3a330011x+1a440110x2+xa551100x3+x2a66第四十頁(yè)，共四十八頁(yè)，編輯于2023年，星期六4位向量形式多項(xiàng)式形式生成元冪形式指數(shù)形式

1011x3+x+1a770101x2+1a881010x3+xa990100x2

a10

100111x2+x+1

a11111110x3+x2+xa12121111x3+x2+x+1a13131101x3+x2+1