Pebble Coding

ソフトウェアエンジニアによるIT技術、数学の備忘録

素体を拡大する

素体  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 として、
 x^{n} + p x^{n-1} + p x^{n-2} + ... + p x + p = 0を選べば良いです。
これは、アイゼンシュタインの既約判定法を用いて作ったものですが、
係数が小さい方が計算量が少なくてすみますから、通常これは選びません。

アイゼンシュタインの既約判定法 - Wikipedia

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

参考:
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}と書けることを覚えておくと、どこかで役にたつかも知れません。

乗法群

拡大した体 F_{3^{2}}の乗法群を考えます。
表を見れば分かりますが、0を除いた{1, 2, x, 2x, 1+x, 1+2x, 2+x, 2+2x}の8個がこの乗法群の元になることが確かめられます。
単位元は1です。
この乗法群の位数は8ですから、
任意の元を8乗すると単位元になるはずです。  a \in F_{{3}^{3}}^{\times}
として、
 a^{8} = a^{{3}^{3} -1 } = 1

この群の元の位数は群位数の約数になるので1, 2, 4, 8のどれかです。
位数8の元の一つを試しに計算してみます。
 (1+2x)^{2} = 2+2x
 (1+2x)^{3} = (1+2x)(2+2x) = x
 (1+2x)^{4} = (1+2x)x = 2
 (1+2x)^{5} = 2(1+2x)=2+x
 (1+2x)^{6} = (1+2x)(2+x) = 1+x
 (1+2x)^{7} = (1+x)(1+2x) = 2x
 (1+2x)^{8} = 2x(1+2x) = 1

べき部分を一般化します。
 a \in F_{3^{n}}^{\times} のとき、
 a^{3^{n}-1} = 1
さらに一般化すると、
 a \in F_{p^{n}}^{\times}, pは素数, nは整数のとき、
 a^{p^{n}-1} = 1
逆に、
 a^{p^{n}-1} = 1が成り立つとき、
 a \in F_{p^{n}}^{\times}
が成り立つことが知られています。