前編内容

素数べき要素数の有限体のための基礎知識
素数べき要素数の有限体とその作り方
素数べき要素数の有限体の例
素数べき要素数の有限体のガロア群

中編内容

JavaScriptで実装する素数べき要素数有限体
2べき要素数の有限体に特化した実装

後編内容

有限体の応用: リードソロモン符号とBCH符号

素数べき要素数の有限体のための基礎知識

素数べき要素数の有限体に取り組むにな、以下の前提知識が必要です。

素数要素数の有限体
多項式

体

四則演算と分配則を備えた数の集合(Set)のことを、「体(Field)」と呼びます。

体の例: 有理数(Rational number, Q)、実数(Real number, R)、複素数(Complex number, C)

四則演算は、加算(Add, +)、減算(Subtract, -)、乗算(Multiply, *)、除算(Divide, /)のことです。

ただし、減算a-bは、bと足すと0になる負数-bを足すこと(a-b = a+(-b))であり、除算a/bは、bと掛けると1になる逆数1/bを掛けること(a/b = a*(1/b))のことです。このため、体は、

加算(a+b)と乗算(a*b)を持つ数の集合
任意の数aについて、a+0=a, a*1=aとなる数0と1が存在する
すべての数aに、a+(-a)=0となる負数-aに相当する数が存在する
0以外のすべての数aに、a*(1/a)=1となる逆数1/aが存在する
数a,b,cについて、a*(b+c) = a*b + a*cが成立する(分配則)

を満たす代数構造(algebraic system)となります。

この条件のうち、逆数の存在を要求しない代数構造は環(Ring)と呼ばれます。
整数(Integer, Z)は、環ですが、体ではありません。

体にならない環との区別として、0以外のすべての数に逆数が存在するかどうかが、体であるかどうかのポイントとなります。

素数要素数の有限体

体の要素である数が有限個であるものを有限体と呼びます。

要素数が素数p個の有限体は、非負整数へのモジュロ演算(剰余演算、a mod p もしくは a % p)での関係として、簡単に構成できます。

p個の数: 0, 1, ..., p-1
加算: a + b mod p
乗算: a * b mod p
数aの負数: p - a mod p

ただし、aに掛けると1となる、aの逆数(inverse)については、単純計算ではなく、全ての数の中から対応する数を見つける必要があります。

素数個要素数の有限体の逆数と拡張ユークリッド互除法

素数要素数の有限体での逆数を得るために、よく行われる手段が、pとaを使った(整数の)拡張ユークリッド互除法(Extended GCD, EGCD)です。

EGCDとは、通常のユークリッドの互除法でaとbの最大公約数(GCD)gを得るだけでなく、a*s + b*t = gとなるsとtも同時に返す計算を行う関数です。

pは素数なので、0以外の有限体の数aとの最大公約数gは必ず1となります。
aとpでEGCDを行った結果のg=1とsとtについての先の等式でmod pをとると、a*s + p*t = 1 mod p、つまり、a * (s mod p) = 1となります。

よって、このEGCDで得られる**s mod p**が、aにかけることで1になる、有限体での逆数(inverse)となります。

EGCD、および、aの逆元を求める関数は、JavaScriptでは以下のコードとなります。

invp.js

const egcd = (a, b) => {
  if (a === 0) return [b, 0, 1];    // b = a*0 + b*1
  const r = b % a, d = (b - r) / a; // r = b - a*d;
  const [gcd, s, t] = egcd(r, a);   // gcd = r*s + a*t
  return [gcd, t - d * s, s];       // gcd = (b-a*d)*s + a*t = a*(t-d*s) + b*s
}
// example
{
  const a = 5, b = 13;
  const [gcd, s, t] = egcd(a, b); // gcd=1, s=-5, t=2
  console.assert(a * s + b * t == gcd);
}

const modp = p => a => (p + a % p) % p;
const invp = (a, p) => modp(p)(egcd(a, p)[1]);
// example
{
  console.assert(invp(5, 13) === 8);
  console.assert(5 * invp(5, 13) % 13 === 1);
}

素数要素数の有限体の例

ここでは、有限体を表現するのに、全2数の間での加算表と乗算表を用います。
これらの表の中で、全ての数、加算関係と負数(相当する数)、乗算関係と逆数の存在が確認できるでしょう。

以下は、一番単純な要素数が2個の有限体の加算表と乗算表です。

+	0	1
0	0	1
1	1	0

*	0	1
0	0	0
1	0	1

次に、要素数が3個の有限体の加算表と乗算表です。

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

*	1	2
0	0	0
1	1	2
2	2	1

そして、要素数が5個の有限体の加算表と乗算表です。

+	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

*	1	2	3	4
0	0	0	0	0
1	1	2	3	4
2	2	4	1	3
3	3	1	4	2
4	4	3	2	1

たとえば、3の負数-3に相当する数は、加算表で3の行で0のセルのあるのが2の列であることから、2となります。
また、3の逆数1/3に相当する数は、乗算表で3の行で1のセルのあるのが2の列であることから、2となります。

これらの乗算表の各行の値が全て違う数であることは、体としての性質の一つです。
0以外での乗算a * bでは、aに対して、bごとに0以外のそれぞれ違う値になります。

多項式

もう一つの予備知識として、(1変数の)多項式(polynomial)が必要です。

多項式は、パラメータのべき乗の項の線形和で構成する要素です。以下はすべて多項式です。

$x^3$
$x^3+2x+2$
$3$

普通の数も、変数xの0乗の項$x^0$のみの定数多項式となります。$3 = 3x^0$

0乗も含め、変数xへの指数kごとに、係数$C_k$のついたk次の項$C_kx^k$があって、それらを足し合わせたものが多項式です。項1つの多項式は、単項式(monomial)と呼びます。

以降の説明では、多項式での定数多項式と、係数の数とを識別するために、以下のように多項式は()でくくることにします。

$(x^3)$
$(x^3+2x+2)$
$(3)$

数と同様、多項式も演算が定義された集合の要素です。
数がそうであるように、多項式も、変数に割り当てたり、足したり引いたりする**対象(オブジェクト)**として扱うものです。

多項式変数

変数xの多項式を割り当てる変数は、a(x),b(x),f(x),g(x)等で表現します。

このxは、係数と同じ種の数です。a(x)に数vを入れることは、a(v)もしくは、a(x=v)として記述します。
このa(v)は、(多項式ではなく)係数と同じ種の数となります。

多項式の次数

多項式中の変数xの指数の最大値は、次数(orderもしくはdegree)と呼びます。
次数がnである多項式のことを、n次多項式と呼びます。$x^3+x+1$は3次多項式です。

変数に付く数を係数(coefficient)と呼びます。係数はn次多項式なら0次の定数項も含めてn+1個あります。

多項式の演算

多項式の加減算は、項ごとの係数の加減算を行います。

例: $(x^3+x+1) + (x^2+x+1) = (x^3+x^2+2x+2)$

多項式の定数倍n*a(x)も、係数ごとの定数倍となります。

例: $2 * (x^3+x+1) = (2x^3+2x+2)$

多項式の変数倍は、すべての項の指数に1足すことに相当します。

例: $x * (x^3+x+1) = (x^4+x^2+x)$

よって多項式の変数のべき乗倍では、すべての項の指数にその指数を足すことになります。

例: $x^2 * (x^3+x+1) = (x^5+x^3+x^2)$

そして、乗算a(x)*b(x)は、多項式a(x)をb(x)の各項ごとに係数倍と変数倍をし、すべて足し合わすことで行います。

例: $(x^3+x+1) * (x^2+2) = (x^5+x^3+x^2) + (2x^3+2x+2) = (x^5+3x^3+x^2+2x+2)$

この各項ごとに掛け、すべて足し込む計算のことは、一般的に「畳み込み(convolution)」と呼ばれます。

多項式のモジュロ算

一般的に、多項式f(x)とg(x)の間では、f(x) = d(x)*g(x) + r(x)という関係が成立します。
ただし、r(x)の次数は、g(x)の次数未満です。

この場合、r(x)は、f(x)をg(x)で割った余りであり、多項式の剰余と呼びます。

注意点は、剰余となる多項式の条件は、その次数がg(x)の次数より小さいことであり、多項式の係数が正であることではありません。

例: $(x^3+1) \mod (x^3+x+1) = (-x)$

多項式の加減乗算の結果として、その結果の多項式の剰余多項式を得ることを多項式のモジュロ算(剰余演算)といいます。
数でのモジュロ算と同様に、a(x) mod g(x)のように記述します。

数でのモジュロ算と同様に

a(x) + b(x) mod g(x) = (a(x) mod g(x)) + (b(x) mod g(x))
a(x) * b(x) mod g(x) = (a(x) mod g(x)) * (b(x) mod g(x)) mod g(x)

という、演算の途中でモジュロ算を行っても同じ結果となる性質があります。

この性質から、多項式のモジュロ算をするために、分解して足したり掛けたりすることを繰り返すことで行うことも可能です。

例: $(x^5+1) \mod (x^2+x+1)$

まず、$(x^2) \mod (x^2+x+1) = (-x-1)$
$(x^5) \mod (x^2+x+1) = (x^2) * (x^2) * (x) = (-x-1) * (-x-1) * (x) = (x^2+2x+1) * (x) = ((-x-1)+(2x+1)) * (x) = (x^2) = (-x-1)$
よって、$(x^5+1) \mod (x^2+x+1) = (-x)$

有限体係数の多項式

多項式の係数には、有限体も用いる事ができます。

この場合、係数への加減算と乗算で、有限体での加減算と乗算を適用します。
また、係数が有限体であっても、多項式のモジュロ算も成立します。

要素数2の有限体係数の多項式の演算例

$(x^2+x+1) + (x+1) = (x^2+2x+2) = (x^2)$
$(x^2+x+1) * (x+1) = (x^3+2x^2+2x+1) = (x^3+1)$
$(x^2+x+1) \mod (x+1) = (x)(x+1)+(1) \mod (x+1) = (1)$

多項式を数として扱うこと

多項式も加減乗算ができることで、多項式自体を数そのものとしても扱います。

はじめは多項式f(x)の変数xが何なのか気になるかもしれませんが、むしろ多項式内の変数そのものは無視することです。
見るべきは、変数の指数値と係数値です。

プログラミングではn次多項式は、n+1要素の係数値の配列データで表現します。こうなると変数名は消えます。

$x^3+x+2$ => [2,1,0,1]

数式や変数の意味に惑わされるなら、係数値の配列のことだと思うとよいです。f(x)は、f[]のことです。

そして、多項式の演算は、数値配列同士のための演算系だと考えることが可能です。

多項式の加算は、配列の要素ごとの加算
多項式の乗算は、配列同士のconvolution処理
多項式のモジュロ算は、要素数を一定以下に制限する計算

素数べき要素数の有限体とその作り方

素数べき(単一素数のべき乗数)要素数の有限体は、要素数が素数ではなくなるため、要素数でのモジュロ算では体が構成できません。

このため、素数べき要素数の有限体では、多項式を数として、多項式のモジュロ算によって有限体を構成します。

素数べき要素数の有限体の要素

まず、$p^n$要素数の有限体では、(整数ではなく)、p要素数の有限体を係数とするn-1次までの多項式を、要素である数として用います。

たとえば、$8=2^3$要素数の有限体の要素である数は、2次までの全多項式

$(0)$、$(1)$、$(a)$、$(a+1)$、$(a^2)$、$(a^2+1)$、$(a^2+a)$、$(a^2+a+1)$

の8個になります。

有限体要素の多項式で使う変数名は、aやα(アルファ)を使うことが多いです。

素数べき要素数の有限体の加算

この数同士での加算は、多項式での加算となります。つまり、係数同士のpモジュロ算での加算です。

8要素数の有限体の加算の例: $(a^2+a+1) + (a^2+1) = (a)$

素数べき要素数の有限体の乗算

要素数が$p^n$個の有限体での乗算は、n次多項式のモジュロ算での乗算を用います。

たとえば、$8=2^3$個要素の有限体では、3次方程式でモジュロ算をします。その結果、2次多項式のどれかになります。

$(0)$、$(1)$、$(a)$、$(a+1)$、$(a^2)$、$(a^2+1)$、$(a^2+a)$、$(a^2+a+1)$

ただし、結果が有限体となるためには、そのモジュロ算で用いる多項式には、(係数はp要素数の有限体の)**n次既約多項式**を用います。

既約多項式

n次既約多項式とは、n次多項式のうち、n次未満の多項式をかけ合わせて構築できるn次可約多項式ではないn次多項式のことです。
また、理由は後述しますが、この既約多項式では、最大次数の係数は1に限定してよいです。

係数が有限体の場合、n次多項式を全て列挙することが可能です。このため、可約多項式も既約多項式も全列挙可能です。

8要素数の有限体のための3次既約多項式は以下のようにして求めまります。

全1次多項式: $(x)$、$(x+1)$
全2次多項式: $(x^2)$、$(x^2+1)$、$x^2+x+1$
全3次可約多項式(6個): $(x^3)$、$(x^3+x^2)$、$(x^3+x)$、$(x^3+x^2+x+1)$、$(x^3+x^2+x)$、$(x^3+1)$
全3次既約多項式(2個): $(x^3+x+1)$、$(x^3+x^2+1)$

そして、有限体の多項式要素$(a)$を、この中から選んだ既約多項式の方程式を満たす解となる数に割り当てます。

つまり、既約多項式として$(x^3+x+1)$を選んだら、多項式の演算のもと、$(a)$は$(a)^3+(a)+(1)=(0)$となる値とする、という意味をもたせるということです。

既約多項式は方程式として扱うため、最高次の係数は1に限定できます。
方程式としては、最高次の係数で、その全ての項の係数を割った多項式による方程式と同等だからです。

たとえば、$2x^2+4x+4 = 0$と$x^2+2x+2 = 0$は方程式として同じ

既約多項式による乗算関係

選んだ2要素有限体係数のn次規約方程式に(a)を代入すると、$(a)^3+(a)+(1)=(0)$となります。
この式を変形すると、

$(a)^3 = -(a)-(1) = (a)+(1) = (a+1)$

となり、これは、多項式$(a)$は、3乗することで多項式(a+1)になる、と解釈します。

多項式$(a^3)$を規約多項式$(a^3+a+1)$でモジュロ算をしたことと同等です。

係数は要素数2の有限体なので、$(a^3) \mod (a^3+a+1) = (-a-1) = (a+1)$

n次だけではなく、n次以上の多項式は、選んだn次既約多項式でモジュロ算を行うことで、必ず有限体の多項式の数のどれかになります。

有限体の要素$(a)$に$(a)$を掛け続け、$(a)$のべき乗を計算することで、以下の関係がもたらされます。

$(a^0) = (1)$
$(a^1) = (a)$
$(a^2) = (a^2)$
$(a^3) = (a+1)$
$(a^4) = (a^2+a)$
$(a^5) = (a^2+a+1)$
$(a^6) = (a^2+1)$
$(a^7) = (1)$

ここでは、$(0)$以外の多項式の数すべてが、$(a)$のべき乗数として算出できました。

べき乗を取ることで、すべての要素になる$(a)$のような数を、その有限体の**原始元(primitive element)**と呼びます。
原始元が解となる既約多項式を、原始多項式と呼びます。

要素数$p^n$によっては、解が原始元とならない既約多項式も存在することがあります。
そういった既約多項式の解を(a)とすると、$(a)$のべき乗では出てこない数が存在します。
この場合でも$(a+1)$等の別の多項式が原始元になります。

しかし、以下の指数表現を用いた乗算の簡略化のために、普通は**$(a)$が原始元となる**よう、既約多項式を選び直します。

この原始元$(a)$の指数表現を用いることで、簡易に乗算を行うことが可能です。
多項式を一度指数表現にし、指数同士を$p^n-1$のモジュロ算で足した結果の指数表現を多項式表現に戻すことです。

例: $(a^2+a) * (a^2+1)$

指数のモジュロ和: $(a^2+a) * (a^2+1) = (a^4) * (a^6) = (a^{4+6 \mod 7}) = (a^3) = (a+1)$
モジュロ乗算: $(a^2+a) * (a^2+1) = a^4+a^2+a^3+a = (a^3)*a + (a^3) + (a^2+a) = (a+1) * a + (a+1) + (a^2+a) = (a+1)$

まとめ: 素数べき要素数の有限体の作り方

要素数が$p^n$な有限体は、

要素: pモジュロ係数のn次多項式すべて
加算: pモジュロ係数のn次多項式の加算(係数ごとのpモジュロ加算)
n次既約多項式の算出
- n未満次多項式を列挙
- 足してn次になる多項式同士をすべて掛け、n次可約多項式を列挙
- n次可約多項式でない、n次多項式を既約多項式として列挙
多項式要素$(a)$を解とするものとして既約多項式を1つ選び、$(a)$について0から$p^n -1$乗までの指数表現を作る
- $(a)$が、$(0)$以外の要素がすべて列挙される原始元にならない場合、別の既約多項式を用いる
乗算: $(a)$の指数表現での指数の和で計算(もしくは既約多項式のモジュロ乗算をする)

で構成できます。

有限体の多項式要素と既約多項式の関係

有限体の多項式要素$(a)$は、選んだn次既約多項式の方程式の解です。
つまり、n次方程式として、$(a)$以外のn-1個の解が、別の多項式要素として存在します。

8要素の有限体の3次既約方程式$x^3+x+1=0$を満たすのは、$(a)$、$(a^2)$、$(a^2+a)$です。

また、選ばなかったn次既約多項式の方程式の解となる数も、それぞれn個づつ多項式要素のどれかになっています。

8要素の有限体の3次既約方程式$x^3+x^2+1=0$を満たすのは、$(a+1)$、$(a^2+1)$、$(a^2+a+1)$です。

すべてのn次既約多項式のそれぞれn個の解すべてがこの有限体の要素になります。($(0)$や$(1)$のように、"n次"既約多項式の解にならない要素はあります)。

乗算のとき作った指数表現にすると、同一の方程式の解である関係が見えます。

$x^3+x+1=0$の解: $(a^1)$、$(a^2)$、$(a^4)$
$x^3+x^2+1=0$の解: $(a^3)$、$(a^6)$、$(a^5)=(a^{12})$

さらに言えば、4 * 2 mod 7 = 1であり、5 * 2 mod 7 = 3です。
一般的には、同一方程式の解は、互いに指数をp倍していった関係(つまりp乗した関係)があります。

このため、どのn次既約多項式を選んでも、要素表示として$(a)$にあたるものが入れ替わっただけになります。

結果として、素数べき要素数の有限体は要素数ごとにただ一つの演算関係を持ちます。

有限体は、要素数で唯一の構造が決まるので、有限体の別名である**ガロア体(Galois Field)**にちなみ、GF($p^n$)と名付けられています。

GF(2), GF(3), GF(5), GF(4)もしくはGF($2^2$),GF(9)もしくは、GF($3^2$)、GF(8)もしくはGF($2^3$), ...

素数べき要素数の有限体の例

以降からは、上述の説明のために用いた、多項式要素である表現のための()は外します。

ここでは実際に例として、要素数の少ない(p,n)=(2,2)、(p,n)=(3,2)、(p,n)=(2,3)の有限体GF($p^n$)を、前述の手順によって構築します。

GF(4)

要素数4の有限体GF(4)は、p=2、n=2の有限体です。

体の要素(1次以下の多項式): $0$, $1$, $a$, $a+1$

加算表(係数ごとの2モジュロ和)

+	$0 $	$1 $	$a $	$a+1$
$0 $	$0 $	$1 $	$a $	$a+1$
$1 $	$1 $	$0 $	$a+1$	$a $
$a $	$a $	$a+1$	$0 $	$1 $
$a+1$	$a+1$	$a $	$1 $	$0 $

(乗算関係をつくるための多項式の列挙)

1次多項式: $x$, $x+1$
2次可約多項式: $x^2$, $x^2+x$, $x^2+1$
2次既約多項式: $x^2+x+1$

選んだ既約方程式から、$a^2+a+1=0$とすると、$a^2$=$a+1$です。よって

$a^0$ = $1$
$a^1$ = $a$
$a^2$ = $a^2$ = $a+1$
$a^3$ = $(a+1)*a$ = $a^2+a$ = $a+1+a$ = $1$

乗算表

*	$0 $	$1 $	$a $	$a+1$
$0 $	$0 $	$0 $	$0 $	$0 $
$1 $	$0 $	$1 $	$a $	$a+1$
$a $	$0 $	$a $	$a+1$	$1 $
$a+1$	$0 $	$a+1$	$1 $	$a $

GF(9)

要素数9の有限体GF(9)は、p=3、n=2の有限体です。

体の要素(1次以下の多項式): $0$, $1$, $2$, $a$, $a+1$, $a+2$, $2a$, $2a+1$, $2a+2$

加算表

+	$0 $	$1 $	$2 $	$a $	$a+1 $	$a+2 $	$2a $	$2a+1$	$2a+2$
$0 $	$0 $	$1 $	$2 $	$a $	$a+1 $	$a+2 $	$2a $	$2a+1$	$2a+2$
$1 $	$1 $	$2 $	$0 $	$a+1 $	$a+2 $	$a $	$2a+1$	$2a+2$	$2a $
$2 $	$2 $	$0 $	$1 $	$a+2 $	$a $	$a+1 $	$2a+2$	$2a $	$2a+1$
$a $	$a $	$a+1 $	$a+2 $	$2a $	$2a+1$	$2a+2$	$0 $	$1 $	$2 $
$a+1 $	$a+1 $	$a+2 $	$a $	$2a+1$	$2a+2$	$2a $	$1 $	$2 $	$0 $
$a+2 $	$a+2 $	$a $	$a+1 $	$2a+2$	$2a $	$2a+1$	$2 $	$0 $	$1 $
$2a $	$2a $	$2a+1$	$2a+2$	$0 $	$1 $	$2 $	$a $	$a+1 $	$a+2 $
$2a+1$	$2a+1$	$2a+2$	$2a $	$1 $	$2 $	$0 $	$a+1 $	$a+2 $	$a $
$2a+2$	$2a+2$	$2a $	$2a+1$	$2 $	$0 $	$1 $	$a+2 $	$a $	$a+1 $

1次多項式: $x$, $x+1$, $x+2$
2次可約多項式: $x^2$, $x^2+x$, $x^2+2x$, $x^2+2x+1$, $x^2+2$, $x^2+x+1$
2次既約多項式: $x^2+1$, $x^2+x+2$, $x^2+2x+2$

既約方程式を$a^2+2a+2=0$とすると、$a^2=a+1$です。よって

$a^0$ = $1$
$a^1$ = $a$
$a^2$ = $a+1$
$a^3$ = $(a+1)*a$ = $a^2+a$ = $a+1+a$ = $2a+1$
$a^4$ = $(2a+1)*a$ = $2a^2+a$ = $2(a+1)+a$ = $2$
$a^5$ = $2a$
$a^6$ = $2a^2$ = $2(a+1)$ = $2a+2$
$a^7$ = $(2a+2)*a$ = $2a^2+2a$ = $2(a+1)+2a$ = $a+2$
$a^8$ = $(a+2)a$ = $a^22a$ = $(a+1)+2a$ = $1$

乗算表

*	$0 $	$1 $	$2 $	$a $	$a+1 $	$a+2 $	$2a $	$2a+1$	$2a+2$
$0 $	$0 $	$0 $	$0 $	$0 $	$0 $	$0 $	$0 $	$0 $	$0 $
$1 $	$0 $	$1 $	$2 $	$a $	$a+1 $	$a+2 $	$2a $	$2a+1$	$2a+2$
$2 $	$0 $	$2 $	$1 $	$2a $	$2a+2$	$2a+1$	$a $	$a+2 $	$a+1 $
$a $	$0 $	$a $	$2a $	$a+1 $	$2a+1$	$1 $	$2a+2$	$2 $	$a+2 $
$a+1 $	$0 $	$a+1 $	$2a+2$	$2a+1$	$2 $	$a $	$a+2 $	$2a $	$1 $
$a+2 $	$0 $	$a+2 $	$2a+1$	$1 $	$a $	$2a+2$	$2 $	$a+1 $	$2a $
$2a $	$0 $	$2a $	$a $	$2a+2$	$a+2 $	$2 $	$a+1 $	$1 $	$2a+1$
$2a+1$	$0 $	$2a+1$	$a+2 $	$2 $	$2a $	$a+1 $	$1 $	$2a+2$	$a $
$2a+2$	$0 $	$2a+2$	$a+1 $	$a+2 $	$1 $	$2a $	$2a+1$	$a $	$2 $

ちなみに、既約方程式は3つありますが、有限体の多項式な要素は、それぞれそのうちのどれかの解の一つです。よって、その既約多項式に要素をいれると0になります。

$a$は、$x^2+2x+2=0$の解です。
$(a+1)^2$ = $2$なので、2+1=0から、$a+1$は$x^2+1=0$を満たす解になります。
$(a+2)^2$ = $2a+2$なので、(2a+2)+(a+2)+2=0から、$a+2$は$x^2+x+2=0$を満たす解になります。
$2a+1$は、$x^2+2x+2=0$の解です。
$2a+2$は、$x^2+1=0$の解です。
$2a$は、$x^2+x+2=0$の解です。

同一既約方程式の解同士は、べき乗表現から以下の関係になります。

既約方程式	$1 = 3^0 = 3^2$	$3 = 3^1$
$x^2+2x+2=0$	$a = a^9$	$2a+1 = a^3$
$x^2+1=0$	$a+1 = a^2 = (a^2)^9$	$2a+2 = a^6 = (a^2)^3$
$x^2+x+2=0$	$a+2 = a^7 = (a^7)^9$	$2a = a^5 = (a^7)^3$

GF(8)

要素数8の有限体GF(8)は、p=2、n=3の有限体です。

体の要素(2次以下の多項式): $0$, $1$, $a$, $a+1$, $a^2$, $a^2+1$, $a^2+a$, $a^2+a+1$

加算表

+	$0 $	$1 $	$a $	$a+1 $	$a^2 $	$a^2+1 $	$a^2+a $	$a^2+a+1$
$0 $	$0 $	$1 $	$a $	$a+1 $	$a^2 $	$a^2+1 $	$a^2+a $	$a^2+a+1$
$1 $	$1 $	$0 $	$a+1 $	$a $	$a^2+1 $	$a^2 $	$a^2+a+1$	$a^2+a $
$a $	$a $	$a+1 $	$0 $	$1 $	$a^2+a $	$a^2+a+1$	$a^2 $	$a^2+1 $
$a+1 $	$a+1 $	$a $	$1 $	$0 $	$a^2+a+1$	$a^2+a $	$a^2+1 $	$a^2 $
$a^2 $	$a^2 $	$a^2+1 $	$a^2+a $	$a^2+a+1$	$0 $	$1 $	$a $	$a+1 $
$a^2+1 $	$a^2+1 $	$a^2 $	$a^2+a+1$	$a^2+a $	$1 $	$0 $	$a+1 $	$a $
$a^2+a $	$a^2+a $	$a^2+a+1$	$a^2 $	$a^2+1 $	$a $	$a+1 $	$0 $	$1 $
$a^2+a+1$	$a^2+a+1$	$a^2+a $	$a^2+1 $	$a^2 $	$a+1 $	$a $	$1 $	$0 $

1次多項式: $x$, $x+1$
2次多項式: $x^2$, $x^2+1$, $x^2+x$, $x^2+x+1$
3次可約多項式: $x^3$, $x^3+x$, $x^3+x^2$, $x^3+x^2+x$, $x^3+x^2+x+1$, $x^3+1$
3次既約多項式: $x^3+x+1$, $x^3+x^2+1$

既約方程式を$a^3+a+1=0$とすると、$a^3=a+1$です。よって、

$a^0$ = $1$
$a^1$ = $a$
$a^2$ = $a^2$
$a^3$ = $a+1$
$a^4$ = $(a+1)*a$ = $a^2+a$
$a^5$ = $(a^2+a)*a$ = $a^3+a^2$ = $a^2+a+1$
$a^6$ = $(a^2+a+1)*a$ = $a^3+a^2+a$ = $(a+1)+a^2+a$ = $a^2+1$
$a^7$ = $(a^2+1)*a$ = $a^3+a$ = $(a+1)+a$ = $1$

乗算表

*	$0 $	$1 $	$a $	$a+1 $	$a^2 $	$a^2+1 $	$a^2+a $	$a^2+a+1$
$0 $	$0 $	$0 $	$0 $	$0 $	$0 $	$0 $	$0 $	$0 $
$1 $	$0 $	$1 $	$a $	$a+1 $	$a^2 $	$a^2+1 $	$a^2+a $	$a^2+a+1$
$a $	$0 $	$a $	$a^2 $	$a^2+a $	$a+1 $	$1 $	$a^2+a+1$	$a^2+1 $
$a+1 $	$0 $	$a+1 $	$a^2+a $	$a^2+1 $	$a^2+a+1$	$a^2 $	$1 $	$a $
$a^2 $	$0 $	$a^2 $	$a+1 $	$a^2+a+1$	$a^2+a $	$a $	$a^2+1 $	$1 $
$a^2+1 $	$0 $	$a^2+1 $	$1 $	$a^2 $	$a $	$a^2+a+1$	$a+1 $	$a^2+a $
$a^2+a $	$0 $	$a^2+a $	$a^2+a+1$	$1 $	$a^2+1 $	$a+1 $	$a $	$a^2 $
$a^2+a+1$	$0 $	$a^2+a+1$	$a^2+1 $	$a $	$1 $	$a^2+a $	$a^2 $	$a+1 $

ちなみに、$a$、$a^2$, $a^2+a$が$x^3+x+1=0$の解であり、$a+1$、$a^2+1$、$a^2+a+1$が$x^3+x^2+1=0$の解です。

同一既約方程式の解同士は、べき乗表現から以下の関係になります。

既約方程式	$1 = 2^0 = 2^3$	$2 = 2^1$	$4 = 2^2$
$x^3+x+1=0$	$a = a^8$	$a^2$	$a^2+a = a^4$
$x^3+x^2+1=0$	$a+1 = a^3 = (a^3)^8$	$a^2+1 = a^6 = (a^3)^2$	$a^2+a+1 = a^5 = (a^3)^4$

素数べき要素数の有限体のガロア群

置換と群

集合の要素同士を入れ替える変換を置換(Permutation)といいます。
入れ替えなので、置換は、変換元に対して、変換先の要素に過不足のない、**1対1の変換(全単射, bijection)**になります。

置換を行った結果にさらに置換を行う、といった繰り返しの適用が可能で、置換を繰り返し適用することも置換となります。
全要素を入れ替えない**恒等置換e(x)**も置換とします。

恒等置換を含む、同一対象への置換同士の繰り返し適用関係がとる構造が群(Group)です。
群構造を持つ置換の集合のことを、置換群と呼びます。

演算関係の維持など、対象への入れ替えに制約をつけると、集合要素に対して取りうる全置換の一部分だけが適用可能になります。
このような、大きな群の一部だけで群が構成できる部分集合のことを部分群といいます。

対象の持つ性質や制約と、その性質や制約を維持する置換のなす群の構造は、対応関係を持ちます。
これが群に注目する理由となります。

対象の置換群にどのような部分群構造を持つかを調べることで、その対象が持つ性質や制約が判明します。

体の自己同型

つぎに、体のように要素に演算関係を持つ集合(代数構造)について考えます。

集合についた演算関係を維持する置換のことを自己同型(Automorphism)といいます。

体の場合は、加算と乗算の関係を維持することです。
置換をf(x)とすると、f(x)が自己同型であるには、体の任意の要素a,bに対し、

$f(a) + f(b) = f(a + b)$
$f(a) * f(b) = f(a * b)$

が成立することが条件となります。

恒等置換は、自明な自己同型になります。

また、どんな体のどんな自己同型f(x)も、0と1は入れ替えません。

$f(a) + f(0) = f(a+0) = f(a) = f(a) + 0$ より、$f(0) = 0$
$f(a) * f(1) = f(a*1) = f(a) = f(a) * 1$ より、$f(1) = 1$

そして、0と1が入れ替え不可能なことから、1を足し続けることで得られる整数値(とその負数と逆数)で構成する、有理数体Qの自己同型は、恒等置換e(x)のみです。

部分体と拡大体

例示した加算表と乗算表を見れば、GF(4)やGF(8)は、左上の0と1だけの部分で完結する、要素数2の有限体GF(2)となっています。GF(9)も、左上の0,1,2だけで完結する、要素数3の有限体GF(3)となります。

これはGF(4)やGF(8)はGF(2)を部分体としてもつ構造である、といいます。
同様のことを、GF(4)やGF(8)は、GF(2)の拡大体である、ともいいます。

一般的に、有限体GF($p^n$)は、必ずGF(p)を部分体として持ちます。

体のガロア群

自己同型の変換がなす群のことを、ガロア群といいます。

そして、体のガロア群の部分群の存在が、その体が(何らかの体の)拡大体であるという性質に対応しています。

ある自己同型変換について、変換の前後で変化しない要素をすべてとりだすと、それらは部分体の関係を持っている

このことから、たとえば、

拡大体でなければ、自己同型が成立する置換は、恒等置換のみになる
恒等置換以外の自己同型があれば、部分体が存在する

ことになります。

ちなみに、有理数体と同様の理由で、素数要素数の有限体GF(p)の自己同型は恒等置換のみであり、どんな素数pであっても部分体は存在しません。

素数べき要素数の有限体の自己同型

結論から言うと、有限体GF($p^n$)の自己同型となる変換は、指数表現での指数をp倍($\mod p^n-1$)する変換です。この指数のp倍の繰り返しが、その有限体の置換群をなします。

つまり、自己同型は、同一方程式の解同士での入れ替え関係になります。

具体的には、

GF(4): $a$と$a+1$を入れ替える
GF(9): ($a$, $a+1$, $a+2$)の組を($2a+1$、$2a+2$, $2a$)の組とで同時に入れ替える
GF(8): ($a$, $a+1$)の組を($a^2$, $a^2+1$)へ、($a^2$, $a^2+1$)の組を($a^2+a$, $a^2+a+1$)へ、($a^2+a$, $a^2+a+1$)の組を($a$, $a+1$)へ同時に入れ替える

が自己同型変換になっています。

素数べき要素数の有限体のガロア群

既約方程式の解はn個なので、解同士の入れ替えである自己同型、指数のp倍は、n回くりかえせば元に戻る性質があります。

変換をn回繰り返すともとに戻る(恒等置換になる)群のことは、n次巡回群(Cyclic group)といいます。
ちなみに、1次巡回群は恒等置換のことです。

よって、GF(p^n)のガロア群は、n次巡回群である、ということになります。

n次巡回群の部分群は、nの約数次の巡回群すべてです。

たとえば、6回でもとに戻る変換を2回繰り返した変換は、3回行えばもとにもどります。
また、6回でもとに戻る変換を3回繰り返した変換は、2回行えばもとにもどります。

このため6次巡回群は、部分群に、2次巡回群と3次巡回群の双方を持つことになります。

ここで、6次巡回群をガロア群とするGF($64=2^6$)について、群の視点から、その構造を観察していきます。

GF($4=2^2$)のガロア群が2次巡回群、GF($8=2^3$)のガロア群が3次巡回群であることから、GF($64=2^6$)が、GF(4)とGF(8)をそれぞれ部分体もっていることが示唆されます。

これはすなわち、GF(64)の多項式要素には、(GF(4)の)2次既約方程式1つを満たす要素2つと、(GF(8)の)3次既約方定式2つをそれぞれ満たす要素6つが、ともに含まれていることを意味します。

ここから、GF(2)の(1次既約方程式の解でもある)0と1の2つを除く、54(=64-2-2-6)個の要素が6次既約方程式の解であることになります。
さらに、それぞれの6次既約方程式の解は6個づつあるので、(2モジュロ係数の)6次既約方定式の総数は9個あることが得られます。

6次既約多項式が9個あることは、原始元aの指数の2倍(のmod 63)を繰り返すことでできる指数のグルーピングでも確認できます。

0
1,2,4,8,16,32,
3,6,12,24,48,33
5,10,20,40,17,34
7,14,28,56,49,35
9,18,36
11,22,44,25,50,37
13,26,52,41,19,38
15,30,60,57,51,39
21,42
23,46,29,58,53,43
27,54,45
31,62,61,59,55,47

グループ内の要素数に注目することで、$a^{21}$と$a^{42}$は部分体GF(4)の要素であり、$a^9$、$a^{18}$、$a^{36}$と$a^{27}$、$a^{54}$、$a^{45}$が部分体GF(8)の要素であることが決まります。

ただし、どの指数のグループが、複数あるどの既約多項式を満たすかは、$a$を解とする原始多項式の選択できまることです。

指定した要素が解となる既約方程式の求め方

ある多項式要素がどの既約方程式を満たすものかを見つけるためには、その多項式要素が解となる既約多項式の係数をとくための連立方程式を作って行います。

たとえば、$a^3+a+1=0$なGF(8)で$a+1$が満たす既約多項式の係数の連立方程式を作ってみます。

$a+1$を解に持つ3次既約方程式を$x^3+sx^2+tx+u=0$とし、このs,t,uを求めることです。

ちなみに、$(a+1)^2=a^2+1$、$a^3=a+1$より$(a+1)^3=a^9=a^2$です。
よって、x=a+1を代入すると、$(a^2) +s*(a^2+1) + t*(a+1) + u = 0$となります。

aの多項式として各項を展開し、aの指数ごとに分離して、連立方程式にします。

$(1+s)a^2 + ta + (s+t+u) = 0$

ここから

$a^2$: $1+s=0$
$a^1$: $t=0$
$a^0$: $s+t+u=0$

これを解くと、s=1, t=0, u=1が得られます。
よって、$a+1$を解とする既約方程式は、$x^3+x+1=0$だったのでした。

GF(64)における2次既約多項式や3次既約多項式も、同様に求められます。

ただし、有効な変数に対して連立式が多くなり、得られる連立方程式が一次独立ではなくなるので、機械的に解く場合などでは注意が必要です。有限体での冗長な連立方程式が解ける必要があります。

その他

有限体の平方根

数eの平方根は、2乗するとeになる数のことです。

0以外の有限体の数は原始元aのべき乗でも表現できるので、$a^k$の二乗である$a^{2k \mod p^n-1}$の平方根が$a^k$になります。これは$p^n-1$が偶数か奇数かで違いが出ます。つまり、pが2のときと、それ以外の奇素数とで違いがあります。

p=2のとき: すべての数に平方根が1つづつある
- $a^{2m}$の平方根の指数: $m$
- $a^{2m+1}$の平方根の指数: $\frac{(2m+1) + (2^n-1)}{2}$
p>2のとき: 数$a^k$の指数kが偶数のとき平方根となる数が2つあり、kが奇数のときは平方根は存在しない
- $a^{2m}$の平方根の指数 $m$、$m + \frac{p^n-1}{2}$

また、有限体GF($p^n$)の**$p-1$は$1=a^0=a^{p^n-1}$の平方根**の一つです(もう一つは1)。$(p-1)^2 = p^2-2p+1 \mod p = 1$だからです。これは当然GF(p)にも当てはまります。

$(p-1)^2 = 1$

逆に考えるとp >= 3のときの、$p-1$は、任意の原始元aで$a^{\frac{p^n-1}{2}}$になります。

$p-1 = a^{\frac{p^n-1}{2}}$

また、p>=5なGF(p)では、$p-1$は2乗するだけで1になるため、原始元にはなりません。

この結果、有限体の0以外の**全要素を一つづつかけ合わせたものは$p-1$**になることが判明します。

$\prod_{k=0}^{p^n-2}a^k = p - 1$

まず、$a^0$から$a^{p^n-2}$までをかけるので、結果の原始元aの指数は総和$\frac{(p^n-2)(p^n-1)}{2}$になります。

p>2のときは、偶数になるのは$(p^n-1)$側なので、$p^n-1$でmodをとると($p^n-2 \mod p^n-1 = -1$より)、$-\frac{p^n-1}{2}$となります。これを$\mod p^n-1$での($p^n-1$を足すことで)正値にすると、$\frac{p^n-1}{2}$になります。この結果から、総乗したものは$a^{\frac{p^n-1}{2}}$となり、先の結果から必ず$p-1$と等しくなります。よって、0以外の全要素を総乗すると$p-1$となります。
p=2ならば、偶数になるのは$(p^n-2)$側です。よって$\mod p^n-1$をとると0になり、$a^0=1$で、p=2のときも結果的にp-1になります。

全既約多項式の積

GF($p^n$)の要素は、いずれかの既約方程式を解に持つ多項式でした。

たとえば、GF(4)の$a$と$a+1$は、既約方程式$x^2+x+1=0$解でした。

解であることから、**$(x-a)(x-(a+1))$は、$x^2+x+1$**と等しくなります。
なぜなら、方程式として$x^2+x+1=0$の解である以上、$x^2+x+1$は$x-a$で割り切れ、また$x-(a+1)$でも割り切れなくてはなりません。そして方程式の次数が2である以上、条件を満たす2次の式は、$(x-a)(x-(a+1))$のみだからです。
これは、展開した各係数$(a)+(a+1)=1$、$(a) * (a+1) = 1$であることでも確認可能です。

また、有限体の0以外の値は、$どれもp^n-1$乗すると1になります。つまり、有限体の0以外の値は

$x^{p^n-1}-1=0$

の解になります。そして、0以外の数である$a^k$は$x^{p^n-1}-1=0$の解であることから、$x^{p^n-1}-1$はどの$x-a^k$で割り切れる式になります。$a^k$は0から$a^{pn-2}$の{p^n-1}種類あり、$x^{p^n-1}-1$の次数も$p^n-1$であるため、

$x^{p^n-1}-1 = \prod_{k=0}^{p^n-2}(x-a^k)$

が成立します。この$x^{p^n-1}-1$は、$a^k$を解に持つ既約多項式すべてをかけ合わせたものでもあります。
言い換えると、$x^{p^n-1}-1$は、GF($p^n$)の要素を解に持つどの既約多項式でも割り切れる多項式である、といえます。

そして、要素0の既約方程式は$x=0$とすると、GF($p^n$)の要素を解に持つ既約多項式を全て掛け合わせると

$x^{p^n}-x=0$

となります。

そして、0を含む有限体GF($p^n$)の要素xはすべて、$x^{p^n}=x$つまり、要素数と同じ$p^n$乗するともとの値に戻ることも証明されます。

これはn=1であるGF(p)のケースでも同様に成立します。

また、$x^{p^n-1}-1 = \prod_{k=0}^{p^n-2}(x-a^k)$より、右辺を展開したときの$p^n-2$次の係数は、0以外の要素をすべて足した$-\sum_{k=0}^{p^n-2}a^k$であり、これは0になります。よって、

$-\sum_{k=0}^{p^n-2}a^k=0$

です。これは0も含めて、有限体の全要素をすべて足すと0になる、とも言えます。
これは他の係数についても言えます。

$\sum_{k=0}^{p^n-3}a^k\sum_{j=k+1}^{p^n-2}a^j = 0$
$\sum_{k=0}^{p^n-4}a^k\sum_{j=k+1}^{p^n-3}a^j\sum_{i=j+1}^{p^n-2}a^i = 0$
...

GF(p^n)をもとに作る素数べき要素数の有限体GF((p^n)^m)

素数要素数のGF(p)だけでなく、素数べき要素数のGF($p^n$)を係数にした多項式でも、GF($(p^n)^m$)を構築することが可能です。
前述の手法のGF(p)係数とそのモジュロ演算の代わりに、GF($p^n$)係数とその演算系を用いるだけです。

例としてGF(4)を用い、GF($16=4^2$)を構築してみます。

GF(4): $0$、$1$、$a$、$a+1$
- $a^2 = a + 1$、$a * (a+1) = 1$

GF(16)の要素16個(原始元はb)

$0$、$1$、$a$、$a+1$
$b$、$b+1$、$b+a$、$b+(a+1)$
$ab$、$ab+1$、$ab+a$、$ab+(a+1)$
$(a+1)b$、$(a+1)b+1$、$(a+1)b+a$、$(a+1)b+(a+1)$

(加算は略)

乗算関係の定義

GF(4)係数の1次多項式(4個): $x$、$x+1$、$x+a$、$x+(a+1)$
GF(4)係数の2次可約多項式(10個): $x^2$、$x^2+x$、 $x^2+ax$、 $x^2+(a+x)x$、 $x^2+1$、 $x^2+(a+1)x+a$、 $x^2+ax+(a+1)$、$x^2+a+1$、 $x^2+x+1$、 $x^2+a$
GF(4)係数の2次既約多項式(6個): $x^2+x+a$、$x^2+x+(a+1)$、$x^2+ax+1$、$x^2+ax+a$、$x^2+(a+1)x+1$、$x^2+(a+1)x+(a+1)$

ここでは、$b^2+b+a=0$を選択します。つまり、$b^2=b+a$

指数表現

$b^0=1$
$b^1=b$
$b^2=b+a$
$b^3=(a+1)b+a$
$b^4=ab+(a+1)(b+a)=ab+ab+b+a+1+1=b+1$
$b^5=b+b+a=a$
$b^6=ab$
$b^7=ab+(a+1)$
$b^8=(a+1)b+a(b+a)=b+(a+1)$
$b^9=(a+1)b+b+a=ab+a$
$b^{10}=ab+a(b+a)=a+1$
$b^{11}=(a+1)b$
$b^{12}=(a+1)(b+a)=(a+1)b+1$
$b^{13}=b+(a+1)(b+a)=ab+1$
$b^{14}=b+a(b+a)=(a+1)b+(a+1)$
$b^{15}=(a+1)b+(a+1)(b+a)=1$

と、bは原始元になり、乗算の関係が構築できます。

２の4乗として作るとき、4次既約多項式3個になりますが、4の2乗で構築するときは、2次既約多項式が6個になります。

この2次既約多項式は、指数を4倍する自己同型によって、同一既約方程式の解としての分類ができます。

例: $b$と$b^4$が、同一2次既約多項式$x^2+x+a=0$を満たす解

また指数の2倍での自己同型では、$b$と$b^2$は同じ4次多項式の解に分類されます。
$b^2$つまり$b+a$を解に持つ2次既約多項式は、$x^2+x+(a+1)$です。$b^8$はこの多項式のもう一つの解になります。

$x^2+x+a$と$x^2+x+(a+1)$をかけると、$x^4+x+1$となり、これはGF(4)の部分体である2モジュロ係数での4次既約多項式でもあります(GF(4)係数での既約多項式をかけてできた結果なので、GF(4)係数では可約多項式です)。
自己同型で分類関係のある要素の既約多項式をかけあわせれば、係数が部分体の要素だけで構成され、その部分体での既約多項式になります。

この関係性から、2モジュロ係数での多項式要素との間の対応を取ることができるようになります。

$x^4+x+1$の解のAと、$x^2+x+a$の解のbを対応させることができます。
同様に、$x^4+x+1$の解のAと、$x^2+x+(a+1)$の解のbとも対応させることもできます。
この違いは、$A^2$に対応するのが$b+a$か$b+a+1$かの違いとして現れます。