有限体の勉強 〜位数64の有限体の構造を探る〜 [数学]
前回の記事で、有限体に関する一般的な性質をいくつか確認しました。今回はそれを使って、もう少し大きな位数の有限体である $F_{64}$ の構造を調べることにします。
なぜ $F_{64}$ なのかというと、$64 = 2^6$ なので標数は$2$で、前回の【定理2】より、
\begin{eqnarray*}
F_2 \subset F_4 \subset F_{64} \\
F_2 \subset F_8 \subset F_{64}
\end{eqnarray*}
という$2$つの異なった部分体の系列を持つから、その様子を見たいという理由です。元の数が$64$だったらなんとか手作業で頑張れる範囲だろうという目論見もあります。実際、今回の作業はスプレッドシート（EXCEL が代表的ですが実際に使ったのは LibreOffice）を使ってあまり苦労せずに実施できました。
まず、前回の【定理1】より、$F_{64}$ は $F_2$ 上の多項式 $X^{64}-X$ の最小分解体なので、$X^{64}-X$ を $F_2$ 上で既約因子に分解することを考えます。これは前回の【定理2】より、$F_2$ 上の$6$次の既約多項式を全て見出せばよいことになります（次数$1,2,3$の既約多項式は前々回で全て分かっています）。
前回の【定理3】の後の考察によって、$F_2$ 上の$6$次の既約多項式は全部で$9$つあります。多項式の既約性の確認は一般に面倒な作業ですが、今回の場合はちょっと発想を変えることによってそれほど苦労せずにこの$9$つを特定できました。以下その手順です。
$F_2$ 上の多項式なので係数は$0,1$のみを考えればよろしい。そして、
① $X$ を因子に持たないことから、$X$ に$0$を代入した結果は$0$ではない。従って定数項は$1$。
② $X-1$ を因子に持たないことから、$X$ に$1$を代入した結果は$0$ではない。従って係数$1$の項は奇数個。
の$2$つの条件を満たすものが候補になります。これらをみたす$6$次多項式は以下の$16$個です。
\begin{eqnarray*}
(A) &\quad& X^6+X^5+X^4+X^3+X^2+X+1 \\
(B) &\quad& X^6+X^5+X^4+X^3+1 \\
(C) &\quad& X^6+X^5+X^4+X^2+1 \\
(D) &\quad& X^6+X^5+X^4+X+1 \\
(E) &\quad& X^6+X^5+X^3+X^2+1 \\
(F) &\quad& X^6+X^5+X^3+X+1 \\
(G) &\quad& X^6+X^5+X^2+X+1 \\
(H) &\quad& X^6+X^4+X^3+X^2+1 \\
(I) &\quad& X^6+X^4+X^3+X+1 \\
(J) &\quad& X^6+X^4+X^2+X+1 \\
(K) &\quad& X^6+X^3+X^2+X+1 \\
(L) &\quad& X^6+X^5+1 \\
(M) &\quad& X^6+X^4+1 \\
(N) &\quad& X^6+X^3+1 \\
(O) &\quad& X^6+X^2+1 \\
(P) &\quad& X^6+X+1
\end{eqnarray*}
次に、これらの中から$2$次以上の既約因子に分解できるものを除きます。次数が$6$なので分解のパターンは、$2$次×$2$次×$2$次、$2$次×$4$次、$3$次×$3$次 の$3$とおりしかありません。そして前々回の記事より、$2$次の既約多項式は
\begin{equation*}
X^2+X+1
\end{equation*}
の$1$つだけ、$3$次の既約多項式は
\begin{eqnarray*}
&& X^3+X^2+1 \\
&& X^3+X+1
\end{eqnarray*}
の$2$つ、$4$次の既約多項式は
\begin{eqnarray*}
&& X^4+X^3+X^2+X+1 \\
&& X^4+X^3+1 \\
&& X^4+X+1
\end{eqnarray*}
の$3$つであることがわかっているので、これらの組み合わせとなる$6$次多項式を候補から除けばよいわけです。実際に計算すると、
\begin{eqnarray*}
(X^2+X+1)^3 &=& X^6+X^5+X^3+X+1 \quad &\cdots& \quad (F)\\
(X^2+X+1)(X^4+X^3+X^2+X+1) &=& X^6+X^4+X^3+X^2+1 \quad &\cdots& \quad (H)\\
(X^2+X+1)(X^4+X^3+1) &=& X^6+X^3+X^2+X+1 \quad &\cdots& \quad (K)\\
(X^2+X+1)(X^4+X+1) &=& X^6+X^5+X^4+X^3+1 \quad &\cdots& \quad (B)\\
(X^3+X^2+1)^2 &=& X^6+X^4+1 \quad &\cdots& \quad (M)\\
(X^3+X+1)^2 &=& X^6+X^2+1 \quad &\cdots& \quad (O)\\
(X^3+X^2+1)(X^3+X+1) &=& X^6+X^5+X^4+X^3+X^2+X+1 \quad &\cdots& \quad (A)
\end{eqnarray*}
となりますので、これらを除くことにより、結局次の$9$つが $F_2$ 上の$6$次の既約多項式の全てであることがわかりました。
\begin{eqnarray*}
(C) &\quad& X^6+X^5+X^4+X^2+1 \\
(D) &\quad& X^6+X^5+X^4+X+1 \\
(E) &\quad& X^6+X^5+X^3+X^2+1 \\
(G) &\quad& X^6+X^5+X^2+X+1 \\
(I) &\quad& X^6+X^4+X^3+X+1 \\
(J) &\quad& X^6+X^4+X^2+X+1 \\
(L) &\quad& X^6+X^5+1 \\
(N) &\quad& X^6+X^3+1 \\
(P) &\quad& X^6+X+1
\end{eqnarray*}
従って、多項式 $X^{64}-X$ は $F_2$ 上で次のように既約因子に分解されます。
\begin{eqnarray*}
X^{64}-X &=& X(X-1)(X^2+X+1)(X^3+X^2+1)(X^3+X+1) \\
&& \cdot (X^6+X^5+X^4+X^2+1)(X^6+X^5+X^4+X+1)(X^6+X^5+X^3+X^2+1) \\
&& \cdot (X^6+X^5+X^2+X+1)(X^6+X^4+X^3+X+1)(X^6+X^4+X^2+X+1) \\
&& \cdot (X^6+X^5+1)(X^6+X^3+1)(X^6+X+1)
\end{eqnarray*}
この分解が正しいことを手作業で確認することはさすがにやめました。前回の【定理3】を信じます。
さて、これら$9$つの$6$次の既約多項式のうち、どの多項式の根を $F_2$ に添加しても同じ $F_{64}$ が構成できますが、乗算表を楽に作るためには前々回でみたように 、根が$F_{64}$ の乗法群 $F_{64}^\times$ の原始元になるような多項式を探す必要があります（原始元が必ず存在することは証明されています）。この作業はある意味試行錯誤ですが、スプレッドシートの力を借りて計算することにより、
\begin{equation*}
(D) \quad X^6+X^5+X^4+X+1
\end{equation*}
の根が原始元になることがわかりました。以下$(D)$の根を$\alpha$とおき、これを基本にします。$\alpha^{63} = 1$ なので、
\[ F_{64} = \{ \, 0, \, \alpha^0(=1), \, \alpha^1, \, \alpha^2, \cdots , \alpha^{61} , \alpha^{62} \, \} \]
であり、$F_{64}^\times$ の全ての元について、$\alpha$の指数で表す「べき表現」と、 $(\alpha^5, \alpha^4, \alpha^3, \alpha^2, \alpha, 1)$ を基底とする「ベクトル表現」との対応づけができます。これが次の表です。
この表の見方は、例えば上から8行目を見ると、
\[ \alpha^7 = \alpha^{-56} = \alpha^4+\alpha^2+1 \]
であって、さらにその $F_2$ における最小多項式が $X^6+X^3+1$ である、ということです。
この対応表の作成も、スプレッドシートを使って1ビットずつ計算式を入れることにより簡単にできました。最小多項式の欄については、前回の【定理4】より指数が2倍になっても同じ最小多項式になることを使い、負の指数もうまく使うことによって簡単に埋まりました。
ここまでくると、スプレッドシートを使って $F_{64}$ の加算表と乗算表が機械的に作成できます。加算表はベクトル表現を、乗算表はべき表現を使って作成し、それぞれを変換表を用いて他の表現に置き換えると、次のようにベクトル表現とべき表現による加算表と乗算表ができあがります（リンクをクリックすると別ページで表示されます。なおべき表現では$0$が表現できないので * であらわしています。）。
・$F_{64}$の加算表（ベクトル表現）
・$F_{64}$の加算表（べき表現）
・$F_{64}$の乗算表（ベクトル表現）
・$F_{64}$の乗算表（べき表現）
これらの表では部分体も色付けによって表現しています。ピンクは $F_2$、黄色は $F_4 \setminus F_2$、緑は $F_8 \setminus F_2$ に相当する部分です。これら部分体を見出すのも上の対応表を使えば簡単にできます。$F_2 = \{ \, 0, \, \alpha^0 \, \}$ は当然として、$F_4$ は最小多項式が$2$次になるものを取り出せばよいので、
\[ F_4 = \{ \, 0, \, \alpha^0 \, \alpha^{21} \, \alpha^{42} \, \} \]
と指数が$21$の倍数になるもので構成されることがわかり、同様に $F_8$ は最小多項式が$3$次になるものを取り出せばよいので、
\[ F_8 = \{ \, 0, \, \alpha^0 \, \alpha^9 \, \alpha^{18} \, \alpha^{27} \, \alpha^{36} \, \alpha^{45} \, \alpha^{54} \, \} \]
と指数が$9$の倍数になるもので構成されることがわかり、これらの場所を各表に色付けすればよいわけです。蛇足ながら $F_4$ が $F_8$ の部分体にならないことも一目瞭然です。
さらに蛇足ながら、乗法群 $F_{64}^\times$ の原始元になることは、位数が$63$になること、すなわち$\alpha$の指数が$63$と互いに素であることと同値なので、原始元はオイラーの$\varphi$関数を用いて $\varphi(63) = 36$ 個あることになります。上の表で指数が$63$と互いに素なものに対応する最小多項式を全て拾い出すと、
\begin{eqnarray*}
(D) &\quad& X^6+X^5+X^4+X+1 \\
(E) &\quad& X^6+X^5+X^3+X^2+1 \\
(G) &\quad& X^6+X^5+X^2+X+1 \\
(I) &\quad& X^6+X^4+X^3+X+1 \\
(L) &\quad& X^6+X^5+1 \\
(P) &\quad& X^6+X+1
\end{eqnarray*}
の$6$つです。これらの多項式の根は全て $F_{64}^\times$ の原始元になるというわけです。このような多項式を原始多項式といいます。
これら以外の$6$次の既約多項式$3$つ
\begin{eqnarray*}
(C) &\quad& X^6+X^5+X^4+X^2+1 \\
(J) &\quad& X^6+X^4+X^2+X+1 \\
(N) &\quad& X^6+X^3+1
\end{eqnarray*}
については、その根が $F_{64}^\times$ の原始元にならないので、原始多項式ではありません。既約多項式が原始多項式かどうかを係数から簡単に見分ける方法があるのかないのか、今の僕はその知見を持っていません。
（続く）（前記事）
なぜ $F_{64}$ なのかというと、$64 = 2^6$ なので標数は$2$で、前回の【定理2】より、
\begin{eqnarray*}
F_2 \subset F_4 \subset F_{64} \\
F_2 \subset F_8 \subset F_{64}
\end{eqnarray*}
という$2$つの異なった部分体の系列を持つから、その様子を見たいという理由です。元の数が$64$だったらなんとか手作業で頑張れる範囲だろうという目論見もあります。実際、今回の作業はスプレッドシート（EXCEL が代表的ですが実際に使ったのは LibreOffice）を使ってあまり苦労せずに実施できました。
まず、前回の【定理1】より、$F_{64}$ は $F_2$ 上の多項式 $X^{64}-X$ の最小分解体なので、$X^{64}-X$ を $F_2$ 上で既約因子に分解することを考えます。これは前回の【定理2】より、$F_2$ 上の$6$次の既約多項式を全て見出せばよいことになります（次数$1,2,3$の既約多項式は前々回で全て分かっています）。
前回の【定理3】の後の考察によって、$F_2$ 上の$6$次の既約多項式は全部で$9$つあります。多項式の既約性の確認は一般に面倒な作業ですが、今回の場合はちょっと発想を変えることによってそれほど苦労せずにこの$9$つを特定できました。以下その手順です。
$F_2$ 上の多項式なので係数は$0,1$のみを考えればよろしい。そして、
① $X$ を因子に持たないことから、$X$ に$0$を代入した結果は$0$ではない。従って定数項は$1$。
② $X-1$ を因子に持たないことから、$X$ に$1$を代入した結果は$0$ではない。従って係数$1$の項は奇数個。
の$2$つの条件を満たすものが候補になります。これらをみたす$6$次多項式は以下の$16$個です。
\begin{eqnarray*}
(A) &\quad& X^6+X^5+X^4+X^3+X^2+X+1 \\
(B) &\quad& X^6+X^5+X^4+X^3+1 \\
(C) &\quad& X^6+X^5+X^4+X^2+1 \\
(D) &\quad& X^6+X^5+X^4+X+1 \\
(E) &\quad& X^6+X^5+X^3+X^2+1 \\
(F) &\quad& X^6+X^5+X^3+X+1 \\
(G) &\quad& X^6+X^5+X^2+X+1 \\
(H) &\quad& X^6+X^4+X^3+X^2+1 \\
(I) &\quad& X^6+X^4+X^3+X+1 \\
(J) &\quad& X^6+X^4+X^2+X+1 \\
(K) &\quad& X^6+X^3+X^2+X+1 \\
(L) &\quad& X^6+X^5+1 \\
(M) &\quad& X^6+X^4+1 \\
(N) &\quad& X^6+X^3+1 \\
(O) &\quad& X^6+X^2+1 \\
(P) &\quad& X^6+X+1
\end{eqnarray*}
次に、これらの中から$2$次以上の既約因子に分解できるものを除きます。次数が$6$なので分解のパターンは、$2$次×$2$次×$2$次、$2$次×$4$次、$3$次×$3$次 の$3$とおりしかありません。そして前々回の記事より、$2$次の既約多項式は
\begin{equation*}
X^2+X+1
\end{equation*}
の$1$つだけ、$3$次の既約多項式は
\begin{eqnarray*}
&& X^3+X^2+1 \\
&& X^3+X+1
\end{eqnarray*}
の$2$つ、$4$次の既約多項式は
\begin{eqnarray*}
&& X^4+X^3+X^2+X+1 \\
&& X^4+X^3+1 \\
&& X^4+X+1
\end{eqnarray*}
の$3$つであることがわかっているので、これらの組み合わせとなる$6$次多項式を候補から除けばよいわけです。実際に計算すると、
\begin{eqnarray*}
(X^2+X+1)^3 &=& X^6+X^5+X^3+X+1 \quad &\cdots& \quad (F)\\
(X^2+X+1)(X^4+X^3+X^2+X+1) &=& X^6+X^4+X^3+X^2+1 \quad &\cdots& \quad (H)\\
(X^2+X+1)(X^4+X^3+1) &=& X^6+X^3+X^2+X+1 \quad &\cdots& \quad (K)\\
(X^2+X+1)(X^4+X+1) &=& X^6+X^5+X^4+X^3+1 \quad &\cdots& \quad (B)\\
(X^3+X^2+1)^2 &=& X^6+X^4+1 \quad &\cdots& \quad (M)\\
(X^3+X+1)^2 &=& X^6+X^2+1 \quad &\cdots& \quad (O)\\
(X^3+X^2+1)(X^3+X+1) &=& X^6+X^5+X^4+X^3+X^2+X+1 \quad &\cdots& \quad (A)
\end{eqnarray*}
となりますので、これらを除くことにより、結局次の$9$つが $F_2$ 上の$6$次の既約多項式の全てであることがわかりました。
\begin{eqnarray*}
(C) &\quad& X^6+X^5+X^4+X^2+1 \\
(D) &\quad& X^6+X^5+X^4+X+1 \\
(E) &\quad& X^6+X^5+X^3+X^2+1 \\
(G) &\quad& X^6+X^5+X^2+X+1 \\
(I) &\quad& X^6+X^4+X^3+X+1 \\
(J) &\quad& X^6+X^4+X^2+X+1 \\
(L) &\quad& X^6+X^5+1 \\
(N) &\quad& X^6+X^3+1 \\
(P) &\quad& X^6+X+1
\end{eqnarray*}
従って、多項式 $X^{64}-X$ は $F_2$ 上で次のように既約因子に分解されます。
\begin{eqnarray*}
X^{64}-X &=& X(X-1)(X^2+X+1)(X^3+X^2+1)(X^3+X+1) \\
&& \cdot (X^6+X^5+X^4+X^2+1)(X^6+X^5+X^4+X+1)(X^6+X^5+X^3+X^2+1) \\
&& \cdot (X^6+X^5+X^2+X+1)(X^6+X^4+X^3+X+1)(X^6+X^4+X^2+X+1) \\
&& \cdot (X^6+X^5+1)(X^6+X^3+1)(X^6+X+1)
\end{eqnarray*}
この分解が正しいことを手作業で確認することはさすがにやめました。前回の【定理3】を信じます。
さて、これら$9$つの$6$次の既約多項式のうち、どの多項式の根を $F_2$ に添加しても同じ $F_{64}$ が構成できますが、乗算表を楽に作るためには前々回でみたように 、根が$F_{64}$ の乗法群 $F_{64}^\times$ の原始元になるような多項式を探す必要があります（原始元が必ず存在することは証明されています）。この作業はある意味試行錯誤ですが、スプレッドシートの力を借りて計算することにより、
\begin{equation*}
(D) \quad X^6+X^5+X^4+X+1
\end{equation*}
の根が原始元になることがわかりました。以下$(D)$の根を$\alpha$とおき、これを基本にします。$\alpha^{63} = 1$ なので、
\[ F_{64} = \{ \, 0, \, \alpha^0(=1), \, \alpha^1, \, \alpha^2, \cdots , \alpha^{61} , \alpha^{62} \, \} \]
であり、$F_{64}^\times$ の全ての元について、$\alpha$の指数で表す「べき表現」と、 $(\alpha^5, \alpha^4, \alpha^3, \alpha^2, \alpha, 1)$ を基底とする「ベクトル表現」との対応づけができます。これが次の表です。
| べき表現 | 負べき表現 | ベクトル表現 | 最小多項式 |
| 0 | -63 | 000001 | $X-1$（または $X+1$） |
| 1 | -62 | 000010 | $X^6+X^5+X^4+X+1$ |
| 2 | -61 | 000100 | $X^6+X^5+X^4+X+1$ |
| 3 | -60 | 001000 | $X^6+X^4+X^2+X+1$ |
| 4 | -59 | 010000 | $X^6+X^5+X^4+X+1$ |
| 5 | -58 | 100000 | $X^6+X^4+X^3+X+1$ |
| 6 | -57 | 110011 | $X^6+X^4+X^2+X+1$ |
| 7 | -56 | 010101 | $X^6+X^3+1$ |
| 8 | -55 | 101010 | $X^6+X^5+X^4+X+1$ |
| 9 | -54 | 100111 | $X^3+X^2+1$ |
| 10 | -53 | 111101 | $X^6+X^4+X^3+X+1$ |
| 11 | -52 | 001001 | $X^6+X+1$ |
| 12 | -51 | 010010 | $X^6+X^4+X^2+X+1$ |
| 13 | -50 | 100100 | $X^6+X^5+1$ |
| 14 | -49 | 111011 | $X^6+X^3+1$ |
| 15 | -48 | 000101 | $X^6+X^5+X^4+X^2+1$ |
| 16 | -47 | 001010 | $X^6+X^5+X^4+X+1$ |
| 17 | -46 | 010100 | $X^6+X^4+X^3+X+1$ |
| 18 | -45 | 101000 | $X^3+X^2+1$ |
| 19 | -44 | 100011 | $X^6+X^5+1$ |
| 20 | -43 | 110101 | $X^6+X^4+X^3+X+1$ |
| 21 | -42 | 011001 | $X^2+X+1$ |
| 22 | -41 | 110010 | $X^6+X+1$ |
| 23 | -40 | 010111 | $X^6+X^5+X^3+X^2+1$ |
| 24 | -39 | 101110 | $X^6+X^4+X^2+X+1$ |
| 25 | -38 | 101111 | $X^6+X+1$ |
| 26 | -37 | 101101 | $X^6+X^5+1$ |
| 27 | -36 | 101001 | $X^3+X+1$ |
| 28 | -35 | 100001 | $X^6+X^3+1$ |
| 29 | -34 | 110001 | $X^6+X^5+X^3+X^2+1$ |
| 30 | -33 | 010001 | $X^6+X^5+X^4+X^2+1$ |
| 31 | -32 | 100010 | $X^6+X^5+X^2+X+1$ |
| 32 | -31 | 110111 | $X^6+X^5+X^4+X+1$ |
| 33 | -30 | 011101 | $X^6+X^4+X^2+X+1$ |
| 34 | -29 | 111010 | $X^6+X^4+X^3+X+1$ |
| 35 | -28 | 000111 | $X^6+X^3+1$ |
| 36 | -27 | 001110 | $X^3+X^2+1$ |
| 37 | -26 | 011100 | $X^6+X+1$ |
| 38 | -25 | 111000 | $X^6+X^5+1$ |
| 39 | -24 | 000011 | $X^6+X^5+X^4+X^2+1$ |
| 40 | -23 | 000110 | $X^6+X^4+X^3+X+1$ |
| 41 | -22 | 001100 | $X^6+X^5+1$ |
| 42 | -21 | 011000 | $X^2+X+1$ |
| 43 | -20 | 110000 | $X^6+X^5+X^3+X^2+1$ |
| 44 | -19 | 010011 | $X^6+X+1$ |
| 45 | -18 | 100110 | $X^3+X+1$ |
| 46 | -17 | 111111 | $X^6+X^5+X^3+X^2+1$ |
| 47 | -16 | 001101 | $X^6+X^5+X^2+X+1$ |
| 48 | -15 | 011010 | $X^6+X^4+X^2+X+1$ |
| 49 | -14 | 110100 | $X^6+X^3+1$ |
| 50 | -13 | 011011 | $X^6+X+1$ |
| 51 | -12 | 110110 | $X^6+X^5+X^4+X^2+1$ |
| 52 | -11 | 011111 | $X^6+X^5+1$ |
| 53 | -10 | 111110 | $X^6+X^5+X^3+X^2+1$ |
| 54 | -9 | 001111 | $X^3+X+1$ |
| 55 | -8 | 011110 | $X^6+X^5+X^2+X+1$ |
| 56 | -7 | 111100 | $X^6+X^3+1$ |
| 57 | -6 | 001011 | $X^6+X^5+X^4+X^2+1$ |
| 58 | -5 | 010110 | $X^6+X^5+X^3+X^2+1$ |
| 59 | -4 | 101100 | $X^6+X^5+X^2+X+1$ |
| 60 | -3 | 101011 | $X^6+X^5+X^4+X^2+1$ |
| 61 | -2 | 100101 | $X^6+X^5+X^2+X+1$ |
| 62 | -1 | 111001 | $X^6+X^5+X^2+X+1$ |
この表の見方は、例えば上から8行目を見ると、
\[ \alpha^7 = \alpha^{-56} = \alpha^4+\alpha^2+1 \]
であって、さらにその $F_2$ における最小多項式が $X^6+X^3+1$ である、ということです。
この対応表の作成も、スプレッドシートを使って1ビットずつ計算式を入れることにより簡単にできました。最小多項式の欄については、前回の【定理4】より指数が2倍になっても同じ最小多項式になることを使い、負の指数もうまく使うことによって簡単に埋まりました。
ここまでくると、スプレッドシートを使って $F_{64}$ の加算表と乗算表が機械的に作成できます。加算表はベクトル表現を、乗算表はべき表現を使って作成し、それぞれを変換表を用いて他の表現に置き換えると、次のようにベクトル表現とべき表現による加算表と乗算表ができあがります（リンクをクリックすると別ページで表示されます。なおべき表現では$0$が表現できないので * であらわしています。）。
・$F_{64}$の加算表（ベクトル表現）
・$F_{64}$の加算表（べき表現）
・$F_{64}$の乗算表（ベクトル表現）
・$F_{64}$の乗算表（べき表現）
これらの表では部分体も色付けによって表現しています。ピンクは $F_2$、黄色は $F_4 \setminus F_2$、緑は $F_8 \setminus F_2$ に相当する部分です。これら部分体を見出すのも上の対応表を使えば簡単にできます。$F_2 = \{ \, 0, \, \alpha^0 \, \}$ は当然として、$F_4$ は最小多項式が$2$次になるものを取り出せばよいので、
\[ F_4 = \{ \, 0, \, \alpha^0 \, \alpha^{21} \, \alpha^{42} \, \} \]
と指数が$21$の倍数になるもので構成されることがわかり、同様に $F_8$ は最小多項式が$3$次になるものを取り出せばよいので、
\[ F_8 = \{ \, 0, \, \alpha^0 \, \alpha^9 \, \alpha^{18} \, \alpha^{27} \, \alpha^{36} \, \alpha^{45} \, \alpha^{54} \, \} \]
と指数が$9$の倍数になるもので構成されることがわかり、これらの場所を各表に色付けすればよいわけです。蛇足ながら $F_4$ が $F_8$ の部分体にならないことも一目瞭然です。
さらに蛇足ながら、乗法群 $F_{64}^\times$ の原始元になることは、位数が$63$になること、すなわち$\alpha$の指数が$63$と互いに素であることと同値なので、原始元はオイラーの$\varphi$関数を用いて $\varphi(63) = 36$ 個あることになります。上の表で指数が$63$と互いに素なものに対応する最小多項式を全て拾い出すと、
\begin{eqnarray*}
(D) &\quad& X^6+X^5+X^4+X+1 \\
(E) &\quad& X^6+X^5+X^3+X^2+1 \\
(G) &\quad& X^6+X^5+X^2+X+1 \\
(I) &\quad& X^6+X^4+X^3+X+1 \\
(L) &\quad& X^6+X^5+1 \\
(P) &\quad& X^6+X+1
\end{eqnarray*}
の$6$つです。これらの多項式の根は全て $F_{64}^\times$ の原始元になるというわけです。このような多項式を原始多項式といいます。
これら以外の$6$次の既約多項式$3$つ
\begin{eqnarray*}
(C) &\quad& X^6+X^5+X^4+X^2+1 \\
(J) &\quad& X^6+X^4+X^2+X+1 \\
(N) &\quad& X^6+X^3+1
\end{eqnarray*}
については、その根が $F_{64}^\times$ の原始元にならないので、原始多項式ではありません。既約多項式が原始多項式かどうかを係数から簡単に見分ける方法があるのかないのか、今の僕はその知見を持っていません。
（続く）（前記事）
有限体の勉強 〜素体上の既約多項式への分解〜 [数学]
有限体のことを何も知らないので勉強を始めました。前回は標数2の有限体のうち、$F_2$ から $F_{16}$ までの加算乗算表を作るところまでやってみました。
この過程で見えてきたことを一つずつ検証してみます。
まず単純な話ですが、$F_2$ 上の多項式には次数$n$が何であっても必ず$n$次の既約多項式がある、という事実があります。$2$次ならば $X^2+X+1$ がそうですし、$3$次でも$4$次でもありました。これは標数が一般の素数$p$に対して成り立ちます。
このことを証明するために、有限体の位数（元の数）に関する基本的な定理をまず書いておきます。
（証明）$K$を有限体とすると、$\mathbb{Q}$が無限集合だから$K$の標数は$0$ではなく、素数$p$である。$K$は素体 $F_p$ 上の有限次元ベクトル空間なので、次元を$n$とすると$K$の位数は $p^n$ になる。従って有限体の位数は $p^n$ と表されるものに限られる。
素数$p$と正整数$n$に対して $q = p^n$ とし、$F_p$ 上で$q$次の多項式 $f(X) = X^q-X$ を考えると、体の拡大の一般論によって、$f(X)$ の $F_p$ 上の最小分解体が同形を除いて一意に存在する。また $f(X)$ の形式微分は標数が$p$であることから $f'(X) = -1$ なので $f(X)$ は重根を持たず、従って最小分解体上で $f(X)$ は異なる$q$個の根を持つ。$\alpha, \beta$ を $f(X)$ の根とすると、フロベニウス写像が環準同型であることと $\alpha^q = \alpha, \, \beta^q = \beta$ より、
\begin{eqnarray*}
f(\alpha+\beta) &=& (\alpha+\beta)^{p^n} - (\alpha+\beta) = \alpha^{p^n} +\beta^{p^n} - \alpha - \beta = \alpha^q +\beta^q - \alpha - \beta = \alpha + \beta - \alpha - \beta = 0 \\
f(\alpha\beta) &=& (\alpha\beta)^q - \alpha\beta = \alpha^q \beta^q - \alpha\beta = \alpha \beta - \alpha\beta = 0 \\
f(\alpha^{-1}) &=& (\alpha^{-1})^q - \alpha^{-1} = (\alpha^q)^{-1} - \alpha^{-1} = \alpha^{-1} - \alpha^{-1} = 0
\end{eqnarray*}
となるから、$f(X)$ の$q$個の根の集合は体を構成する。従って最小分解体はちょうど$q$個の元を持ち、位数$q$の有限体は存在する。
位数$q$の体$K$の乗法群 $K^\times$ は位数 $q-1$ なので、任意の $K^\times$ の元$\alpha$は $\alpha^{q-1} = 1$ をみたし、従って$K$の$q$個の元は$0$を含め全て $\alpha^q = \alpha$ をみたすから、$f(X)$ の根である。従って $f(X)$ は$K$上$q$個の$1$次式に分解されるから、$K$は $F_p$ 上の $f(X)$ の最小分解体である。従って位数$q$の有限体は同形を除いて一意に定まる。□
平たくいうと、位数 $q = p^n$ の有限体は、$F_p$ の拡大体で多項式 $X^q-X$ の$q$個の根を元に持つものとして特徴付けられることになります。
さて、位数 $q = p^n$ の有限体 $F_q$ は素体 $F_p$ 上の$n$次元ベクトル空間ですから、体の拡大の一般論によって、ある $F_q$ の元$\alpha$があって $F_q = F_p(\alpha)$ と表され（つまり $F_q$ は$\alpha$を $F_p$ に添加した体であり）、$\alpha$の $F_p$ 上の最小多項式の次数が$n$になります。 この最小多項式は $F_p$ 上で既約なので、これで $F_p$ 上の$n$次の既約多項式の存在が示されました。
ここまでの知識を持って前回の記事を見返し、特に $F_{16}$ について $X^{16}-X$ を $F_2$ 上で既約多項式に分解した結果を再度見直してみます。
\[ X^{16}-X = X(X-1)(X^2+X+1)(X^4+X+1)(X^4+X^3+1)(X^4+X^3+X^2+X+1) \tag{1} \]
$16=2^4$ なので因子に$4$次多項式が含まれることはわかるのですが、そのほかに$1$次と$2$次の多項式も因子に含まれています。そして、
\begin{eqnarray*}
X^4-X &=& X(X-1)(X^2+X+1) \\
X^2-X &=& X(X-1)
\end{eqnarray*}
であり、$F_4$ は $F_2$ 上の $X^4-X$ の最小分解体、$F_{16}$ は $F_2$ 上の $X^{16}-X$ の最小分解体であることを考えると、$X^{16}-X$ が $X^4-X$ を因子に持ち、また $X^4-X$ が $X^2-X$ を因子に持つことから、
\[ F_2 \subset F_4 \subset F_{16} \]
という拡大体の系列ができていることがわかります。
これは一般に次の形で成り立ちます。
（証明）$F_{p^m} \subseteq F_{p^n}$ ならば、$F_{p^n}$ の $F_{p^m}$ 上の拡大次数を$k$とすると、$(p^m)^k = p^n$ より $mk=n$ すなわち $m \mid n$ である。
逆に $m \mid n$ ならば、$mk=n$ とすると、
\[ p^n-1 = (p^m)^k-1 = (p^m-1)((p^m)^{k-1} + \cdots + p^m +1) \]
なので、$\ell = (p^m)^{k-1} + \cdots + p^m +1$ とおくと、$F_p$ 上で
\begin{eqnarray*}
X^{p^n}-X &=& X(X^{p^n-1}-1) \\
&=& X((X^{p^m-1})^\ell -1) \\
&=& X(X^{p^m-1} -1)((X^{p^m-1})^{\ell-1} + \cdots + X^{p^m-1} + 1) \\
&=& (X^{p^m}-X)((X^{p^m-1})^{\ell-1} + \cdots + X^{p^m-1} + 1)
\end{eqnarray*}
が成り立つ。よって $F_{p^n}$ 上で $X^{p^m}-X$ の根が $p^m$ 個存在し、それらは体 $F_{p^m}$ を構成するから $F_{p^m} \subseteq F_{p^n}$ である。□
このことから、$F_p$ 上の多項式 $X^{p^n}-X$ の分解については、次の特徴でまとめられることがわかります。
（証明）①は【定理2】で示したとおり。
②は、$X^{p^m}-X$ が次数$m$の全ての既約多項式を因子に持つことを示せば、①から従う。もし $X^{p^m}-X$ の因子にない次数$m$の既約多項式が存在すると仮定すると、その既約多項式を使って $F_p$ を $F_{p^m}$ に拡大することができ、$X^{p^m}-X$ の別の分解ができてしまうので、多項式環 $F_p[X]$ の一意分解性に矛盾する。
③を示すため、$m \nmid n$ なる$m$に対して、$F_p$ 上既約な次数$m$の多項式 $f(X)$ が $X^{p^n}-X$ の因子に含まれると仮定する。$F_p$ の拡大体 $F_{p^m}$ を考えると、②より $f(X)$ は $X^{p^m}-X$ の因子にも含まれ、$f(X)$ の全ての根は $F_{p^n}$ と $F_{p^m}$ の両方に属する。$K = F_{p^m} \cap F_{p^n}$ とおくと、$K$は加法、乗法と乗法逆元に対して閉じているので $F_{p^m}$ と $F_{p^n}$ の共通の部分体である。よって【定理2】より、ある正整数$k$があって $K = F_{p^k}$ かつ $k \mid m$ かつ $k \mid n$ であるが、一方で $f(X)$ の全ての根が$K$に属することから $X^{p^k}-X$ は $f(X)$ を因子に持ち、$f(X)$ は $F_p$ 上既約で次数$m$だから、拡大 $F_{p^k}/F_p$ の次数$k$は $k \ge m$ をみたす。従って $k=m$ となるしかなく、$m \mid n$ が従うが、仮定より $m \nmid n$ なので矛盾である。
④については、もし $X^{p^m}-X$ が$1$次以上の多項式 $f(X)$ の平方を因子に持ったと仮定すると、
\[ X^{p^m}-X = f(X)^2g(X) \]
と表され、この両辺を形式微分すると標数が$p$であることから、
\[ -1 = f(X)(2f'(X)g(X)+f(X)g'(X)) \]
となって矛盾を生じる。
□
$X^{16}-X$ を $F_2$ 上で分解した式$(1)$を見ると、実際に①③④が成り立っていることがわかり、さらに②の事実から、
$F_2$ 上の$1$次の既約多項式は $X, \ X-1$（あるいは $X, \ X+1$ ）の$2$個
$F_2$ 上の$2$次の既約多項式は $X^2+X+1$ の$1$個
$F_2$ 上の$4$次の既約多項式は $X^4+X+1, \ X^4+X^3+1, \ X^4+X^3+X^2+X+1$ の$3$個
であることがわかります。次数をみると、
\[ 1 \times 2 + 2 \times 1 + 4 \times 3 = 16 \]
となるので、計算が合いますね。
一般に素数$p$と正整数$n$に対して、$F_p$ 上の$n$次のモニックな既約多項式の個数を $\sigma(p,n)$ とおくと、$X^{p^n}-X$ の $F_p$ 上の既約因子への分解を考え、【定理3】を使ってその次数を比較することにより、
\[ p^n = \sum_{d \mid n} d \sigma(p,d) \tag{2} \]
であることがわかります。ここで右辺は$n$の全ての約数$d$にわたって和を取ることを意味します。明らかに $\sigma(p,1)=p$ なので、これを用いて再帰的に $\sigma(p,n)$ が計算できます。$p=2, 3$ のときに実際に計算すると、
\begin{eqnarray*}
\sigma(2,1) && &=& 2 \\
\sigma(2,2) &=& (2^2 - \sigma(2,1))/2 &=& 1 \\
\sigma(2,3) &=& (2^3 - \sigma(2,1))/3 &=& 2 \\
\sigma(2,4) &=& (2^4 - \sigma(2,1) - 2\sigma(2,2))/4 &=& 3 \\
\sigma(2,5) &=& (2^5 - \sigma(2,1))/5 &=& 6 \\
\sigma(2,6) &=& (2^6 - \sigma(2,1)- 2\sigma(2,2)- 3\sigma(2,3))/6 &=& 9 \\
&\cdots& \\
\\
\sigma(3,1) && &=& 3 \\
\sigma(3,2) &=& (3^2 - \sigma(3,1))/2 &=& 3 \\
\sigma(3,3) &=& (3^3 - \sigma(3,1))/3 &=& 8 \\
\sigma(3,4) &=& (3^4 - \sigma(3,1) - 2\sigma(3,2))/4 &=& 18 \\
\sigma(3,5) &=& (3^5 - \sigma(3,1))/5 &=& 48 \\
\sigma(3,6) &=& (3^6 - \sigma(3,1)- 2\sigma(3,2)- 3\sigma(3,3))/6 &=& 116 \\
&\cdots&
\end{eqnarray*}
となります。
もう一つ、前回の記事において、$F_2$ においては既約多項式の根は2乗しても同じ既約多項式の根になる、という現象を見ました。これは一般の標数$p$に対して次のように証明できます（既約多項式でなくても成立します）。
（証明）$F_p$ の拡大体$K$上で $f(\alpha) = 0$ なので、$(f(\alpha))^p = 0$ である。$\displaystyle f(X) = \sum_{i=0}^mc_iX^i$ とすると、標数が$p$だからフロベニウス写像が環準同型であることより、
\[ (f(\alpha))^p = \left( \sum_{i=0}^mc_i \alpha^i \right)^p = \sum_{i=0}^m(c_i)^p (\alpha^i)^p = \sum_{i=0}^m(c_i)^p (\alpha^p)^i \]
ここで係数 $c_i$ は $F_p$ の元だから $0^p=0$ とフェルマーの小定理によって $(c_i)^p = c_i$ である。よって、
\[ f(\alpha^p) = (f(\alpha))^p = 0 \]
が従い、$\alpha^p$ も $f(X)$ の根である。□
これより、$q = p^n$ のとき $F_q$ の$q$個の元は、$F_p$ 上の $X^q-X$ の既約因子のどれに所属するかに基づき、それぞれの既約因子の次数$d$ずつ組になって$p$乗の繰り返しによって巡回します。具体的には、例えば$d$次の既約多項式 $f(X)$ が $X^q-X$ の因子とし、その$1$つの根を$\alpha$とすると、
\[ \alpha, \alpha^p, \alpha^{p^2}, \cdots , \alpha^{p^{d-1}} \]
の$d$個の $F_q$ の元がどれも $f(X)$ の根となり、$f(X)$ の根は$d$個なので、$p$乗の繰り返しによってこれら$d$個の間で巡回します。
もう一度前回の記事の、$F_8$ や $F_{16}$ の原始元のべき表現と既約因子の根との対応を見ると、上の内容がよくわかります。例えば $F_{16}$ では、既約多項式 $X^4+X+1$ の一つの根を $\alpha$ とすると、各既約因子と根との対応は、
\begin{eqnarray*}
X \ &:& \ 0 \\
X-1 \ &:& \ \alpha^0 \\
X^2+X+1 \ &:& \ \alpha^5, \alpha^{10} \\
X^4+X+1 \ &:& \ \alpha^1, \alpha^2, \alpha^4, \alpha^8 \\
X^4+X^3+1 \ &:& \ \alpha^{14}, \alpha^{13}, \alpha^{11}, \alpha^7 \\
X^4+X^3+X^2+X+1 \ &:& \ \alpha^3, \alpha^6, \alpha^{12}, \alpha^9
\end{eqnarray*}
のようになりました。$\alpha^{15}=1$ なので、これらの根を$2$乗すること、すなわち指数で見ると$2$をかけて$\mod 15$ をとることによって、
\begin{eqnarray*}
X-1 \ &:& 0 \to 0\\
X^2+X+1 \ &:& 5 \to 10 \to 5\\
X^4+X+1 \ &:& 1 \to 2 \to 4 \to 8 \to 1\\
X^4+X^3+1 \ &:& 14 \to 13 \to 11 \to 7 \to 14\\
X^4+X^3+X^2+X+1 \ &:& 3 \to 6 \to 12 \to 9 \to 3
\end{eqnarray*}
のようにそれぞれの既約多項式の中で巡回することがわかります。
これでとりあえず前回の記事に関する検証ができたし、これ以上書くとボロが出るので、この辺までにしておきます。
（続く）（前記事）
この過程で見えてきたことを一つずつ検証してみます。
まず単純な話ですが、$F_2$ 上の多項式には次数$n$が何であっても必ず$n$次の既約多項式がある、という事実があります。$2$次ならば $X^2+X+1$ がそうですし、$3$次でも$4$次でもありました。これは標数が一般の素数$p$に対して成り立ちます。
このことを証明するために、有限体の位数（元の数）に関する基本的な定理をまず書いておきます。
【定理1】有限体の位数はある素数$p$と正整数$n$に対して $p^n$ と表されるものに限る。逆に、任意の素数$p$と正整数$n$に対して位数 $p^n$ の有限体が同形を除いて一意に存在し、それは素体 $F_p$ 上の多項式 $X^{p^n}-X$ の最小分解体である。
（証明）$K$を有限体とすると、$\mathbb{Q}$が無限集合だから$K$の標数は$0$ではなく、素数$p$である。$K$は素体 $F_p$ 上の有限次元ベクトル空間なので、次元を$n$とすると$K$の位数は $p^n$ になる。従って有限体の位数は $p^n$ と表されるものに限られる。
素数$p$と正整数$n$に対して $q = p^n$ とし、$F_p$ 上で$q$次の多項式 $f(X) = X^q-X$ を考えると、体の拡大の一般論によって、$f(X)$ の $F_p$ 上の最小分解体が同形を除いて一意に存在する。また $f(X)$ の形式微分は標数が$p$であることから $f'(X) = -1$ なので $f(X)$ は重根を持たず、従って最小分解体上で $f(X)$ は異なる$q$個の根を持つ。$\alpha, \beta$ を $f(X)$ の根とすると、フロベニウス写像が環準同型であることと $\alpha^q = \alpha, \, \beta^q = \beta$ より、
\begin{eqnarray*}
f(\alpha+\beta) &=& (\alpha+\beta)^{p^n} - (\alpha+\beta) = \alpha^{p^n} +\beta^{p^n} - \alpha - \beta = \alpha^q +\beta^q - \alpha - \beta = \alpha + \beta - \alpha - \beta = 0 \\
f(\alpha\beta) &=& (\alpha\beta)^q - \alpha\beta = \alpha^q \beta^q - \alpha\beta = \alpha \beta - \alpha\beta = 0 \\
f(\alpha^{-1}) &=& (\alpha^{-1})^q - \alpha^{-1} = (\alpha^q)^{-1} - \alpha^{-1} = \alpha^{-1} - \alpha^{-1} = 0
\end{eqnarray*}
となるから、$f(X)$ の$q$個の根の集合は体を構成する。従って最小分解体はちょうど$q$個の元を持ち、位数$q$の有限体は存在する。
位数$q$の体$K$の乗法群 $K^\times$ は位数 $q-1$ なので、任意の $K^\times$ の元$\alpha$は $\alpha^{q-1} = 1$ をみたし、従って$K$の$q$個の元は$0$を含め全て $\alpha^q = \alpha$ をみたすから、$f(X)$ の根である。従って $f(X)$ は$K$上$q$個の$1$次式に分解されるから、$K$は $F_p$ 上の $f(X)$ の最小分解体である。従って位数$q$の有限体は同形を除いて一意に定まる。□
平たくいうと、位数 $q = p^n$ の有限体は、$F_p$ の拡大体で多項式 $X^q-X$ の$q$個の根を元に持つものとして特徴付けられることになります。
さて、位数 $q = p^n$ の有限体 $F_q$ は素体 $F_p$ 上の$n$次元ベクトル空間ですから、体の拡大の一般論によって、ある $F_q$ の元$\alpha$があって $F_q = F_p(\alpha)$ と表され（つまり $F_q$ は$\alpha$を $F_p$ に添加した体であり）、$\alpha$の $F_p$ 上の最小多項式の次数が$n$になります。 この最小多項式は $F_p$ 上で既約なので、これで $F_p$ 上の$n$次の既約多項式の存在が示されました。
ここまでの知識を持って前回の記事を見返し、特に $F_{16}$ について $X^{16}-X$ を $F_2$ 上で既約多項式に分解した結果を再度見直してみます。
\[ X^{16}-X = X(X-1)(X^2+X+1)(X^4+X+1)(X^4+X^3+1)(X^4+X^3+X^2+X+1) \tag{1} \]
$16=2^4$ なので因子に$4$次多項式が含まれることはわかるのですが、そのほかに$1$次と$2$次の多項式も因子に含まれています。そして、
\begin{eqnarray*}
X^4-X &=& X(X-1)(X^2+X+1) \\
X^2-X &=& X(X-1)
\end{eqnarray*}
であり、$F_4$ は $F_2$ 上の $X^4-X$ の最小分解体、$F_{16}$ は $F_2$ 上の $X^{16}-X$ の最小分解体であることを考えると、$X^{16}-X$ が $X^4-X$ を因子に持ち、また $X^4-X$ が $X^2-X$ を因子に持つことから、
\[ F_2 \subset F_4 \subset F_{16} \]
という拡大体の系列ができていることがわかります。
これは一般に次の形で成り立ちます。
【定理2】有限体 $F_{p^m}$ と $F_{p^n}$ について、$F_{p^m} \subseteq F_{p^n}$ であることと $m \mid n$ であることは同値である。
（証明）$F_{p^m} \subseteq F_{p^n}$ ならば、$F_{p^n}$ の $F_{p^m}$ 上の拡大次数を$k$とすると、$(p^m)^k = p^n$ より $mk=n$ すなわち $m \mid n$ である。
逆に $m \mid n$ ならば、$mk=n$ とすると、
\[ p^n-1 = (p^m)^k-1 = (p^m-1)((p^m)^{k-1} + \cdots + p^m +1) \]
なので、$\ell = (p^m)^{k-1} + \cdots + p^m +1$ とおくと、$F_p$ 上で
\begin{eqnarray*}
X^{p^n}-X &=& X(X^{p^n-1}-1) \\
&=& X((X^{p^m-1})^\ell -1) \\
&=& X(X^{p^m-1} -1)((X^{p^m-1})^{\ell-1} + \cdots + X^{p^m-1} + 1) \\
&=& (X^{p^m}-X)((X^{p^m-1})^{\ell-1} + \cdots + X^{p^m-1} + 1)
\end{eqnarray*}
が成り立つ。よって $F_{p^n}$ 上で $X^{p^m}-X$ の根が $p^m$ 個存在し、それらは体 $F_{p^m}$ を構成するから $F_{p^m} \subseteq F_{p^n}$ である。□
このことから、$F_p$ 上の多項式 $X^{p^n}-X$ の分解については、次の特徴でまとめられることがわかります。
【定理3】$F_p$ 上の多項式 $X^{p^n}-X$ について次が成り立つ。
① $n$の全ての約数$m$に対し、$X^{p^n}-X$ は $X^{p^m}-X$ を因子に持つ。
② $n$の全ての約数$m$に対し、$X^{p^n}-X$ は次数$m$の全ての既約多項式を因子に持つ。
③ $m$が$n$の約数でなければ、$X^{p^n}-X$ は次数$m$の既約多項式を因子に持たない。
④ $X^{p^n}-X$ は$1$次以上の多項式の平方を因子に持たない。
① $n$の全ての約数$m$に対し、$X^{p^n}-X$ は $X^{p^m}-X$ を因子に持つ。
② $n$の全ての約数$m$に対し、$X^{p^n}-X$ は次数$m$の全ての既約多項式を因子に持つ。
③ $m$が$n$の約数でなければ、$X^{p^n}-X$ は次数$m$の既約多項式を因子に持たない。
④ $X^{p^n}-X$ は$1$次以上の多項式の平方を因子に持たない。
（証明）①は【定理2】で示したとおり。
②は、$X^{p^m}-X$ が次数$m$の全ての既約多項式を因子に持つことを示せば、①から従う。もし $X^{p^m}-X$ の因子にない次数$m$の既約多項式が存在すると仮定すると、その既約多項式を使って $F_p$ を $F_{p^m}$ に拡大することができ、$X^{p^m}-X$ の別の分解ができてしまうので、多項式環 $F_p[X]$ の一意分解性に矛盾する。
③を示すため、$m \nmid n$ なる$m$に対して、$F_p$ 上既約な次数$m$の多項式 $f(X)$ が $X^{p^n}-X$ の因子に含まれると仮定する。$F_p$ の拡大体 $F_{p^m}$ を考えると、②より $f(X)$ は $X^{p^m}-X$ の因子にも含まれ、$f(X)$ の全ての根は $F_{p^n}$ と $F_{p^m}$ の両方に属する。$K = F_{p^m} \cap F_{p^n}$ とおくと、$K$は加法、乗法と乗法逆元に対して閉じているので $F_{p^m}$ と $F_{p^n}$ の共通の部分体である。よって【定理2】より、ある正整数$k$があって $K = F_{p^k}$ かつ $k \mid m$ かつ $k \mid n$ であるが、一方で $f(X)$ の全ての根が$K$に属することから $X^{p^k}-X$ は $f(X)$ を因子に持ち、$f(X)$ は $F_p$ 上既約で次数$m$だから、拡大 $F_{p^k}/F_p$ の次数$k$は $k \ge m$ をみたす。従って $k=m$ となるしかなく、$m \mid n$ が従うが、仮定より $m \nmid n$ なので矛盾である。
④については、もし $X^{p^m}-X$ が$1$次以上の多項式 $f(X)$ の平方を因子に持ったと仮定すると、
\[ X^{p^m}-X = f(X)^2g(X) \]
と表され、この両辺を形式微分すると標数が$p$であることから、
\[ -1 = f(X)(2f'(X)g(X)+f(X)g'(X)) \]
となって矛盾を生じる。
□
$X^{16}-X$ を $F_2$ 上で分解した式$(1)$を見ると、実際に①③④が成り立っていることがわかり、さらに②の事実から、
$F_2$ 上の$1$次の既約多項式は $X, \ X-1$（あるいは $X, \ X+1$ ）の$2$個
$F_2$ 上の$2$次の既約多項式は $X^2+X+1$ の$1$個
$F_2$ 上の$4$次の既約多項式は $X^4+X+1, \ X^4+X^3+1, \ X^4+X^3+X^2+X+1$ の$3$個
であることがわかります。次数をみると、
\[ 1 \times 2 + 2 \times 1 + 4 \times 3 = 16 \]
となるので、計算が合いますね。
一般に素数$p$と正整数$n$に対して、$F_p$ 上の$n$次のモニックな既約多項式の個数を $\sigma(p,n)$ とおくと、$X^{p^n}-X$ の $F_p$ 上の既約因子への分解を考え、【定理3】を使ってその次数を比較することにより、
\[ p^n = \sum_{d \mid n} d \sigma(p,d) \tag{2} \]
であることがわかります。ここで右辺は$n$の全ての約数$d$にわたって和を取ることを意味します。明らかに $\sigma(p,1)=p$ なので、これを用いて再帰的に $\sigma(p,n)$ が計算できます。$p=2, 3$ のときに実際に計算すると、
\begin{eqnarray*}
\sigma(2,1) && &=& 2 \\
\sigma(2,2) &=& (2^2 - \sigma(2,1))/2 &=& 1 \\
\sigma(2,3) &=& (2^3 - \sigma(2,1))/3 &=& 2 \\
\sigma(2,4) &=& (2^4 - \sigma(2,1) - 2\sigma(2,2))/4 &=& 3 \\
\sigma(2,5) &=& (2^5 - \sigma(2,1))/5 &=& 6 \\
\sigma(2,6) &=& (2^6 - \sigma(2,1)- 2\sigma(2,2)- 3\sigma(2,3))/6 &=& 9 \\
&\cdots& \\
\\
\sigma(3,1) && &=& 3 \\
\sigma(3,2) &=& (3^2 - \sigma(3,1))/2 &=& 3 \\
\sigma(3,3) &=& (3^3 - \sigma(3,1))/3 &=& 8 \\
\sigma(3,4) &=& (3^4 - \sigma(3,1) - 2\sigma(3,2))/4 &=& 18 \\
\sigma(3,5) &=& (3^5 - \sigma(3,1))/5 &=& 48 \\
\sigma(3,6) &=& (3^6 - \sigma(3,1)- 2\sigma(3,2)- 3\sigma(3,3))/6 &=& 116 \\
&\cdots&
\end{eqnarray*}
となります。
もう一つ、前回の記事において、$F_2$ においては既約多項式の根は2乗しても同じ既約多項式の根になる、という現象を見ました。これは一般の標数$p$に対して次のように証明できます（既約多項式でなくても成立します）。
【定理4】$f(X)$ を $F_p$ 上の多項式とし、$\alpha$を $F_p$ の拡大体$K$における $f(X)$ の根とすると、$\alpha^p$ も $f(X)$ の根である。従って任意の正整数$n$に対し $\alpha^{p^n}$ も $f(X)$ の根である。
（証明）$F_p$ の拡大体$K$上で $f(\alpha) = 0$ なので、$(f(\alpha))^p = 0$ である。$\displaystyle f(X) = \sum_{i=0}^mc_iX^i$ とすると、標数が$p$だからフロベニウス写像が環準同型であることより、
\[ (f(\alpha))^p = \left( \sum_{i=0}^mc_i \alpha^i \right)^p = \sum_{i=0}^m(c_i)^p (\alpha^i)^p = \sum_{i=0}^m(c_i)^p (\alpha^p)^i \]
ここで係数 $c_i$ は $F_p$ の元だから $0^p=0$ とフェルマーの小定理によって $(c_i)^p = c_i$ である。よって、
\[ f(\alpha^p) = (f(\alpha))^p = 0 \]
が従い、$\alpha^p$ も $f(X)$ の根である。□
これより、$q = p^n$ のとき $F_q$ の$q$個の元は、$F_p$ 上の $X^q-X$ の既約因子のどれに所属するかに基づき、それぞれの既約因子の次数$d$ずつ組になって$p$乗の繰り返しによって巡回します。具体的には、例えば$d$次の既約多項式 $f(X)$ が $X^q-X$ の因子とし、その$1$つの根を$\alpha$とすると、
\[ \alpha, \alpha^p, \alpha^{p^2}, \cdots , \alpha^{p^{d-1}} \]
の$d$個の $F_q$ の元がどれも $f(X)$ の根となり、$f(X)$ の根は$d$個なので、$p$乗の繰り返しによってこれら$d$個の間で巡回します。
もう一度前回の記事の、$F_8$ や $F_{16}$ の原始元のべき表現と既約因子の根との対応を見ると、上の内容がよくわかります。例えば $F_{16}$ では、既約多項式 $X^4+X+1$ の一つの根を $\alpha$ とすると、各既約因子と根との対応は、
\begin{eqnarray*}
X \ &:& \ 0 \\
X-1 \ &:& \ \alpha^0 \\
X^2+X+1 \ &:& \ \alpha^5, \alpha^{10} \\
X^4+X+1 \ &:& \ \alpha^1, \alpha^2, \alpha^4, \alpha^8 \\
X^4+X^3+1 \ &:& \ \alpha^{14}, \alpha^{13}, \alpha^{11}, \alpha^7 \\
X^4+X^3+X^2+X+1 \ &:& \ \alpha^3, \alpha^6, \alpha^{12}, \alpha^9
\end{eqnarray*}
のようになりました。$\alpha^{15}=1$ なので、これらの根を$2$乗すること、すなわち指数で見ると$2$をかけて$\mod 15$ をとることによって、
\begin{eqnarray*}
X-1 \ &:& 0 \to 0\\
X^2+X+1 \ &:& 5 \to 10 \to 5\\
X^4+X+1 \ &:& 1 \to 2 \to 4 \to 8 \to 1\\
X^4+X^3+1 \ &:& 14 \to 13 \to 11 \to 7 \to 14\\
X^4+X^3+X^2+X+1 \ &:& 3 \to 6 \to 12 \to 9 \to 3
\end{eqnarray*}
のようにそれぞれの既約多項式の中で巡回することがわかります。
これでとりあえず前回の記事に関する検証ができたし、これ以上書くとボロが出るので、この辺までにしておきます。
（続く）（前記事）
RICOH THETA を使って360度写真を撮ってみた [日常生活]
今更ながら、360度パノラマ写真が撮れるカメラ（RICOH THETA SC2）を買ったので、テスト的に何か広い場所で景色を撮ろうと出かけてきました。
というわけで、雨の淀川河川敷の風景です。PCだとマウスでつかんでグリグリ回せます。スマホだと自分がグルグル回れば画像もグルグル回るのでより臨場感があります。
このブログへの埋め込みのためには、THETAの公式サイトにアップロードしてもよいのですが、公開範囲がより細かく設定できてスマホのグルグル機能？もある「ハコスコストア」を使うことにしました。
また、下の方には撮影者の姿と指が写っていて不恰好ですが、一応ボカシを入れてちょっとは見やすくしました。360度写真といってもデータは普通のJPEGファイルなので、フリーの画像編集ソフトで加工できます。
全体の雰囲気が手軽に記録できるので、これからちょくちょく使おうかと。
というわけで、雨の淀川河川敷の風景です。PCだとマウスでつかんでグリグリ回せます。スマホだと自分がグルグル回れば画像もグルグル回るのでより臨場感があります。
このブログへの埋め込みのためには、THETAの公式サイトにアップロードしてもよいのですが、公開範囲がより細かく設定できてスマホのグルグル機能？もある「ハコスコストア」を使うことにしました。
また、下の方には撮影者の姿と指が写っていて不恰好ですが、一応ボカシを入れてちょっとは見やすくしました。360度写真といってもデータは普通のJPEGファイルなので、フリーの画像編集ソフトで加工できます。
全体の雰囲気が手軽に記録できるので、これからちょくちょく使おうかと。
有限体の勉強 〜標数2の有限体の加算乗算表を作る〜 [数学]
自分が有限体についてあまりに無知なので、改めて勉強してみました。
有限体とは文字どおり、有限個の元で構成される体（四則演算が定義された代数系）のことですが、これについては、
① 有限体の位数（元の数）$q$は、ある素数$p$と正整数$n$によって $q=p^n$ で表されるものに限る。
② 位数 $p^n$ の有限体は同型を除いて唯一存在し、その標数は$p$である。
ということがどの本にも書いてあります。以下では位数$q$の有限体を $F_q$ で表します。
では、例えば標数$2$の有限体を考えると、小さい方から $F_2, F_4, F_8, F_{16}, \cdots$ という有限体が存在することになりますが、これらがどのような構造をしているかについてはなかなかピンときません。なので、自分で手を動かして考えてみました。
(1) $F_2$ の構造
まず一番簡単な $F_2$ から始めます。これは単に整数環 $\mathbb{Z}$ をイデアル $2\mathbb{Z}$ で割った剰余環がそのまま体になったもの、すなわち $F_2 = \mathbb{Z}/2\mathbb{Z}$ なので、その加算表と乗算表は次のようになります。
(2) $F_4$ の構造
$F_2$ に係数をもつ多項式環 $F_2[X]$ を考えます。$F_2$ 上の$2$次の多項式は、
\[ X^2, \quad X^2+1, \quad X^2+X, \quad X^2+X+1 \]
の$4$通りですが、このうち $X^2+X+1$ は$0$も$1$も根にならないので、$1$次の因子で分解できない既約多項式です（他の$3$つが可約であることはすぐわかります）。従って、$F_2[X]$ をイデアル $(X^2+X+1)$ で割った剰余環 $F_2[X]/(X^2+X+1)$ は体になり、拡大次数$2$の $F_2$ の拡大体です。これは位数 $2^2=4$ をもつので、これが $F_4$ に他ならないことになります。
もっと直感的に考えると、$X^2+X+1$ の$1$つの根 $\alpha$ を考え、それを $F_2$ に添加した根体 $F_2(\alpha)$ が $F_4$ である、ということになります。
この $\alpha$ を使うと、$F_4$ は基底 $(\alpha, 1)$ を持つ $F_2$ 上の$2$次元ベクトル空間なので、$F_4$ の元は、
\[ 0, \quad 1, \quad \alpha, \quad \alpha+1 \]
の$4$つになります。これらを簡単に
\[ 00, \quad 01, \quad 10, \quad 11 \]
と表し、「ベクトル表現」と呼びます。このベクトル表現を用いて加算表、乗算表を作ると、次のようになります。
ここで加算表を作るのは、単にベクトル空間における加算なので、それぞれの係数を $F_2$上で加算すればいいだけです。問題は乗算表ですが、普通に $\alpha$ 混じりの多項式と考えて乗算し、
\[ \alpha^2 = \alpha + 1 \]
を使って $\alpha^2$ の項を消せば答えが出ます（標数$2$なのでマイナスとプラスの違いはないことに注意）。少し面倒ですがここまでくらいは何とかなります。
黄色で塗った部分は $F_2$ に相当し、$F_2$ が $F_4$ の部分体であることがわかります。
ところで、$F_4$ 上の多項式として、
\begin{eqnarray*}
X^4-X &=& X(X-1)(X^2+X+1) \\
&=& X(X-1)(X-\alpha)(X-(\alpha+1))
\end{eqnarray*}
が成り立つので、$F_4$ は $F_2$ 上の多項式 $X^4-X$ の最小分解体として特徴づけられます。これは実際には一般の有限体 $F_q \ (q=p^n)$ についても成立し、$F_q$ は $F_p$ 上の多項式 $X^q-X$ の最小分解体となります。
(3) $F_8$ の構造
$F_4$ でやったことと同じようにして $F_2$ から $F_8$ を構成します。$F_2$ 上の多項式 $X^8-X$ は、
\[ X^8-X = X(X-1)(X^3+X+1)(X^3+X^2+1) \]
と既約多項式に分解されるので、このうち$3$次の既約多項式の$1$つ $X^3+X+1$ をとります（これが既約になることは、もし可約ならば$1$次の因子を持つので、$X$に$0$または$1$を代入すると$0$になるはずですが、そうはならないことからわかります）。この多項式の$1$つの根 $\alpha$ を $F_2$ に添加した拡大体 $F_2(\alpha)$ を考えると、これは拡大次数$3$の $F_2$ の拡大体ですから位数が $2^3=8$ となって、$F_8$ と同型になります。
$F_4$ と同じように、基底を $(\alpha^2, \alpha, 1)$ としたベクトル表現で加算表と乗算表を作ることを考えます。加算表は簡単で、次のようになります。
乗算表についても地道に計算して $\alpha^3 = \alpha+1$ を使って $\alpha$ の$3$次以上の項を消せばよいのですが、なにぶん埋めるべきマスの数が多いのでとても面倒です。もうちょっと楽をすることを考えます。
実は $F_8$ の元のうち$0$を除いた$7$個については、$\alpha$ のべき乗との間に次の関係があります。
これくらいの計算はまだ頑張る気になる範囲です。これを見ると、$\alpha$ は $F_8$ の乗法群 $F_8^\times$ の原始元になっていることがわかります。$F_8^\times$ の位数は$7$なので $\alpha^7 = 1 = \alpha^0$ です。すなわち $\alpha$ の指数は $\mod 7$ で計算すればよいわけです。
べき表現だと $F_8^\times$ の乗算表はEXCELなどのスプレッドシートで簡単に作れます。指数を足し算して $\mod 7$ を取ればいいのです。指数だけ記載すると次の表になります。
これをベクトル表現に置き換えて、$0$の行と列を付け加えると、次の乗算表が出来上がります。
これで $F_8$ 加算表と乗算表が書けました。黄色で塗った部分は $F_2$ に相当し、$F_2$ が $F_8$ の部分体であることがわかります。一方で $F_4$ は $F_8$ の部分体にはなりません。なぜなら $4^n=8$ となる正整数$n$が存在しないからです。
ところで、$F_2$ 上の多項式 $X^8-X$ の各既約因子の根をべき表現で表すと、
\begin{eqnarray*}
X \ &:& \ 0 \\
X-1 \ &:& \ \alpha^0 \\
X^3+X+1 \ &:& \ \alpha^1, \alpha^2, \alpha^4 \\
X^3+X^2+1 \ &:& \ \alpha^3, \alpha^6, \alpha^5
\end{eqnarray*}
となります。この場合、$2$つの$3$次の既約多項式のどちらをとっても、その根は $F_8^\times$ の原始元になり、同様な $F_8$ の加算表と乗算表が作れます。また既約多項式の根は$2$乗しても同じ既約多項式の根になっていることがわかります。これは偶然ではなく、比較的簡単に証明できる事実です。
(4) $F_{16}$ の構造
$F_{16}$ の加算表と乗算表の作り方も、$F_8$ のやり方を踏襲できます。$F_2$ 上の多項式 $X^{16}-X$ は、
\[ X^{16}-X = X(X-1)(X^2+X+1)(X^4+X+1)(X^4+X^3+1)(X^4+X^3+X^2+X+1) \]
と既約多項式に分解されるので、このうち$4$次の既約多項式の$1$つ $X^4+X+1$ をとります（既約性の確認は$3$次と違って一手間かかります）。この多項式の$1$つの根 $\alpha$ を $F_2$ に添加した拡大体 $F_2(\alpha)$ を考えると、これは拡大次数$4$の $F_2$ の拡大体ですから位数が $2^4=16$ となって、$F_{16}$ と同型になります。
基底を $(\alpha^3, \alpha^2, \alpha, 1)$ としたベクトル表現で、まず加算表を作ると次のようになります。
乗算表を作るために、$F_8$ でやったのと同様に、$\alpha$ のべき表現とベクトル表現との対応表を作ります。
$F_{16}^\times$ の位数は$15$なので $\alpha^{15} = 1 = \alpha^0$ です。すなわち $\alpha$ の指数は $\mod 15$ で計算すればよいわけです。$F_8$ でやったのと同様にべき表現での乗算表をEXCELなどのスプレッドシートで作り、それをベクトル表現に置き換えて$0$の行と列を追加すると、次のように $F_{16}$ の乗算表が出来上がります。
これで $F_{16}$ の加算表と乗算表が書けました。黄色で塗ったのは $F_4$ に相当する部分で、$F_4$ が $F_{16}$ の部分体になることがわかります。もちろん $F_2$ も $F_{16}$ の部分体ですが、$F_8$ は $F_{16}$ の部分体にはなりません。
ところで、$F_2$ 上の多項式 $X^{16}-X$ の各既約因子の根をべき表現で表すと、
\begin{eqnarray*}
X \ &:& \ 0 \\
X-1 \ &:& \ \alpha^0 \\
X^2+X+1 \ &:& \ \alpha^5, \alpha^{10} \\
X^4+X+1 \ &:& \ \alpha^1, \alpha^2, \alpha^4, \alpha^8 \\
X^4+X^3+1 \ &:& \ \alpha^{14}, \alpha^{13}, \alpha^{11}, \alpha^7 \\
X^4+X^3+X^2+X+1 \ &:& \ \alpha^3, \alpha^6, \alpha^{12}, \alpha^9
\end{eqnarray*}
となります。この場合、$3$つの$4$次の既約多項式のうち、$X^4+X+1$ と $X^4+X^3+1$ の根は $F_{16}^\times$ の原始元になりますが、$X^4+X^3+X^2+X+1$ の根は原始元にはなりません（もちろん $X^2+X+1$ の根も原始元にはなりません）。$X^4+X^3+X^2+X+1$ の根をもとにベクトル表現を考えると、乗算表を作るときに上での方法が使えずに苦労する羽目になります。
既約多項式の根が$2$乗しても同じ既約多項式の根になっているのは、$F_8$ や $F_4$ など他の標数2の有限体と同様です。
とりあえずここまで。
（本記事の加算表と乗算表は、LibreOfficeで作成したものをこのサイトを使用してHTMLに変換したものです。サイトの作成者様に感謝いたします。）
（続く）
有限体とは文字どおり、有限個の元で構成される体（四則演算が定義された代数系）のことですが、これについては、
① 有限体の位数（元の数）$q$は、ある素数$p$と正整数$n$によって $q=p^n$ で表されるものに限る。
② 位数 $p^n$ の有限体は同型を除いて唯一存在し、その標数は$p$である。
ということがどの本にも書いてあります。以下では位数$q$の有限体を $F_q$ で表します。
では、例えば標数$2$の有限体を考えると、小さい方から $F_2, F_4, F_8, F_{16}, \cdots$ という有限体が存在することになりますが、これらがどのような構造をしているかについてはなかなかピンときません。なので、自分で手を動かして考えてみました。
(1) $F_2$ の構造
まず一番簡単な $F_2$ から始めます。これは単に整数環 $\mathbb{Z}$ をイデアル $2\mathbb{Z}$ で割った剰余環がそのまま体になったもの、すなわち $F_2 = \mathbb{Z}/2\mathbb{Z}$ なので、その加算表と乗算表は次のようになります。
| + | 0 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| × | 0 | 1 |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
(2) $F_4$ の構造
$F_2$ に係数をもつ多項式環 $F_2[X]$ を考えます。$F_2$ 上の$2$次の多項式は、
\[ X^2, \quad X^2+1, \quad X^2+X, \quad X^2+X+1 \]
の$4$通りですが、このうち $X^2+X+1$ は$0$も$1$も根にならないので、$1$次の因子で分解できない既約多項式です（他の$3$つが可約であることはすぐわかります）。従って、$F_2[X]$ をイデアル $(X^2+X+1)$ で割った剰余環 $F_2[X]/(X^2+X+1)$ は体になり、拡大次数$2$の $F_2$ の拡大体です。これは位数 $2^2=4$ をもつので、これが $F_4$ に他ならないことになります。
もっと直感的に考えると、$X^2+X+1$ の$1$つの根 $\alpha$ を考え、それを $F_2$ に添加した根体 $F_2(\alpha)$ が $F_4$ である、ということになります。
この $\alpha$ を使うと、$F_4$ は基底 $(\alpha, 1)$ を持つ $F_2$ 上の$2$次元ベクトル空間なので、$F_4$ の元は、
\[ 0, \quad 1, \quad \alpha, \quad \alpha+1 \]
の$4$つになります。これらを簡単に
\[ 00, \quad 01, \quad 10, \quad 11 \]
と表し、「ベクトル表現」と呼びます。このベクトル表現を用いて加算表、乗算表を作ると、次のようになります。
| + | 00 | 01 | 10 | 11 |
| 00 | 00 | 01 | 10 | 11 |
| 01 | 01 | 00 | 11 | 10 |
| 10 | 10 | 11 | 00 | 01 |
| 11 | 11 | 10 | 01 | 00 |
| × | 00 | 01 | 10 | 11 |
| 00 | 00 | 00 | 00 | 00 |
| 01 | 00 | 01 | 10 | 11 |
| 10 | 00 | 10 | 11 | 01 |
| 11 | 00 | 11 | 01 | 10 |
ここで加算表を作るのは、単にベクトル空間における加算なので、それぞれの係数を $F_2$上で加算すればいいだけです。問題は乗算表ですが、普通に $\alpha$ 混じりの多項式と考えて乗算し、
\[ \alpha^2 = \alpha + 1 \]
を使って $\alpha^2$ の項を消せば答えが出ます（標数$2$なのでマイナスとプラスの違いはないことに注意）。少し面倒ですがここまでくらいは何とかなります。
黄色で塗った部分は $F_2$ に相当し、$F_2$ が $F_4$ の部分体であることがわかります。
ところで、$F_4$ 上の多項式として、
\begin{eqnarray*}
X^4-X &=& X(X-1)(X^2+X+1) \\
&=& X(X-1)(X-\alpha)(X-(\alpha+1))
\end{eqnarray*}
が成り立つので、$F_4$ は $F_2$ 上の多項式 $X^4-X$ の最小分解体として特徴づけられます。これは実際には一般の有限体 $F_q \ (q=p^n)$ についても成立し、$F_q$ は $F_p$ 上の多項式 $X^q-X$ の最小分解体となります。
(3) $F_8$ の構造
$F_4$ でやったことと同じようにして $F_2$ から $F_8$ を構成します。$F_2$ 上の多項式 $X^8-X$ は、
\[ X^8-X = X(X-1)(X^3+X+1)(X^3+X^2+1) \]
と既約多項式に分解されるので、このうち$3$次の既約多項式の$1$つ $X^3+X+1$ をとります（これが既約になることは、もし可約ならば$1$次の因子を持つので、$X$に$0$または$1$を代入すると$0$になるはずですが、そうはならないことからわかります）。この多項式の$1$つの根 $\alpha$ を $F_2$ に添加した拡大体 $F_2(\alpha)$ を考えると、これは拡大次数$3$の $F_2$ の拡大体ですから位数が $2^3=8$ となって、$F_8$ と同型になります。
$F_4$ と同じように、基底を $(\alpha^2, \alpha, 1)$ としたベクトル表現で加算表と乗算表を作ることを考えます。加算表は簡単で、次のようになります。
| + | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
| 000 | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
| 001 | 001 | 000 | 011 | 010 | 101 | 100 | 111 | 110 |
| 010 | 010 | 011 | 000 | 001 | 110 | 111 | 100 | 101 |
| 011 | 011 | 010 | 001 | 000 | 111 | 110 | 101 | 100 |
| 100 | 100 | 101 | 110 | 111 | 000 | 001 | 010 | 011 |
| 101 | 101 | 100 | 111 | 110 | 001 | 000 | 011 | 010 |
| 110 | 110 | 111 | 100 | 101 | 010 | 011 | 000 | 001 |
| 111 | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
乗算表についても地道に計算して $\alpha^3 = \alpha+1$ を使って $\alpha$ の$3$次以上の項を消せばよいのですが、なにぶん埋めるべきマスの数が多いのでとても面倒です。もうちょっと楽をすることを考えます。
実は $F_8$ の元のうち$0$を除いた$7$個については、$\alpha$ のべき乗との間に次の関係があります。
| べき表現 | ベクトル表現 |
| $\alpha^0$ | 001 |
| $\alpha^1$ | 010 |
| $\alpha^3$ | 011 |
| $\alpha^2$ | 100 |
| $\alpha^6$ | 101 |
| $\alpha^4$ | 110 |
| $\alpha^5$ | 111 |
これくらいの計算はまだ頑張る気になる範囲です。これを見ると、$\alpha$ は $F_8$ の乗法群 $F_8^\times$ の原始元になっていることがわかります。$F_8^\times$ の位数は$7$なので $\alpha^7 = 1 = \alpha^0$ です。すなわち $\alpha$ の指数は $\mod 7$ で計算すればよいわけです。
べき表現だと $F_8^\times$ の乗算表はEXCELなどのスプレッドシートで簡単に作れます。指数を足し算して $\mod 7$ を取ればいいのです。指数だけ記載すると次の表になります。
| × | 0 | 1 | 3 | 2 | 6 | 4 | 5 |
| 0 | 0 | 1 | 3 | 2 | 6 | 4 | 5 |
| 1 | 1 | 2 | 4 | 3 | 0 | 5 | 6 |
| 3 | 3 | 4 | 6 | 5 | 2 | 0 | 1 |
| 2 | 2 | 3 | 5 | 4 | 1 | 6 | 0 |
| 6 | 6 | 0 | 2 | 1 | 5 | 3 | 4 |
| 4 | 4 | 5 | 0 | 6 | 3 | 1 | 2 |
| 5 | 5 | 6 | 1 | 0 | 4 | 2 | 3 |
これをベクトル表現に置き換えて、$0$の行と列を付け加えると、次の乗算表が出来上がります。
| × | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
| 000 | 000 | 000 | 000 | 000 | 000 | 000 | 000 | 000 |
| 001 | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
| 010 | 000 | 010 | 100 | 110 | 011 | 001 | 111 | 101 |
| 011 | 000 | 011 | 110 | 101 | 111 | 100 | 001 | 010 |
| 100 | 000 | 100 | 011 | 111 | 110 | 010 | 101 | 001 |
| 101 | 000 | 101 | 001 | 100 | 010 | 111 | 011 | 110 |
| 110 | 000 | 110 | 111 | 001 | 101 | 011 | 010 | 100 |
| 111 | 000 | 111 | 101 | 010 | 001 | 110 | 100 | 011 |
これで $F_8$ 加算表と乗算表が書けました。黄色で塗った部分は $F_2$ に相当し、$F_2$ が $F_8$ の部分体であることがわかります。一方で $F_4$ は $F_8$ の部分体にはなりません。なぜなら $4^n=8$ となる正整数$n$が存在しないからです。
ところで、$F_2$ 上の多項式 $X^8-X$ の各既約因子の根をべき表現で表すと、
\begin{eqnarray*}
X \ &:& \ 0 \\
X-1 \ &:& \ \alpha^0 \\
X^3+X+1 \ &:& \ \alpha^1, \alpha^2, \alpha^4 \\
X^3+X^2+1 \ &:& \ \alpha^3, \alpha^6, \alpha^5
\end{eqnarray*}
となります。この場合、$2$つの$3$次の既約多項式のどちらをとっても、その根は $F_8^\times$ の原始元になり、同様な $F_8$ の加算表と乗算表が作れます。また既約多項式の根は$2$乗しても同じ既約多項式の根になっていることがわかります。これは偶然ではなく、比較的簡単に証明できる事実です。
(4) $F_{16}$ の構造
$F_{16}$ の加算表と乗算表の作り方も、$F_8$ のやり方を踏襲できます。$F_2$ 上の多項式 $X^{16}-X$ は、
\[ X^{16}-X = X(X-1)(X^2+X+1)(X^4+X+1)(X^4+X^3+1)(X^4+X^3+X^2+X+1) \]
と既約多項式に分解されるので、このうち$4$次の既約多項式の$1$つ $X^4+X+1$ をとります（既約性の確認は$3$次と違って一手間かかります）。この多項式の$1$つの根 $\alpha$ を $F_2$ に添加した拡大体 $F_2(\alpha)$ を考えると、これは拡大次数$4$の $F_2$ の拡大体ですから位数が $2^4=16$ となって、$F_{16}$ と同型になります。
基底を $(\alpha^3, \alpha^2, \alpha, 1)$ としたベクトル表現で、まず加算表を作ると次のようになります。
| + | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
| 0000 | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
| 0001 | 0001 | 0000 | 0011 | 0010 | 0101 | 0100 | 0111 | 0110 | 1001 | 1000 | 1011 | 1010 | 1101 | 1100 | 1111 | 1110 |
| 0010 | 0010 | 0011 | 0000 | 0001 | 0110 | 0111 | 0100 | 0101 | 1010 | 1011 | 1000 | 1001 | 1110 | 1111 | 1100 | 1101 |
| 0011 | 0011 | 0010 | 0001 | 0000 | 0111 | 0110 | 0101 | 0100 | 1011 | 1010 | 1001 | 1000 | 1111 | 1110 | 1101 | 1100 |
| 0100 | 0100 | 0101 | 0110 | 0111 | 0000 | 0001 | 0010 | 0011 | 1100 | 1101 | 1110 | 1111 | 1000 | 1001 | 1010 | 1011 |
| 0101 | 0101 | 0100 | 0111 | 0110 | 0001 | 0000 | 0011 | 0010 | 1101 | 1100 | 1111 | 1110 | 1001 | 1000 | 1011 | 1010 |
| 0110 | 0110 | 0111 | 0100 | 0101 | 0010 | 0011 | 0000 | 0001 | 1110 | 1111 | 1100 | 1101 | 1010 | 1011 | 1000 | 1001 |
| 0111 | 0111 | 0110 | 0101 | 0100 | 0011 | 0010 | 0001 | 0000 | 1111 | 1110 | 1101 | 1100 | 1011 | 1010 | 1001 | 1000 |
| 1000 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 |
| 1001 | 1001 | 1000 | 1011 | 1010 | 1101 | 1100 | 1111 | 1110 | 0001 | 0000 | 0011 | 0010 | 0101 | 0100 | 0111 | 0110 |
| 1010 | 1010 | 1011 | 1000 | 1001 | 1110 | 1111 | 1100 | 1101 | 0010 | 0011 | 0000 | 0001 | 0110 | 0111 | 0100 | 0101 |
| 1011 | 1011 | 1010 | 1001 | 1000 | 1111 | 1110 | 1101 | 1100 | 0011 | 0010 | 0001 | 0000 | 0111 | 0110 | 0101 | 0100 |
| 1100 | 1100 | 1101 | 1110 | 1111 | 1000 | 1001 | 1010 | 1011 | 0100 | 0101 | 0110 | 0111 | 0000 | 0001 | 0010 | 0011 |
| 1101 | 1101 | 1100 | 1111 | 1110 | 1001 | 1000 | 1011 | 1010 | 0101 | 0100 | 0111 | 0110 | 0001 | 0000 | 0011 | 0010 |
| 1110 | 1110 | 1111 | 1100 | 1101 | 1010 | 1011 | 1000 | 1001 | 0110 | 0111 | 0100 | 0101 | 0010 | 0011 | 0000 | 0001 |
| 1111 | 1111 | 1110 | 1101 | 1100 | 1011 | 1010 | 1001 | 1000 | 0111 | 0110 | 0101 | 0100 | 0011 | 0010 | 0001 | 0000 |
乗算表を作るために、$F_8$ でやったのと同様に、$\alpha$ のべき表現とベクトル表現との対応表を作ります。
| べき表現 | ベクトル表現 |
| $\alpha^0$ | 0001 |
| $\alpha^1$ | 0010 |
| $\alpha^4$ | 0011 |
| $\alpha^2$ | 0100 |
| $\alpha^8$ | 0101 |
| $\alpha^5$ | 0110 |
| $\alpha^{10}$ | 0111 |
| $\alpha^3$ | 1000 |
| $\alpha^{14}$ | 1001 |
| $\alpha^9$ | 1010 |
| $\alpha^7$ | 1011 |
| $\alpha^6$ | 1100 |
| $\alpha^{13}$ | 1101 |
| $\alpha^{11}$ | 1110 |
| $\alpha^{12}$ | 1111 |
$F_{16}^\times$ の位数は$15$なので $\alpha^{15} = 1 = \alpha^0$ です。すなわち $\alpha$ の指数は $\mod 15$ で計算すればよいわけです。$F_8$ でやったのと同様にべき表現での乗算表をEXCELなどのスプレッドシートで作り、それをベクトル表現に置き換えて$0$の行と列を追加すると、次のように $F_{16}$ の乗算表が出来上がります。
| × | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
| 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 | 0000 |
| 0001 | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
| 0010 | 0000 | 0010 | 0100 | 0110 | 1000 | 1010 | 1100 | 1110 | 0011 | 0001 | 0111 | 0101 | 1011 | 1001 | 1111 | 1101 |
| 0011 | 0000 | 0011 | 0110 | 0101 | 1100 | 1111 | 1010 | 1001 | 1011 | 1000 | 1001 | 1110 | 0111 | 0100 | 0001 | 0010 |
| 0100 | 0000 | 0100 | 1000 | 1100 | 0011 | 0111 | 1011 | 1111 | 0110 | 0010 | 1110 | 1010 | 0101 | 0001 | 1101 | 1001 |
| 0101 | 0000 | 0101 | 1010 | 1111 | 0111 | 0010 | 1101 | 1000 | 1110 | 1011 | 0100 | 0001 | 1001 | 1100 | 0011 | 0110 |
| 0110 | 0000 | 0110 | 1100 | 1010 | 1011 | 1101 | 0111 | 0001 | 0101 | 0011 | 1001 | 1111 | 1110 | 1000 | 0010 | 0100 |
| 0111 | 0000 | 0111 | 1110 | 1001 | 1111 | 1000 | 0001 | 0110 | 1101 | 1010 | 0011 | 0100 | 0010 | 0101 | 1100 | 1011 |
| 1000 | 0000 | 1000 | 0011 | 1011 | 0110 | 1110 | 0101 | 1101 | 1100 | 0100 | 1111 | 0111 | 1010 | 0010 | 1001 | 0001 |
| 1001 | 0000 | 1001 | 0001 | 1000 | 0010 | 1011 | 0011 | 1010 | 0100 | 1101 | 0101 | 1100 | 0110 | 1111 | 0111 | 1110 |
| 1010 | 0000 | 1010 | 0111 | 1001 | 1110 | 0100 | 1001 | 0011 | 1111 | 0101 | 1000 | 0010 | 0001 | 1011 | 0110 | 1100 |
| 1011 | 0000 | 1011 | 0101 | 1110 | 1010 | 0001 | 1111 | 0100 | 0111 | 1100 | 0010 | 1001 | 1101 | 0110 | 1000 | 0011 |
| 1100 | 0000 | 1100 | 1011 | 0111 | 0101 | 1001 | 1110 | 0010 | 1010 | 0110 | 0001 | 1101 | 1111 | 0011 | 0100 | 1000 |
| 1101 | 0000 | 1101 | 1001 | 0100 | 0001 | 1100 | 1000 | 0101 | 0010 | 1111 | 1011 | 0110 | 0011 | 1110 | 1010 | 0111 |
| 1110 | 0000 | 1110 | 1111 | 0001 | 1101 | 0011 | 0010 | 1100 | 1001 | 0111 | 0110 | 1000 | 0100 | 1010 | 1011 | 0101 |
| 1111 | 0000 | 1111 | 1101 | 0010 | 1001 | 0110 | 0100 | 1011 | 0001 | 1110 | 1100 | 0011 | 1000 | 0111 | 0101 | 1010 |
これで $F_{16}$ の加算表と乗算表が書けました。黄色で塗ったのは $F_4$ に相当する部分で、$F_4$ が $F_{16}$ の部分体になることがわかります。もちろん $F_2$ も $F_{16}$ の部分体ですが、$F_8$ は $F_{16}$ の部分体にはなりません。
ところで、$F_2$ 上の多項式 $X^{16}-X$ の各既約因子の根をべき表現で表すと、
\begin{eqnarray*}
X \ &:& \ 0 \\
X-1 \ &:& \ \alpha^0 \\
X^2+X+1 \ &:& \ \alpha^5, \alpha^{10} \\
X^4+X+1 \ &:& \ \alpha^1, \alpha^2, \alpha^4, \alpha^8 \\
X^4+X^3+1 \ &:& \ \alpha^{14}, \alpha^{13}, \alpha^{11}, \alpha^7 \\
X^4+X^3+X^2+X+1 \ &:& \ \alpha^3, \alpha^6, \alpha^{12}, \alpha^9
\end{eqnarray*}
となります。この場合、$3$つの$4$次の既約多項式のうち、$X^4+X+1$ と $X^4+X^3+1$ の根は $F_{16}^\times$ の原始元になりますが、$X^4+X^3+X^2+X+1$ の根は原始元にはなりません（もちろん $X^2+X+1$ の根も原始元にはなりません）。$X^4+X^3+X^2+X+1$ の根をもとにベクトル表現を考えると、乗算表を作るときに上での方法が使えずに苦労する羽目になります。
既約多項式の根が$2$乗しても同じ既約多項式の根になっているのは、$F_8$ や $F_4$ など他の標数2の有限体と同様です。
とりあえずここまで。
（本記事の加算表と乗算表は、LibreOfficeで作成したものをこのサイトを使用してHTMLに変換したものです。サイトの作成者様に感謝いたします。）
（続く）
