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

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

三個方法：

• 1.定義

循環羣：設羣 G G G中任意元素都可以表示成某一固定元素 a a a的冪次， G = { a n ∣ n ∈ Z } ， G=\{a^n|n\in Z\}， G={an∣n∈Z}，那麼稱 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 as∈H的最小數，我們只需證 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=q⋅s+r,∃q,r∈Z,
我們有 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⋅(a−qs)=am⋅((as)q)−1
因爲 a s ∈ H , a^s\in H, as∈H,由羣的「封閉性」可知， ( a s ) q ∈ H (a^s)^q\in H (as)q∈H;又由羣的「單位元+逆元」可知， ( ( a s ) q ) − 1 ∈ H ((a^s)^q)^{-1}\in H ((as)q)−1∈H，所以 a m ⋅ ( ( a s ) q ) − 1 ∈ H a^m·((a^s)^q)^{-1}\in H am⋅((as)q)−1∈H，即 a r ∈ H 。 a^r\in H。 ar∈H。
又因爲 s s s是使得 a s ∈ H a^s\in H as∈H的最小數，所以 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=q⋅s,am=(as)q，即任意 a m ∈ H a^m\in H am∈H都可以寫成 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 a∈G,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| ∣H∣∣∣G∣。根據羣的「封閉性」，我們知道 < 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>。