信息安全数学基础--群环域--怎么判断是不是循环群？

博主是初学信息安全数学基础（整除+同余+原根+群环域），本意是想整理一些较难理解的定理、算法，加深记忆也方便日后查找；如果有错，欢迎指正。

三个方法：

• 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>。