有限体の勉強 〜有限体をExcel上で計算する〜 [数学]
「有限体の勉強」という記事をいくつか書いてきましたが、これらの記事を書くために多くの有限体の四則演算を実際に行う必要が生じ、手計算ではとても大変なのでスプレッドシートを使ってきました。ここでその具体的な方法を紹介します。なお、ここではスプレッドシートとは一般用語の「表計算ソフト」の意味で使っており、Excelが代表的ですが LibreOffice(Calc) や Googleスプレッドシートも同様の操作になります。
有限体といっても、本記事では標数$2$の有限体を対象とします。標数が$2$以外の有限体はビット演算関数が使えないのでかなり複雑になるからです。
例としてリード・ソロモン符号の記事でも使った $F_{256}$ の場合を考えます。
まず、この体の元をどう表現するかを決める必要があります。そのために必要なのは $F_{256}$ の原始多項式です。これは $F_2$ 上の$8$次の既約多項式で、その根が $F_{256}$ の原始元になるもののことです。一般に原始多項式は試行錯誤で探し出すことになりますが、いまの場合は、
\[ X^8+X^4+X^3+X^2+1 \]
が原始多項式になることが知られていますのでこれを使い、その一つの根を$\alpha$と書きます。このとき、
\[ \alpha^8 = \alpha^4+\alpha^3+\alpha^2+1 \]
が成り立つので（標数$2$なのでプラスとマイナスの区別はありません）、$\alpha$のべき乗について、
\begin{eqnarray*}
\alpha^0 &=& && && && && && && && \alpha^0 \\
\alpha^1 &=& && && && && && && \alpha^1 \\
&\cdots& \\
\alpha^7 &=& \alpha^7 \\
\alpha^8 &=& && && && \alpha^4 &+& \alpha^3 &+& \alpha^2 && &+& \alpha^0 \\
\alpha^9 &=& && && \alpha^5 &+& \alpha^4 &+& \alpha^3 && &+& \alpha^1 \\
&\cdots& \\
\alpha^{253} &=& && \alpha^6 && && && &+& \alpha^2 &+& \alpha^1 &+& \alpha^0 \\
\alpha^{254} &=& \alpha^7 && && && &+& \alpha^3 &+& \alpha^2 &+& \alpha^1
\end{eqnarray*}
という1対1の対応ができ、$0$を除く $F_{256}$ の元が網羅されます（$\alpha^{255} = \alpha^0 = 1$ です）。左辺をべき表現、右辺をベクトル表現といいます。
Excel上でべき表現とベクトル表現をどうデータ化するかですが、べき表現は指数をそのまま整数値で、ベクトル表現は$\alpha$を$2$に置き換えて計算した数値でデータ化するのが一番扱い易いです。後者はどういうことかというと、例えば
\[ \alpha^4+\alpha^3+\alpha^2+\alpha^0 \quad \to \quad 2^4+2^3+2^2+2^0 = 29 \]
と数値化して扱うということです。そしてExcel上ではこのベクトル表現の数値化を基本とします。なぜなら BITXOR 関数などのビット演算関数が使えることと、べき表現は$0$を扱うことができないからです。
とはいえ、後で説明するようにべき表現も頻繁に使いますので、Excel上でべき表現とベクトル表現の対応表を作ることから始めます。縦にべき表現として$0$から$254$までを並べ、その右側の列に次のようにしてベクトル表現を入れます。$1$行目にべき表現$0$に対してベクトル表現$1$を入れます。$2$行目以降は一つ上の行の数値を$2$進法のビット列とみなし、それを BITLSHIFT 関数で左に$1$ビットシフトし、BITAND 関数で下$8$ビットだけをとり、さらに一つ上の行の数値の$7$ビット目が$1$ならば（つまり$128$以上ならば）$2^4+2^3+2^2+2^0 = 29$ との排他的論理和を BITXOR 関数で入れます。これをべき表現$254$の行まで繰り返すと、対応表が出来上がります。
この対応表はべき表現順に並んでいますので、これを丸ごとコピーして値ペーストし、左右を入れ替えてベクトル表現順に並べ替えた対応表も作っておきます。
言葉ではわかりにくいので、これらの対応表を LibreOffice で作ったものをここにアップロードします。ダウンロードしてセル内の数式を確認してください。Excelでも開けます。
対応表ができあがったら、これは一つのシートとして置いておき（シート名を「対応表」とします）、本番の計算は同じファイルの別シートで行うのが便利です。
例として、セルA1とセルB1にベクトル表現で表した数値が入っており、これらの $F_{256}$ としての和、差、積、商を返す計算式は次のようになります。
和については先ほど登場した BITXOR 関数を使って
=BITXOR(A1,B1)
となります。この関数は引数の数値を$2$進法のビット列とみなして各ビット毎に排他的論理和をとる関数です。
差については標数が$2$なので和と全く同じ
=BITXOR(A1,B1)
となります。
積については、べき表現だと単に足し合わせて$255$の剰余をとるだけなので、ここで先ほど作った対応表を使ってベクトル表現からべき表現に変換し、足し合わせて$255$の剰余をとり、結果をまた対応表でべき表現からベクトル表現に戻せばできあがりです。これらの変換には、みんな大好き VLOOKUP 関数が使えます。実際に書き下すと、
=VLOOKUP(MOD(VLOOKUP(A1,$対応表.$D$7:$E$262,2,FALSE)
+VLOOKUP(B1,$対応表.$D$7:$E$262,2,FALSE),255),$対応表.$A$7:$B$261,2,FALSE)
となります（対応表のセル範囲はアップロードしたファイルに対応しています）。ただし引数がどちらも$0$でなければこれで良いのですが、どちらかが$0$だとエラーが出てしまいますので、複雑にはなりますが IF 関数を使って、
=IF(A1=0,0,IF(B1=0,0,VLOOKUP(MOD(VLOOKUP(A1,$対応表.$D$7:$E$262,2,FALSE)
+VLOOKUP(B1,$対応表.$D$7:$E$262,2,FALSE),255),$対応表.$A$7:$B$261,2,FALSE)))
とすれば完璧です。
商については、積の場合の指数の和を差に変えれば良いので、例えば、
=IF(B1=0,"ゼロ除算エラー",IF(A1=0,0,VLOOKUP(MOD(
VLOOKUP(A1,$対応表.$D$7:$E$262,2,FALSE)-VLOOKUP(B1,$対応表.$D$7:$E$262,2,FALSE)
,255),$対応表.$A$7:$B$261,2,FALSE)))
とすれば良いでしょう。
（続く）（前記事）
有限体といっても、本記事では標数$2$の有限体を対象とします。標数が$2$以外の有限体はビット演算関数が使えないのでかなり複雑になるからです。
例としてリード・ソロモン符号の記事でも使った $F_{256}$ の場合を考えます。
まず、この体の元をどう表現するかを決める必要があります。そのために必要なのは $F_{256}$ の原始多項式です。これは $F_2$ 上の$8$次の既約多項式で、その根が $F_{256}$ の原始元になるもののことです。一般に原始多項式は試行錯誤で探し出すことになりますが、いまの場合は、
\[ X^8+X^4+X^3+X^2+1 \]
が原始多項式になることが知られていますのでこれを使い、その一つの根を$\alpha$と書きます。このとき、
\[ \alpha^8 = \alpha^4+\alpha^3+\alpha^2+1 \]
が成り立つので（標数$2$なのでプラスとマイナスの区別はありません）、$\alpha$のべき乗について、
\begin{eqnarray*}
\alpha^0 &=& && && && && && && && \alpha^0 \\
\alpha^1 &=& && && && && && && \alpha^1 \\
&\cdots& \\
\alpha^7 &=& \alpha^7 \\
\alpha^8 &=& && && && \alpha^4 &+& \alpha^3 &+& \alpha^2 && &+& \alpha^0 \\
\alpha^9 &=& && && \alpha^5 &+& \alpha^4 &+& \alpha^3 && &+& \alpha^1 \\
&\cdots& \\
\alpha^{253} &=& && \alpha^6 && && && &+& \alpha^2 &+& \alpha^1 &+& \alpha^0 \\
\alpha^{254} &=& \alpha^7 && && && &+& \alpha^3 &+& \alpha^2 &+& \alpha^1
\end{eqnarray*}
という1対1の対応ができ、$0$を除く $F_{256}$ の元が網羅されます（$\alpha^{255} = \alpha^0 = 1$ です）。左辺をべき表現、右辺をベクトル表現といいます。
Excel上でべき表現とベクトル表現をどうデータ化するかですが、べき表現は指数をそのまま整数値で、ベクトル表現は$\alpha$を$2$に置き換えて計算した数値でデータ化するのが一番扱い易いです。後者はどういうことかというと、例えば
\[ \alpha^4+\alpha^3+\alpha^2+\alpha^0 \quad \to \quad 2^4+2^3+2^2+2^0 = 29 \]
と数値化して扱うということです。そしてExcel上ではこのベクトル表現の数値化を基本とします。なぜなら BITXOR 関数などのビット演算関数が使えることと、べき表現は$0$を扱うことができないからです。
とはいえ、後で説明するようにべき表現も頻繁に使いますので、Excel上でべき表現とベクトル表現の対応表を作ることから始めます。縦にべき表現として$0$から$254$までを並べ、その右側の列に次のようにしてベクトル表現を入れます。$1$行目にべき表現$0$に対してベクトル表現$1$を入れます。$2$行目以降は一つ上の行の数値を$2$進法のビット列とみなし、それを BITLSHIFT 関数で左に$1$ビットシフトし、BITAND 関数で下$8$ビットだけをとり、さらに一つ上の行の数値の$7$ビット目が$1$ならば（つまり$128$以上ならば）$2^4+2^3+2^2+2^0 = 29$ との排他的論理和を BITXOR 関数で入れます。これをべき表現$254$の行まで繰り返すと、対応表が出来上がります。
この対応表はべき表現順に並んでいますので、これを丸ごとコピーして値ペーストし、左右を入れ替えてベクトル表現順に並べ替えた対応表も作っておきます。
言葉ではわかりにくいので、これらの対応表を LibreOffice で作ったものをここにアップロードします。ダウンロードしてセル内の数式を確認してください。Excelでも開けます。
対応表ができあがったら、これは一つのシートとして置いておき（シート名を「対応表」とします）、本番の計算は同じファイルの別シートで行うのが便利です。
例として、セルA1とセルB1にベクトル表現で表した数値が入っており、これらの $F_{256}$ としての和、差、積、商を返す計算式は次のようになります。
和については先ほど登場した BITXOR 関数を使って
=BITXOR(A1,B1)
となります。この関数は引数の数値を$2$進法のビット列とみなして各ビット毎に排他的論理和をとる関数です。
差については標数が$2$なので和と全く同じ
=BITXOR(A1,B1)
となります。
積については、べき表現だと単に足し合わせて$255$の剰余をとるだけなので、ここで先ほど作った対応表を使ってベクトル表現からべき表現に変換し、足し合わせて$255$の剰余をとり、結果をまた対応表でべき表現からベクトル表現に戻せばできあがりです。これらの変換には、みんな大好き VLOOKUP 関数が使えます。実際に書き下すと、
=VLOOKUP(MOD(VLOOKUP(A1,$対応表.$D$7:$E$262,2,FALSE)
+VLOOKUP(B1,$対応表.$D$7:$E$262,2,FALSE),255),$対応表.$A$7:$B$261,2,FALSE)
となります（対応表のセル範囲はアップロードしたファイルに対応しています）。ただし引数がどちらも$0$でなければこれで良いのですが、どちらかが$0$だとエラーが出てしまいますので、複雑にはなりますが IF 関数を使って、
=IF(A1=0,0,IF(B1=0,0,VLOOKUP(MOD(VLOOKUP(A1,$対応表.$D$7:$E$262,2,FALSE)
+VLOOKUP(B1,$対応表.$D$7:$E$262,2,FALSE),255),$対応表.$A$7:$B$261,2,FALSE)))
とすれば完璧です。
商については、積の場合の指数の和を差に変えれば良いので、例えば、
=IF(B1=0,"ゼロ除算エラー",IF(A1=0,0,VLOOKUP(MOD(
VLOOKUP(A1,$対応表.$D$7:$E$262,2,FALSE)-VLOOKUP(B1,$対応表.$D$7:$E$262,2,FALSE)
,255),$対応表.$A$7:$B$261,2,FALSE)))
とすれば良いでしょう。
（続く）（前記事）
コメント 0