信息安全數(shù)學(xué)基礎(chǔ)第一章

信息安全數(shù)學(xué)基礎(chǔ)1授課內(nèi)容

代數(shù)基礎(chǔ)群環(huán)域數(shù)論基礎(chǔ)整除與同余原根與素性檢測(cè)組合論移位寄存器序列2

1.2群的性質(zhì)

1.3正規(guī)子群與商群

1.4群的同態(tài)與同構(gòu)1.1群的定義第一章群

1.5置換群3

定義1

設(shè)M是一個(gè)非空集合,如果存在一個(gè)對(duì)應(yīng)規(guī)則f,使得對(duì)M中任意兩個(gè)元素a和b,在M中都有唯一確定的元素c與它們對(duì)應(yīng),則稱f為M上的一個(gè)代數(shù)運(yùn)算（二元運(yùn)算）,記作c=f(a,b)或簡(jiǎn)記為c=a·b.1.1群的定義-代數(shù)運(yùn)算一些基本代數(shù)運(yùn)算：（1）自然數(shù)集上的加法運(yùn)算；(減法？)（2）整數(shù)集上的加法、減法與乘法運(yùn)算；（3）有理數(shù)集上的加法、減法和乘法運(yùn)算；（4）非零有理數(shù)集上的乘法與除法運(yùn)算；（5）實(shí)數(shù)域上全體階方陣的集合上的矩陣的加法與乘法運(yùn)算。

41.1

群的定義-代數(shù)運(yùn)算定義2設(shè)是大于1的任意正整數(shù)，剩余類(lèi)集定義為

模的加法：模的乘法：在集合中定義如下兩種運(yùn)算：

51.1

群的定義-群的定義定義3設(shè)是一個(gè)非空集合，是上的一個(gè)代數(shù)運(yùn)算，如果該運(yùn)算滿足如下三條性質(zhì)：（1）結(jié)合律：（2）有單位元：（3）有逆元：對(duì)存在使得則稱為一個(gè)群（Group）61.1群的定義-群的定義進(jìn)一步，如果群還滿足如下的交換律：則稱為交換群(commutativegroup)。注1：群中的單位元是唯一的，一般用1表示。

注2：群中每一個(gè)元素的逆元是唯一的，記為。注3：交換群中代數(shù)運(yùn)算通常用表示，此時(shí)單位元稱為零元，記為0，逆元稱為負(fù)元，記為。71.1

群的定義-群的定義注4：由于群里結(jié)合律是滿足的，把元素a的n次連乘記為an（交換群也可記為na），稱為a的n次冪（或稱乘方）。注5：若(G,●)只滿足結(jié)合律，則稱G為半群；如果(G,●)滿足結(jié)合律且有單位元，則稱G為有單位元的半群。81.1

群的定義-群的例子例1整數(shù)加群，有理數(shù)加群，實(shí)數(shù)加群，復(fù)數(shù)加群。例2非零有理數(shù)乘法群，非零實(shí)數(shù)乘法群。例3

：自然數(shù)集合N＝{1，2，3，．．．}對(duì)于通常的加法封閉且滿足結(jié)合律，但不存在單位元和逆元，因此對(duì)于加法是半群不是群。91.1

群的定義-群的例子例4模的剩余類(lèi)加法群，模的剩余類(lèi)乘法群，其中當(dāng)n為素?cái)?shù)時(shí)，則。對(duì)已知的求整數(shù)x，使的問(wèn)題為離散對(duì)數(shù)問(wèn)題。當(dāng)n時(shí)素?cái)?shù)足夠大時(shí)（大于200位），這個(gè)問(wèn)題就遠(yuǎn)遠(yuǎn)超過(guò)人類(lèi)的目前計(jì)算能力。該問(wèn)題促進(jìn)了大素?cái)?shù)的研究，目前最大的素?cái)?shù)是243112609

-1(超過(guò)1200萬(wàn)位)，對(duì)超過(guò)1000萬(wàn)位的素?cái)?shù)，美國(guó)的電子基金會(huì)獎(jiǎng)勵(lì)10萬(wàn)美元。該問(wèn)題被應(yīng)用于：DH密鑰交換協(xié)議、ElGamal公鑰密碼算法、DSA數(shù)字簽名算法等101.1

群的定義-群的例子例5集合的元素不一定是數(shù)，下面是集合元素為二階方陣的例子：該集合對(duì)于矩陣的普通乘法是一個(gè)群，單位元是

111.1群的定義-群的例子例6

一般線性群：特殊線性群：

例7次對(duì)稱群：集合上全體置換關(guān)于置換的合成運(yùn)算構(gòu)成的群。121.1

群的定義-群的例子例8設(shè)D是一個(gè)非平方數(shù)，則集合：對(duì)于實(shí)數(shù)加法運(yùn)算構(gòu)成交換加群；對(duì)于實(shí)數(shù)乘法運(yùn)算不構(gòu)成群。13

1.2群的性質(zhì)

1.3正規(guī)子群與商群

1.4群的同態(tài)與同構(gòu)1.1群的定義第一章群

1.5置換群141.2群的性質(zhì)-群的階定義4如果一個(gè)群G中元素的個(gè)數(shù)是無(wú)限多個(gè)，則稱G是無(wú)限群；如果G中的元素個(gè)數(shù)是有限多個(gè)，則稱G是有限群，G中元素的個(gè)數(shù)稱為群的階，記為|G|。151.2群的性質(zhì)-元素的階定義5設(shè)為一個(gè)群，，如果存在正整數(shù)，使得，則稱為有限階元，否則稱為無(wú)限階元。當(dāng)為有限階元時(shí)，稱使得的最小正整數(shù)為元素的階。1）記為元素的階，則

2）記為元素的階，則a161.2群的性質(zhì)-群的分類(lèi)從元素個(gè)數(shù)來(lái)分：有限群與無(wú)限群從代數(shù)運(yùn)算的交換性來(lái)分：交換群與非交換群模的剩余類(lèi)加法群、乘法群，次對(duì)稱群等為有限群；一般線性群，特殊線性群，整數(shù)加群等為無(wú)限群。模的剩余類(lèi)加法群、乘法群，整數(shù)加群等為交換群；次對(duì)稱群，一般線性群和特殊線性群等為非交換群。171.2群的性質(zhì)-子群定義6設(shè)是一個(gè)群，是的非空子集，如果關(guān)于群的運(yùn)算也構(gòu)成一個(gè)群，那么稱是的子群，記為。群G至少有兩個(gè)子群：G本身；只包含單位元的子集{e}，它們稱為G的平凡子群，其他子群為真子群。例1.6整數(shù)加群是有理數(shù)加群的子群；非零有理數(shù)乘法群是非零實(shí)數(shù)乘法群的子群；例1.7特殊線性群是一般線性群的子群，即181.2群的性質(zhì)-子群定理1一個(gè)群G和它的一個(gè)子群H有：1）G的單位元和H的單位元是同一的；2）如果a

H，a

1是a在G中的逆元，則a

1

H．19上次課回顧定義3設(shè)是一個(gè)非空集合，是上的一個(gè)代數(shù)運(yùn)算，如果該運(yùn)算滿足如下三條性質(zhì)：（1）結(jié)合律：（2）有單位元：（3）有逆元：對(duì)存在使得則稱為一個(gè)群（Group）20上次課回顧定義6設(shè)是一個(gè)群，是的非空子集，如果關(guān)于群的運(yùn)算也構(gòu)成一個(gè)群，那么稱是的子群，記為。定理1一個(gè)群G和它的一個(gè)子群H有：1）G的單位元和H的單位元是同一的；2）如果a

H，a

1是a在G