信息安全數學基礎--羣環域--怎麼判斷是不是循環羣?

信息安全數學基礎--羣環域--怎麼判斷是不是循環羣?

博主是初學信息安全數學基礎(整除+同餘+原根+羣環域),本意是想整理一些較難理解的定理、算法,加深記憶也方便日後查找;如果有錯,歡迎指正。

三個方法:

  • 1.定義

循環羣:設羣 G G G中任意元素都可以表示成某一固定元素 a a a的冪次, G = { a n ∣ n ∈ Z } , G=\{a^n|n\in Z\}, G={annZ}那麼稱 G G G爲循環羣, a a a爲羣 G G G的生成元,寫成 G = < a > G=<a> G=<a>
有一個例子,目前還不是很明白 ^ _ ^
在這裏插入圖片描述

  • 2.循環羣的子羣也是循環羣。

證明:假設循環羣 G = < a > , G=<a>, G=<a>,因爲 < e > <e> <e> < a > <a> <a>不需要證明,直接是循環羣,所以我們只需考慮那些非單位元 { e } \{e\} {e}、非羣 G G G本身的其他羣,假設子羣爲 H H H
s > 1 , s>1, s>1,是使得 a s ∈ H a^s\in H asH的最小數,我們只需證 H H H中的所有元素都可以用 a s a^s as的冪次來表示即可。
我們假設 a m a^m am H H H的任意元素,那麼 m = q ⋅ s + r , ∃ q , r ∈ Z , m=q·s+r,{\exists}q,r\in Z, m=qs+r,q,rZ,
我們有 a r = a m ⋅ ( a − q s ) = a m ⋅ ( ( a s ) q ) − 1 a^r=a^m·(a^{-qs})=a^m·((a^s)^q)^{-1} ar=am(aqs)=am((as)q)1

因爲 a s ∈ H , a^s\in H, asH,由羣的「封閉性」可知, ( a s ) q ∈ H (a^s)^q\in H (as)qH;又由羣的「單位元+逆元」可知, ( ( a s ) q ) − 1 ∈ H ((a^s)^q)^{-1}\in H ((as)q)1H,所以 a m ⋅ ( ( a s ) q ) − 1 ∈ H a^m·((a^s)^q)^{-1}\in H am((as)q)1H,即 a r ∈ H 。 a^r\in H。 arH
又因爲 s s s是使得 a s ∈ H a^s\in H asH的最小數,所以 r = 0 , a r = e r=0,a^r=e r=0,ar=e,即 m = q ⋅ s , a m = ( a s ) q m=q·s,a^m=(a^s)^q m=qs,am=(as)q,即任意 a m ∈ H a^m\in H amH都可以寫成 a s a^s as的冪次形式。

  • 3.素數階羣一定是循環羣,非單位元都是生成元。

假設素數階羣爲 G G G ∣ G ∣ = p , p |G|=p,p G=p,p爲素數。
任意元素 a ∈ G , a ≠ e a\in G,a\neq e aG,a=e,由之前信息安全數學基礎–羣環域–拉格朗日定理(關於羣的陪集)證過的 ∣ G ∣ = ∣ H ∣ ⋅ [ G : H ] |G|=|H|·[G:H] G=H[G:H]我們知道任意子羣 ∣ H ∣ |H| H與羣 ∣ G ∣ |G| G的階都是有整除關係的,即 ∣ H ∣ ∣ ∣ G ∣ |H|\mid |G| HG。根據羣的「封閉性」,我們知道 < a > <a> <a> G G G的子羣,所以有 ∣ < a > ∣ ∣ ∣ G ∣ = p |<a>|\mid |G|=p <a>G=p
又因爲 a ≠ e , → ∣ a ∣ ≠ 1 a\neq e,\rightarrow |a|\neq 1 a=e,a=1,所以 ∣ a ∣ = p |a|=p a=p,即 G = < a > G=<a> G=<a>

相關文章
相關標籤/搜索