信息安全數學基礎1授課內容

代數基礎群環域數論基礎整除與同余原根與素性檢測組合論移位寄存器序列2

1.2群的性質

1.3正規子群與商群

1.4群的同態與同構1.1群的定義第一章群

1.5置換群3

定義1

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

41.1

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

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

51.1

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

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

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

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

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

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

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

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

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

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

例7次對稱群：集合上全體置換關于置換的合成運算構成的群。121.1

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

1.2群的性質

1.3正規子群與商群

1.4群的同態與同構1.1群的定義第一章群

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

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

H，a

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

1

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

H，a

1是a在G