有限体でのガロア拡大(その1)

GF(2)からGF(2^3)のガロア拡大の理屈を工学部出身者向けに直観的に説明してみます。

 

まず、X^8-X=0の根がGF(2^3)の元であることを天下りで決めます。

なぜX^8-X=0の根がGF(2^3)の元であるかは

zuruyasumineko2002.hatenablog.com

で書いてます。


まず、X^8-Xを実数の世界で因数分解すると

X^8-X=X(X^7-1)=X(X-1)(X^6+X^5+X^4+X^3+X^2+X+1)

(X^7-1)/(X-1)は、初項1、公比Xの等比数列の7項目までの総和の公式

なので、1+X+X^2+X^3+X^4+X^5+X^6=(X^7-1)/(X-1)

なので、X-1を移項するという手と

X^7-1に1を代入すると0になるので、X^7-1はX-1で割り切れるということで

割り算してやると1+X+X^2+X^3+X^4+X^5+X^6がでてくるなどの手

を使ってX^8-Xを

X^8-X=X(X^7-1)=X(X-1)(X^6+X^5+X^4+X^3+X^2+X+1)

のように因数分解できます。

複素数の範囲で、X^8-Xを因数分解すると、8次方程式は8個の根があるので

因数分解してみるとX(X^7-1)でX^7-1=0の7個の根は、大学の複素関数論の

結果を使って、β=exp(j*(2π/7))とおくと

β^0(=1)、β、β^2、β^3、β^4、β^5、β^6となる。

よって因数分解すると

X^8-X=X(X-1)(X-β)(X-β^2)(X-β^3)(X-β^4)(X-β^5)(X-β^6)

となります。

さて、GF(2)でX^8-Xを因数分解すると(GF(2)なので、X^8+Xと同じ)

X^8-X=X(X^7-1)

手計算でもコンピュータでもいいけどありとあらゆる多項式でX^7-1をGF(2)で割り算して

割り切れる多項式をさがして因数分解すると、(係数が0か1の多項式なので、有限個しかないので、手計算でも、やる気になればできる。

X^8-X=X(X-1)(X^3+X+1)(X^3+X^2+1)

となる。これ以上因数分解できません。

( GF(2)のことはしらべてね。0と1しか使わない。演算は2で割った余りとする。結局足し算がEXOR

掛け算がANDになる世界。0と1じゃ2通りしかあらわせないから、多項式を考える。項の係数は0か1。)

ということは、X^3+X+1は、最高次の次数が2次以下のすべての多項式でわりきれない。

X^3+X+1は因数分解できないってことです。

こういう多項式を既約多項式という。

X^3+X^2+1も同様である。

さて実数の世界では、X^7-1を7個の最高次の係数が1次の多項式に分解できなかった

複素数の世界にもっていったら、最高次の係数が1次の多項式に分解できた。

実数を複素数に拡大したら因数分解できた。

ならGF(2)を拡大したら、因数分解できるような拡大体を仮定すれば

その拡大体の中では、複素数での場合の因数分解と似た感じで

X(X-1)(X-α)(X-α^2)(X-α^3)(X-α^4)(X-α^5)(X-α^6)

因数分解できる、なんかわからないけどGF(2)の規則にしたがう根αがありそうだ

と考える。

そこで、GF(2)での因数分解にもどる

X^8-X=X(X-1)(X^3+X+1)(X^3+X^2+1)で

αが根なら0と1の根は明らかに違う。αが根ならX^3+X+1かX^3+X^2+1の根という

ことになる。つまり、X^3+X+1を因数分解したものか

X^3+X^2+1を因数分解したものが(X-α)(X^2+・・・)となる。

X^3+X+1のほうにが(X-α)があるなら、α^3+α+1=0が成り立つ

もう一方に(X-α)があるなら、α^3+α^2+1=0が成り立つはずです。

そこで、例えばX^3+X+1のほうに(X-α)があるとしたなら、

α^3+α+1=0がなりたちます。

なぜなら、f(X)=X^3+X+1=(X-α)(X^2+・・・)

でf(α)=0だからα^3+α+1=0ね。

ここで任意の多項式を表現を変えて表すと

任意の多項式=(X^3+X+1)*G(X)+余りの多項式とあらわせます。

任意の多項式のXにαを代入すると

α^3+α+1=0なのでG(α)との積の項は消えて、余りの多項式になります

余りの多項式はX^3+X+1が既約ですから、最高次の次数が2次以下のすべての

多項式のXにαを代入したものになります。

なので、余りとして考えられるものをすべて列挙すると0、1、α、α^2、α+1、

α^2+1、α^2+α、α^2+α+1の8個になります。

これは、X^3+X+1で割った余りで分類した剰余系といえそうなきがしませんか?

さきほどの複素数の世界での因数分解でβとおいたものをαにおきかえて

X^8-Xが、X(X-1)(X-α)(X-α^2)(X-α^3)(X-α^4)(X-α^5)(X-α^6)

因数分解できたらと仮定します。上因数分解式の定数項がα^3+α+1で

わった剰余系のさきほどの8個、0、1、α、α^2、α+1、α^2+1

α^2+α、α^2+α+1と一致していたらどうなるでしょう。

0、1、α、α^2は一致しています。

α^3+α+1=0なので、α^3=α+1がなりたつので、

α^3からα^6を次数をおとしてやると

剰余系のあまりと1対1対応で一致します。(1対1対応を全単射といいます。)

というわけでこれら8個を、X^3+X+1で割った余りの剰余系をGF(2)を拡大したものの

元としてみます。このあとこの8つの元の世界が体をなしているか調べます。

またαはX^7-1=0の根なのでα^7=1がなりたちます。(β^7=1でもある。複素数の世界での話ね!)

それでは、{0,1、α、α^2、α^3、α^4、

α^5、α^6}が体をなしているかしらべましょう。すると、GF(2)の演算で加減乗除についてとじていて、単位元、逆元が存在します。演算の順序をかえても結果はかわりません。結合則も成立します。

したがって体をなしています、元の個数は2^3=8個です

なのでこれをGF(2)を拡大して作ったGF(2^3)ガロア拡大体といいます。

余談ですが複素数の世界でのX^8-X=0の根は乗法について閉じていて、単位元、逆元が存在し、当たり前ですが結合則も成立するので乗法群です。加法については閉じてないので体ではありません。

これで原始多項式の定義が根にαをもつ多項式で、既約なものという意味が分かったし

さらに、既約多項式なんだけどX^7-1を因数分解した多項式でなかったら、原始多項式ではないということ

もわかった。すべて解決である。

今回の説明は直観的だけど、厳密にやるなら、数学の本みて勉強すればいいし、ガロア体みたいな元が有限個の有限体でイメージを

つくっておくと

ほかの、体の拡大のイメージがわくんではないかと思います。

X^3+X+1を原始多項式とした例(X^3+X+1=0がαという根をもつとした例)だったけれど、X^3+X^2+1を原始多項式とした場合(X^3+X^2+1=0がαという根を持つ場合)でも、8つの根が全単射で対応し、ガロア拡大

ができるということもわかる。

さらに確かめる。


(X^3+X+1)がX-αで割り切れると

α^3+α+1=0なら

α^3=α+1

α^4=α^2+α

α^5=α^2+α+1

α^6=α^2+1

α^7=1

X^3+X+1はα^2、α^3、α^4、α^5、α^6のうち

2個を根としてもつはずだから

全部の組み合わせをためすとα^2とα^4を選んだとき


(X-α)(X-α^2)(X-α^4)を試すと

(X-α)(X-α^2)(X-α^4)=X^3+X+1

ここで(X-α)(X-α^2)(X-α^4)を展開するとき

α+α=0、α^2+α^2=0、α^3=α+1、α^7=1などを使うことを忘れないでね。

α、α^2・・・α^6は、それぞれ、それ自体を元としてGF(2)の規則が成り立つからね。

誤り訂正カテゴリのほかの記事に目を通せば、展開の仕方はわかるはずだから、計算過

程はのせないよ。

X^3+X^2+1は残りの根をもつはずだから

(X-α^3)(X-α^6)(X-α^5)

を展開すると確かにX^3+X^2+1になる。


よってX^8-X=X(X-1)(X-α)(X-α^2)(X-α^4)(X-α^3)(X-α^6)(X-α^5)

因数分解できた

確かに矛盾がないことがわかる。

ガロア体は、素数で割ったあまりの剰余系

ガロア拡大体は、原始多項式(原始元αを根とする多項式)で割ったあまりの剰余系。

例えば、原始多項式をX^3+X+1で割ったあまりの2次の多項式にαを代入したもの。

Xの高次多項式は原始多項式でわったあまりで分類でき、それにαを代入すると

ガロア拡大体の元になる。

新たな疑問は、X^n=1の根が、なぜガロア拡大体の元になるのかがわからない。

わかった。・・・X^21=X^14=X^7=1でX^n(nは任意の整数)がすべて1、X,X^2,X^3、X^4、X^5、X^6の7つで表される
単位円をぐるぐるまわる数学用語で巡回群になるからだ。
αを代入すると、乗法で閉じていることがわかるね。体になる条件として必要なのね。
この巡回群は乗法について閉じているわけだ。
しかも、原始多項式でわったあまりなので、剰余系は加法についても閉じている。

総じて、加法と乗法について閉じている
これで単位元と逆元が存在すれば体になって、ガロア拡大体の完成

実際やってみると加法の単位元は0、乗法の単位元は1
逆元はやってみるとありそうだね。

やったガロア拡大体の完成

有限体でもあるGF(2)では2元だったが、GF(2^3)では8元になった。

うん有限体を完全に理解した。

ここまで理解できれば、数学記号の意味を調べれば、数学屋の話が理解できるであろう。

抽象論の一般のガロア拡大にも手が届きそうである。

さて、この記事とサイト「未確認飛行++C++」の体の拡大の記事を読めば、一般の体の拡大も完全に理解できると思うよ。