Pebble Coding

プログラマーの作業メモ

素体を拡大する

素体  F_pを拡大してみます。
 F_3を拡大して、拡大体  F_{{3}^{2}}を作ることにします。
体の拡大には既約多項式を使います。
ここでは、規約多項式 x^{2} + 2 x + 2 = 0を使います。
 F_3を作る場合は素数3で割った余りを使うというルールでした。
 F_3の元は{0, 1, 2}の3つですが、加法の単位元が0で乗法の単位元が1です。

 F_{{3}^{2}}を作る場合のルールは、既約多項式のxを使って、
xを素体に追加して、xを整数1とは独立したものとして計算し、
 x^{2}が出現した場合は  x^{2} = - 2x - 2 = x + 1 に置き換えるというものです。
また1の係数やxの係数は3で割った余りを使います。

元は{0, 1, 2, x, 2x, 1 + x, 1 + 2x, 2 + x, 2 + 2x}の9個になります。
一般に拡大体  F_{{p}^{n}}の元の数は {{p}^{n}}個です。

これらの元同士の加算には x^{2}の項は出てこないため、3で割った余りを使うだけで、簡単なので省略します。
これらの元同士の乗算は面倒なので表にしてみました。

0 1 2 x 2x 1+x 1+2x 2+x 2+2x
0 0 0 0 0 0 0 0 0 0
1 0 1 2 x 2x 1+x 1+2x 2+x 2+2x
2 0 2 1 2x x 2+2x 2+x 1+2x 1+x
x 0 x 2x x+1 2+2x 1+2x 2 1 2+x
2x 0 2x x 2+2x 1+x 2+x 1 2 1+2x
1+x 0 1+x 2+2x 1+2x 2+x 2 2x x 1
1+2x 0 1+2x 2+x 2 1 2x 2+2x 1+x x
2+x 0 2+x 1+2x 1 2 x 1+x 2+2x 2x
2+2x 0 2+2x 1+x 2+x 1+2x 1 x 2x 2

例としてひとつ計算してみます。
 (2x+2) * (2x +2 )= 4 x^{2} + 8x + 4 = x^{2} + 2x + 1 = x + 1 + 2x + 1 = 3x + 2 = 2

ここでは、綺麗に1列に同じ元が出てこないようになっていますね。
既約多項式を使わないと、このようにはならず、列に同じ元が2つ以上出てくるようになってしまいます。

規約多項式 x^{2} + 2 x + 2 = 0以外にも存在します。
例えば、 x^{2} + 1 = 0 x^{2} + x + 1 = 0も規約多項式です。
これを使って掛け算の表を作った場合、異なる表になりますが、元の役割を入れ替えることで、
一つ目の規約多項式を使った場合と同じ表になることが知られているそうです。(同型と言います。)
規約多項式は計算量が少なくなるように係数が小さい方がよいので、
通常 x^{2} + 2 x + 2 = 0などは使いません。

素数が3の時の拡大体  F_{{3}^{2}} を手に入れることができましたが、
素数が3より大きい時に規約多項式をどのように選べば良いでしょうか。
ひとつの例としては、n = p + 1 として、
 x^{n} + 2 x^{n-1} + 2 x^{n-2} + ... + 2 x + 2 = 0を選べば良いです。
これは、アイゼンシュタインの既約判定法を用いて作ったものですが、
係数が小さい方が計算量が少なくてすみますから、通常これは選びません。

最も効率が良い規約多項式を得るには、別の構成方法を用いるようです。

参考:
http://lupus.is.kochi-u.ac.jp/shiota/misc/field/FiniteField.html

体の拡大は、もとの体に規約多項式の解を添加しているとも言えます。

なお、規約多項式 x^{2} + 1 = 0 x^{2} + x + 1 = 0を使った場合は、
この2つの解をそれぞれ、 \alpha, \betaとすると、 (x - \alpha) (x - \beta) = 0なので、
 \alpha \beta = 1が満たされ、 \beta = {\alpha}^{-1}と書けることを覚えておくと、どこかで役にたつかも知れません。