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

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

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

1.2群的性質(zhì)

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

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

1.5置換群3

定義1

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

41.1

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

模的加法：模的乘法：在集合中定義如下兩種運算：

51.1

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

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

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

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

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

群的定義-群的例子例4模的剩余類加法群，模的剩余類乘法群，其中當n為素數(shù)時，則。對已知的求整數(shù)x，使的問題為離散對數(shù)問題。當n時素數(shù)足夠大時（大于200位），這個問題就遠遠超過人類的目前計算能力。該問題促進了大素數(shù)的研究，目前最大的素數(shù)是243112609

-1(超過1200萬位)，對超過1000萬位的素數(shù)，美國的電子基金會獎勵10萬美元。該問題被應(yīng)用于：DH密鑰交換協(xié)議、ElGamal公鑰密碼算法、DSA數(shù)字簽名算法等101.1

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

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

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

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

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

1.2群的性質(zhì)

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

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

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

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

H，a

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

1

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

H，a

1是a在G