SSブログ

有限体の勉強 〜位数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)$ を基底とする「ベクトル表現」との対応づけができます。これが次の表です。

べき表現 負べき表現 ベクトル表現 最小多項式
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$ の原始元にならないので、原始多項式ではありません。既約多項式が原始多項式かどうかを係数から簡単に見分ける方法があるのかないのか、今の僕はその知見を持っていません。

(続く)(前記事)

nice!(0)  コメント(0) 
共通テーマ:学問

nice! 0

コメント 0

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。

※ブログオーナーが承認したコメントのみ表示されます。