巡回群とは？定義・部分群・生成元から暗号への応用まで

巡回群は、ただ一つの元で生成される群であり、群論に現れる最も単純な構造をもつ。生成元をくり返し掛けるだけですべての元が得られるので、時計の針が同じ文字盤をめぐるように、あるいは正多角形が回転で自らに重なるように、有限個または可算個の元がひと筋の輪をなす。すべての巡回群は、整数の加法群 $\mathbb{Z}$ か、その剰余群 $\mathbb{Z}/n\mathbb{Z}$ のどちらかと同型であり、この一言で分類が尽きてしまう。単純でありながら、有限体の乗法群や公開鍵暗号、フーリエ変換の背後にまで顔を出す、応用の広い群でもある。

巡回群の定義

群 $G$ が、ある元 $a\in G$ によって $G=⟨a⟩$ と生成されるとき、$G$ を巡回群という。この $a$ を $G$ の生成元と呼ぶ。生成される部分群は、$a$ の整数乗をすべて集めたものである。

$$⟨a⟩=\{a^n:n\in \mathbb{Z}\}=\{\dots ,a^{-2},a^{-1},e,a,a^2,\dots \}$$

加法で書かれた群なら $a^n$ は $na$ にあたり、$⟨a⟩=\{na:n\in \mathbb{Z}\}$ となる。生成元一つを決めれば群全体が復元できる、という一点に巡回群の単純さが凝縮されている。

時計と回転で捉える

巡回群のいちばん身近な姿は時計である。文字盤は $12$ の目盛りをもち、針を $1$ 時間進める操作をくり返すと $12$ 回でひとまわりして元に戻る。この「$1$ 進める」を生成元とみれば、時計は位数 $12$ の巡回群 $\mathbb{Z}/12\mathbb{Z}$ そのものである。$7$ 時の $8$ 時間後が $3$ 時になるのは、$7+8=15\equiv 3(\mathrm{mod}12)$ という剰余の計算にほかならない。

もう一つの絵が回転である。正 $n$ 角形を中心のまわりに $\frac{360^{\circ }}{n}$ だけ回すと、自分自身にぴたりと重なる。この最小の回転を生成元にとると、$n$ 回で一周する位数 $n$ の巡回群、いわゆる回転群 $C_n$ が得られる。生成元とは、一歩ずつ進めば必ず全体をちょうど一巡してすべての元を踏む歩幅のことだ、と思うと直感がつかめる。

有限巡回群と無限巡回群

生成元 $a$ の位数が有限か無限かで、巡回群は二種類に分かれる。$a$ の位数が $n$、すなわち $a^n=e$ となる最小の正の整数が $n$ のとき、$⟨a⟩$ は有限巡回群であり、相異なる元が $n$ 個そろう。

$$⟨a⟩=\{e,a,a^2,\dots ,a^{n-1}\},|⟨a⟩|=n$$

いっぽう $a$ の位数が無限のときは、$a^i=a^j$ が $i=j$ のときしか起こらない。したがって整数 $n$ と $a^n$ が一対一に対応し、$⟨a⟩$ は整数の加法群 $\mathbb{Z}$ と同型な無限巡回群になる。時計が有限巡回群なら、目盛りが両方向へ果てしなく続く数直線が、無限巡回群にあたる。

いろいろな巡回群

具体例を並べておく。もっとも基本的な無限巡回群は整数の加法群 $\mathbb{Z}$ で、生成元は $1$ と $-1$ の二つである。有限のほうの代表は剰余群 $\mathbb{Z}/n\mathbb{Z}$ で、$0$ から $n-1$ までを法 $n$ で足し合わせる群、生成元は $1$ を含む「$n$ と互いに素な元」たちである。

乗法的に現れる例も多い。複素数のうち $z^n=1$ を満たすもの、すなわち $1$ の $n$ 乗根全体 ${\mu }_n$ は、掛け算に関して位数 $n$ の巡回群をなし、生成元は原始 $n$ 乗根 $e^{2\pi i/n}$ である。これは正 $n$ 角形の頂点を単位円上に並べた姿で、さきほどの回転群 $C_n$ と同じ構造をもつ。さらに、後で見るように有限体の乗法群 ${\mathbb{F}}_q^{\times }$ も巡回群であり、たとえば $(\mathbb{Z}/5\mathbb{Z}{)}^{\times }=\{1,2,3,4\}$ は $2$ を生成元とする位数 $4$ の巡回群になる（$2,4,3,1$ と一巡する）。加法・乗法・回転と装いは違っても、これらはすべて同じ巡回群の変奏にすぎない。

分類定理

例を見ていると、位数さえ同じなら中身も同じに思えてくる。実際それが正しい。位数 $n$ の巡回群はすべて $\mathbb{Z}/n\mathbb{Z}$ と同型であり、無限巡回群はすべて $\mathbb{Z}$ と同型である。生成元を $\mathbb{Z}/n\mathbb{Z}$ の生成元 $1$ に対応させれば、同型がそのまま作れる。

したがって巡回群は、位数ただ一つで完全に分類される。位数 $n$ の巡回群を $C_n$ あるいは ${\mathbb{Z}}_n$ と書くこともあり、これらはすべて同じ群を指す。${\mu }_n$ も $C_n$ も位数 $4$ の $(\mathbb{Z}/5\mathbb{Z}{)}^{\times }$ も、位数が等しければ本質的に区別できない、というのが分類定理の主張である。

部分群

巡回群の部分群は、ふたたび巡回群になる。無限巡回群 $\mathbb{Z}$ の部分群は $n\mathbb{Z}=\{nk:k\in \mathbb{Z}\}$（$n\ge 0$）の形に限られ、これは $n$ で生成される巡回群である。$2\mathbb{Z}$ は偶数全体、$3\mathbb{Z}$ は $3$ の倍数全体、というぐあいだ。

有限のほうはもっと整っている。$\mathbb{Z}/n\mathbb{Z}$ では、$n$ の各約数 $d$ に対して位数 $d$ の部分群がちょうど一つずつ存在し、それは $n/d$ で生成される。$\mathbb{Z}/12\mathbb{Z}$ を例に取ると、$12$ の約数 $1,2,3,4,6,12$ に対応して、位数 $1$ の $⟨0⟩$、位数 $2$ の $⟨6⟩$、位数 $3$ の $⟨4⟩$、位数 $4$ の $⟨3⟩$、位数 $6$ の $⟨2⟩$、位数 $12$ の $⟨1⟩$ が並ぶ。約数の関係がそのまま部分群の包含関係を写し取っているのが、巡回群の際立った特徴である。

部分群と生成元の個数

いまの例から、部分群の個数はすぐ読み取れる。位数 $n$ の巡回群の部分群は $n$ の約数と一対一に対応するので、その個数は約数の個数 $\tau (n)$ に等しい。$\mathbb{Z}/12\mathbb{Z}$ なら $\tau (12)=6$ で、たしかに部分群は六つだった。

生成元の個数は、別の数論的関数で数えられる。$\mathbb{Z}/n\mathbb{Z}$ の生成元は、$n$ と互いに素な元 $k$、すなわち $\gcd (k,n)=1$ を満たすものに限る。その個数はオイラー関数 $\phi (n)$ で与えられる。$\phi (12)=4$ なので、$\mathbb{Z}/12\mathbb{Z}$ の生成元は $1,5,7,11$ の四つである。一般の元 $k$ の位数は $\frac{n}{\gcd (n,k)}$ で決まり、これが $n$ に等しくなる、つまり全体を生成するのは $\gcd (k,n)=1$ のときに限る、というわけだ。

自己同型群

巡回群を自分自身へ移す同型（自己同型）も、生成元の行き先だけで決まる。無限巡回群 $\mathbb{Z}$ では、生成元 $1$ を $1$ か $-1$ のどちらかへ送るしかないので、自己同型は恒等と符号反転の二つ、$\mathrm{Aut}(\mathbb{Z})\cong \mathbb{Z}/2\mathbb{Z}$ である。

有限の $\mathbb{Z}/n\mathbb{Z}$ では、生成元 $1$ を別の生成元 $k$（$\gcd (k,n)=1$）へ送る対応が、それぞれ自己同型を与える。写像の合成が掛け算に対応するので、自己同型群は既約剰余類群と同型になる。

$$\mathrm{Aut}(\mathbb{Z}/n\mathbb{Z})\cong (\mathbb{Z}/n\mathbb{Z}{)}^{\times }$$

その位数は生成元の個数 $\phi (n)$ に等しい。生成元をどう置換できるかが、そのまま群の対称性を測っているわけである。

直積と中国剰余定理

二つの巡回群の直積は、いつでも巡回群になるとは限らない。分かれ目は、位数が互いに素かどうかである。$\gcd (m,n)=1$ のときは、中国剰余定理により直積がふたたび巡回群になる。

$$\mathbb{Z}/m\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}\cong \mathbb{Z}/mn\mathbb{Z}(\gcd (m,n)=1)$$

たとえば $\mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/3\mathbb{Z}\cong \mathbb{Z}/6\mathbb{Z}$ である。ところが位数が互いに素でないと、この同型は壊れる。同じ位数 $4$ をもつ二つの群を比べると、事情がはっきりする。

$\mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/2\mathbb{Z}$ が $\mathbb{Z}/4\mathbb{Z}$ と同型でないのは、$\gcd (2,2)=2>1$ だからである。位数が同じでも、内部の位数の分布が違えば別の群になる、という好例だ。

素数位数の群

位数が素数 $p$ の群は、選択の余地なく巡回群 $\mathbb{Z}/p\mathbb{Z}$ に限られる。$|G|=p$ とし、単位元でない元 $a$ を一つとる。ラグランジュの定理より $a$ の位数は $p$ の約数だが、$a\ne e$ なので $1$ ではなく、$p$ しかありえない。

したがって $⟨a⟩$ は位数 $p$、つまり $G$ 全体に一致し、$G=⟨a⟩$ は巡回群である。位数が素数というだけで、群の構造が一意に決まってしまう。これは、素数位数の群がアーベル群であることや、有限群の分類の出発点としても効いてくる基本事実である。

有限体の乗法群

有限体 ${\mathbb{F}}_q$（$q$ は素数の冪）から $0$ を除いた乗法群 ${\mathbb{F}}_q^{\times }$ は、位数 $q-1$ の巡回群になる。これは決して当たり前ではなく、有限体という特別な舞台でのみ成り立つ、味わい深い事実である。

証明の骨格はこうだ。${\mathbb{F}}_q^{\times }$ の元 $x$ の位数を $d$ とすると $x^d=1$ で、多項式 $x^d-1$ は体の上で高々 $d$ 個しか根をもたない。この根の個数の制約と、有限アーベル群における位数の分布をあわせると、最大位数の元が全体を生成せざるをえないことが従う。この生成元を原始元と呼ぶ。たとえば ${\mathbb{F}}_5^{\times }$ では $2$ が、${\mathbb{F}}_7^{\times }$ では $3$ が原始元になる。有限体の乗法が一本の輪をなすこの性質は、次に見る暗号への応用で決定的に効いてくる。

原始根

${\mathbb{F}}_p^{\times }$ が巡回群だという話は、$(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ が巡回群になるのはどんな $n$ か、という問いへ一般化される。答えははっきりしていて、巡回群になるのは $n=1,2,4,p^k,2p^k$（$p$ は奇素数）のときに限る。このとき存在する生成元を、$n$ を法とする原始根という。

素数を法とする場合は、必ず原始根が存在する。$(\mathbb{Z}/7\mathbb{Z}{)}^{\times }$ では $3$ が原始根で、$3,2,6,4,5,1$ と六つの元をすべて一巡する。いっぽう $(\mathbb{Z}/8\mathbb{Z}{)}^{\times }=\{1,3,5,7\}$ は、$3^2=5^2=7^2=1$ とどの元も位数 $2$ 以下なので巡回群ではなく、$8$ を法とする原始根は存在しない。$8=2^3$ が上の形に当てはまらないことと、ちょうど符合している。

応用：1 の n 乗根と離散フーリエ変換

巡回群の乗法的な姿である $1$ の $n$ 乗根は、信号処理の中心にある離散フーリエ変換を支えている。原始 $n$ 乗根 $\omega =e^{-2\pi i/n}$ の冪 ${\omega }^0,{\omega }^1,\dots ,{\omega }^{n-1}$ は、位数 $n$ の巡回群をなす。離散フーリエ変換は、この冪を係数に使って数列を別の数列へ写す変換である。

$$X_k=\sum _{j=0}^{n-1}{x}_j{\omega }^{jk}(k=0,1,\dots ,n-1)$$

$\omega$ が一巡して ${\omega }^n=1$ に戻る巡回性のおかげで、変換の計算に周期的な対称性が生まれる。高速フーリエ変換は、まさにこの巡回群の構造を再帰的に使って、計算量を $n^2$ から $n\log n$ へ劇的に減らす。巡回群の一巡する性質が、そのまま計算の効率へ直結しているのである。

応用：公開鍵暗号

巡回群は、現代の暗号の土台でもある。大きな素数 $p$ に対する $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$ は位数 $p-1$ の巡回群で、その生成元 $g$ を使うと、$g^x$ を計算するのは易しいのに、$g^x$ から $x$ を復元する（離散対数を求める）のは非常に難しい。この一方通行性を利用したのが、ディフィー・ヘルマンの鍵共有である。

盗聴者は $g^a$ と $g^b$ を見られても、離散対数が解けないため $g^{ab}$ を作れない。巡回群の生成元をめぐる計算の非対称性が、そのまま安全性の根拠になっている。同じ原理は、エルガマル暗号や楕円曲線暗号にも受け継がれている。

応用：身近な周期

抽象的に見える巡回群は、日々くり返される周期のいたるところに潜んでいる。三つほど挙げておく。

時計の針から暗号の鍵、音楽の移調まで、一つの元がくり返し全体を巡るという巡回群の単純な仕組みが、姿を変えて何度も現れる。最も基本的な群が、最も広く世界に根を張っているのである。