有限体でのガロア拡大（その３）

X^8+X^4+X^3+X^2+1は、原始多項式である。
地デジやブルーレイや光通信やＱＲコードのリードソロモン符号ででてくる。
なぜ、これが多用されているかというと、コンピュータはデータをバイト（８ビット）の整数倍で処理するので都合がいいからである。
X^8+X^4+X^3+X^2+1と8ビットの関係の説明がないので、なんのこっちゃと思うと思うので、説明します。
X^8+X^4+X^3+X^2+1と8ビットとの関係がわかるまでが長いけどお付き合いください。
それでは、順番に説明します。
整数を、2で割った余りで分類すると0か1になる。
2で割った余りの世界では、構成要素が0と1しかない。
この０か１しかない世界でも、加算、掛算は定義できる。0+0=0,0+1=1,1+0=1,1+1=0 0*0=0,0*1=0,1*0=0,1*1=1
また加算の単位元と逆元、掛算の単位元と逆元も定義できるので、減算、除算も定義できる。ここの説明はここ
四則演算が定義できる世界のことを体という。実数の世界も四則演算が定義でき、演算してもその答えは実数になる。だから体である。複素数の世界でも四則演算が定義でき、演算の答えも複素数になる、だから体である。
２で割った余りで分類する世界を例に挙げたが、整数を素数で割った余りで分類する世界は体になっており、
これをガロア体という。素数以外で割った余りで分類する世界は体にならない。
ガロア体は工学屋の言葉で、数学やる人は、構成要素の数が有限個なので有限体と呼んでいる。
素数2で割った余りで分類される世界をGF(2)とかく。
素数3で割った余りで分類される世界をGF(3)とかく。
素数5で割った余りで分類される世界をGF(5)とかく。
かっこの中の数は素数の値ではなく、構成要素の数である
GF(2)は構成要素が0と1なので2
GF(3)は構成要素が0,1,2なので3
コンピュータは、２進数で動いているので、0と1だけを使うGF(2)が都合がよさそうである。
なぜなら、足し算がXOR、掛け算がANDで表される。
そこでこれからはGF(2)について考えていく。
GF(2)の構成要素は0と1だけ。これだけじゃ、どうにもならない。
そこでビット列が扱えるように多項式を考える。
0と1しかつかえないから、各項の係数は0か1
ビット列10101を考えると
1*X^4+0*X^3+1*X^2+0*X+1
=X^4+X^2+1
このようにＸのべき乗を使ってビット列をあらわせる。
（でね。上の式のXに2をいれると、２進数の表現になるでしょ。
10101は、21になってうまくいく。
Xに10をいれると10進数の表現になる。
位取り記数法のしくみになってるとこがおもしろいでしょ。
この辺は、kei@soudan.funini.comさんのサイトに書いてある
ことをヒントにしたので、keiさんのオリジナルである。
Xってのは、なんだかわからないけど、GF(2)だと０と１しかないのでXにせざるを
えないでしょ。この文章を全部読んだあと、このかっこ内をみればXには原始根αをいれればよいことがわかるよ。
１の位、αの位、α^2の位って、位取り記数法で書いてもいいことがわかるよ。
それが８ビットの２進数になるわけである。）
GF(2)の世界で多項式が、使えるのかと疑問を持った人のために
説明すると、
実数の世界では四則演算が定義できるので、実数の世界は体です。
この実数体では、多項式が使え、微分や積分が定義できます。
体というのは共通の性質があり、実数体で多項式が使えれば、ガロア体でも多項式がつかえます。
ガロア体の多項式では、形式的に実数の微分、積分公式が使えます。ただ意味はなんだかわかりません。
実数体では方程式や因数分解があります。なので、ガロア体にも方程式や因数分解があります。
この辺を追求しているのが、代数学という数学の分野です。
ということで、ガロア体GF(2)での多項式でX^8+X^4+X^3+X^2+1を考えます。
これは、最初に述べた原始多項式です。
この多項式をGF(2)の世界で因数分解しようとしてもできません。
因数分解できないといえば、実数の世界でもX^2+1という因数分解できない多項式がありました。
そこでどうしたかというと、虚数単位iを導入して複素数の世界に拡張して
因数分解できるようにしました。
このときX^2+1=0の根をiとおきました。
i^2+1=0がなりたちます。i^2=－１
するとX^2+1=(X-i)(X+i)と因数分解ができるようになります。
GF(2)での多項式X^8+X^4+X^3+X^2+1も虚数単位αを導入したらどうだろう
ということで、αは、X^8+X^4+X^3+X^2+1の根と仮定するとどういうことがおこるかというと
α^8+α^4+α^3+α^2+1=0となります。
またX^8+X^4+X^3+X^2+1は、(X-α)(X^7+…)と因数分解できるはずです。
なぜなら、αを代入すると０になるからです。
さて、この先読んでいくとわかるんですが
X^8+X^4+X^3+X^2+1=(X-α)(X-α^2)(X-α^4)(X-α^8)(X-α^16)(X-α-32)(X-α^64)(X-α^128)
と因数分解できます。なぜかは、続きを読んでください。
さて、再び実数と複素数の話にもどりますが
実数から複素数に拡大することで、どんな多項式も1次式だけに因数分解でき、n次方程式の根は必ずn個になりました。
GF(2)では、n次多項式の根は、n個にならないことがあります。1次式だけの積の形にならないので、実数から複素数
に拡大解釈したようにGF(2)もなんらかの拡大解釈した体を考えないとn次多項式の根はn個になりません。
ところで、複素数は実数を拡大した体なので、実数の世界での規則と複素数の世界での規則は同じです。GF(2)は2で割った余りで構成される体です。
なのでGF(2)を拡大したものも、なんかで割った余りで構成されるのではないかと考えます。
そこで発想がぶっとんでるのですが、なんかを多項式にしてみると
ガロア体は素数でわった余りで分類される体です。
ガロア拡大体は、多項式でわった余りで分類される体となります。
ここで、多項式で素数にあたるものはなんだということを考えます。
素数は約数がないという性質があります。約数がないにあたるのは、多項式の世界では因数分解できないということに気付きます。
素数でない6は、6=3*2とあらわせます。因数分解できる多項式X^2-1はX^2-1=(X+1)(X-1)と表せます。
こういうふうに積であらわせないものが、素数や因数分解できない多項式となります。
X+1を因数分解できる多項式X^2-1でわったとき商が1/(Xー1)となってわりきれてしまいます。因数分解できない多項式でわると余りが出て、その多項式の最大次の次数より小さい多項式全部が余りになりえるわけです。
GF(2)のすべての多項式は、さきほどのX^8+X^4+X^3+X^2+1のようなこれ以上因数分解できない多項式でわった余りで分類できるということです。
それ以上因数分解できない多項式のことを既約多項式と呼ぶと、多項式の世界の素数が既約多項式です。
よって、X^8+X^4+X^3+X^2+1で割った余りはというと最高次の項が７次以下のすべての多項式となり
余りなしの0を含めて2^8個＝256個の余りで分類されることがわかります。
すべての多項式は、X^8+X^4+X^3+X^2+1で割った余りで分類され、最高次の項が7次以下のすべての多項式のうちのどれかで
表せます。
これは
任意の多項式＝（X^8+X^4+X^3+X^2+1)*G(X)+最高次の項が7次以下のすべての多項式のうちのひとつ
と表現できます。
さて、虚数単位αはGF(2)に加える要素の一つでした。
実数にiを付け加えて複素数にしたように、αを加えることで、n次多項式にn個根をもたせることができるかもしれない。
で、6行上の式のｘにαを代入すると、G(X)との積の項が消えて
0，1、α、α+1、α^2、α^2+1、α^2+α、α^2+α+1・・・・・・・・・
２５６個の余りがでてきます。
αの任意の多項式は256の余りのうちのどれかに当てはまるということがいえます。
で３行上をみてみると、GF(2)の構成要素、（体の構成要素を元という）GF(2)の元{０,1}
は含まれていて、αを導入したら、254個の元が追加されたと考えましょう。
まだ体かどうかわからないけれどこれをガロア拡大体GF(256）とかGF(2^8)としておいてみましょう。
ガロア拡大体GF(2^8)の元は{0，1、α、α+1、α^2、α^2+1、α^2+α、α^2+α+1・・・・・・}
とおいてみるということです。元は256個あります。

GF(n)の世界にはフェルマーの小定理というものがあります。
フェルマーの小定理については、「ガロア拡大（その２）」の記事で説明しています。
結果だけいうと
元がn個ある体におけるX^n-Xの根は、その体のすべての元になるということです。
GF(2^8)でフェルマーの小定理を適用すると
X^256-Xは、X(X-1)(X-α)(X-(α+1))(X-α^2)・・・・・・・・・・・
と因数分解できるってことになります。ただ、まだGF(2^8)が体かどうかはわかりませんが体と仮定した場合です。

X^256-Xってのは、X(X^255-1)とも因数分解できます。
複素数の世界ではX^255-1の根は単位円上にあります。
ここの説明は、「ガロア拡大（その１）」の記事を見てください。
実数を拡大した複素数の世界で単位円上にあるなら、GF(2)を拡大したGF(2^8)でも単位円上にある
と考えると
複素数でのX^255-1の因数分解
X^255-１＝(X-1)(X-β)(X-β^2)(X-β^3)・・・・(X-β^254)
で
GF(2^8)では、この式のβをαとおいたものと考えると

X^255-1=(X-1)(X-α)(X-α^2)・・・・(X-α^254)
となります。
α^8+α^4+α^3+α^2+1=0でしたので
α^8＝α^4+α^3+α^2+1
がなりたつので、4行上の式のαのべきの数が８以上の定数項に代入してαの7乗以下におとしてやると
すべての余りの多項式と一致します。
例えばα^9＝α*α^8＝α*(α^4+α^３+α^2+1)＝α^5+α^4+α^3+α
X^8+X^4+X^3+X^2+1以外にも既約多項式はありますが、原始多項式は、0とα^0～α^254の256個が、余りの多項式と
と一致するように選んだものなのです。
ということで、原始多項式にαを代入したものは０になるので、α^8+α^4+α^3+α^2+1=0
またX^255=1なのでα^255=1
という規則が、GF(2^8)の世界では、まかりとおっているのです。
おっとGF(2^8)の世界は、体として完全かどうか、つまり、四則演算が成り立つかどうか
検討してみましょう。まず足し算ですが繰り上がりの出ない足し算ができることがわかり、足した結果もGF(2^8)の元
になることがわかります。
掛け算はというとαのべき乗の形でひとつの元を表すことができ、掛け算は指数部をたせばよく、α^255=1ですから
指数部が254よりおおきくなっても254以下にすることができるので掛け算の結果もGF(2^8)の元になることがわかります。
加算の逆元、単位元があれば、減算も定義でき、乗算の逆元、単位元があれば、除算も定義できますが。それぞれの単位元、逆元は
やってみるとあります。よって四則演算ができ、結果も元の中の一つに一致するようになります。これを閉じているといいます。
つまり体として完全です。体としてみたさなければならない条件は、本当はほかにもあるのですが、それらは成り立ってあたりまえなのでふれません。
これで、この記事の最初に説明がなかった
X^8+X^4+X^3+X^2+1と8ビットの関係ですが、
この原始多項式の根をαとおくことによって、GF(2)をGF(2^8)に拡大できその元は8ビットの2進数すべてと対応がつく
ことがわかるからです。例えばα^7+α^3+1 は　10001001と2進数であらわせます。
よって代表的なリードソロモン符号では、8ビットの2進数をGF(2^８)の元1個であらわせるX^8+X^4+X^3+X^2+1
を原始多項式に選ぶことが多いのである。

余談ですが、
α^8＝α^4+α^3+α^2+1を使って次数をおとすということは、α^8+α^4+α^3+α^2+1で割った余りをとるということと同じということです。
例えばα^9＝α^8*α=(α^4+α^3+α^2+1)*α=α^5+α^4+α^3+α
α^9÷（α^8+α^4+α^3+α^2+1)=α あまりα^5+α^4+α^3+α
となり一致します

①、GF(2^8)の元が任意の多項式を原始多項式X^8+X^4+X^3+X^2+1で割った余りのXにαを代入したものであること、256種類
②、フェルマーの小定理が、GF(2^8)拡大体でもなりたつということ
③、１の255乗根が、複素数体では、単位円上にあり、GF(2^8)の世界でも１の255乗根のひとつをαとすればα^0、α^1、α^2、・・・、α^254が根になる。
④、③の255個の根が、①の0を除く255個の元とα^8=α^4+α^3+α^2+1の条件で1対1対応がとれる。


ということで、GF(2)に最高次の次数がnの原始多項式の根αというものを加えると、

GF(2^n)ガロア拡大体が矛盾なく構成できるのである。

ところで、原始多項式X^8+X^4+X^3+X^2+1を因数分解すると

(X-α)(X-α^2)(X-α^4)(X-α^8)(X-α^16)(X-α^32)(X-α^64)(X-α^128）となります。

なんでかっていうとf(X)＝X+1とおくとf(X)^2＝（X+1)^2＝X^2+２X+1＝X^2+1＝f(X^2)
f(X)=X^2+X+1とおくとf(X)^2＝（X^2+X+1)^2＝（X^2+X)^2+2(X^2+X)+1＝X^4+2X^3+X^2+1＝X^4+X^2+1
＝f(X^2)
となんか、GF(2)ではf(X)^2=f(X^2)になりそうじゃんとおもうでしょ。実際証明するとそうで
それは、別のブログ記事にかいてあります。
するとGF(2)でなりたつことはGF(2^8)でもなりたちます。
f(X)^2=f(X^2)=0とおくと
f(X)=0のときf(X^2)も０になります
よってf(X)=X^8+X^4+X^3+X^2+1の根がαなので
f(α)＝f(α^2)=0
ついでにf(α^2)=f(α^4)=0
・・・・
となってαが根ならα^2もα^4もα^8も・・・・・
も根ということになり
X^8+X^4+X^3+X^2+1は８次なので
８つ別の根があればいいわけで、

(X-α)(X-α^2)(X-α^4)(X-α^8)(X-α^16)(X-α^32)(X-α^64)(X-α^128)

の様に因数分解できるわけです。
GF(2^8)では、8次の多項式には８個の根があります。

記事を書き終わって、α^0からα^254までをα^8+α^4+α^3+α^2+1で割ったときの余りに同じものがでてこない。
原始多項式というものがあるということに自然界の美しさを感じずにはいられなかった。

そして、ある多項式が原始多項式だといえるとき、既約であることのほかに、α^0からα^(2^n-2)をその多項式で割ったあまりが全部部違うということになるのである。

原始多項式を求めるプログラムを作る場合、まず、次数がそれより小さい多項式すべてで
わって、余りが出ることを確認する。つまり、既約であることを確認し、さらにそれだけではだめで、α^0からα^(2^n-2)
をn-1次以下の多項式になおして、全部違うことを確認する。α^(2^n-1)が、α^0、α^1、α^2・・・と順に計算して
α^0をのぞいてはじめて１になることを確認して、原始多項式が決定されるように作る必要がある。