循環群與生成元

循環群 (cyclic group) 由一個元素的所有冪生成:$\langle g\rangle = \{e, g, g^2,\dots\}$。有限循環群都同構於 $(\mathbb{Z}_n,+)$,無限的同構於 $\mathbb{Z}$——所以研究循環群就是研究 $\mathbb{Z}_n$ 與 $\mathbb{Z}$。

事實:$k$ 生成 $\mathbb{Z}_n$ ⟺ $\gcd(k,n) = 1$,生成元共 $\varphi(n)$ 個;$\mathbb{Z}_n$ 的子群與 $n$ 的正因數一一對應(每個因數 $d$ 恰一個 $d$ 階子群 $\langle n/d\rangle$);循環群的子群都是循環群;循環群必交換。

算例:$\mathbb{Z}_{12}$ 的生成元 $1,5,7,11$;子群有 6 個(因數 $1,2,3,4,6,12$);$\mathbb{Z}_7$ 除了 0 全是生成元。質數 $p$ 的乘法群 $U(p)$ 也是循環群,生成元叫原根。

循環群是最簡單的群,卻是有限交換群分類的積木(每個有限交換群是循環群的直積);離散對數問題「已知 $g^x$ 求 $x$」在大循環群裡很難,這是 Diffie–Hellman 與 ElGamal 的安全基礎。