標数と位数

　有限個の要素からなる体を有限体と呼びます。 その要素の個数を位数（いすう）と呼びます。
　有限体 $F$ は有限集合ですから有理数体は含みません。 従ってその標数はある素数 $p$ になり、 $F$ は $\FF_p$ 上の有限次元ベクトル空間の構造を持ちます ( 体の項 参照 ) 。 その次元を $n$ とすると、 $F$ はベクトル空間としては $(\FF_p)^n$ と同型ですから、 その位数は $p^n$ になります。 すなわち、有限体の位数は素数べきに限定されます。

　素数 $p$ と自然数 $n$ を与えると、

• 位数 $p^n$ の有限体が必ず存在する
• 位数 $p^n$ の有限体はお互いに全て同型である

ことが知られています。 そこで位数 $p^n$ の有限体を $\FF_{p^n}$ あるいは $\mbox{GF}(p^n)$ と表します ( GF は Galois field の頭文字 )。 有限体が $\FF_q$ と表記されているときは $q$ は必ず素数べきを表しています。

$\FF_4$

　4個の要素を持つ有限体 ( 4元体 ) $\FF_4$ を作ってみましょう。

1. $4 = 2^2$ ですので $\FF_4$ の標数は $2$ でなければなりません。 つまり、$\bmod 2$ の計算がベースにあります。
2. 素体 $\FF_2$ には属さない $\FF_4$ の元 $\alpha$ をひとつ取りましょう。
3. $1$ と $\alpha$ が $\FF_4$ の $\FF_2$ 上の基底になりますので、 $\FF_4$ の4つの元は $0$, $1$, $\alpha$, $\alpha + 1$ です。
4. $\alpha^2$ も $\FF_4$ の元ですから $0$, $1$, $\alpha$, $\alpha + 1$ のいずれかに一致しますが、 体は零因子を持たないことから $$ \alpha^2 = \alpha + 1 $$ であることがわかります。実際、
   • もし $\alpha^2 = 0$ なら $\alpha \neq 0$ に矛盾
   • もし $\alpha^2 = 1$ なら $\alpha = \pm 1 = 1$ となり $\alpha \neq 1$ に矛盾
   • もし $\alpha^2 = \alpha$ なら $\alpha = 0$ or $1$ となり 「 $\alpha \neq 0$ and $\alpha \neq 1$ 」 に矛盾
5. という訳で、$\FF_4$ とは、$\bmod 2$ の上で $\alpha^2 = \alpha + 1$ を満たす数を考えることになります。 少し計算例を書いておきましょう：
   • $(\alpha + 1)^2 = \alpha^2 + 2 \alpha + 1 = \alpha^2 + 1 = (\alpha + 1) + 1 = \alpha$
   • $\alpha^3 = \alpha × \alpha^2 = \alpha (\alpha + 1) = \alpha^2 + \alpha = (\alpha + 1) + \alpha = 1$
   $\bmod 2$ は係数には使えますが、べき指数に使ってはいけません、お間違えなく。

16人麻雀

　16人で麻雀大会を開こうと思います。 全ての人が自分以外の15人と丁度１回ずつ対戦するような組合せ表を $\FF_4$ を利用して作ってみましょう。 上のように $\FF_4$ = $\FF_2(\alpha)$ ( ただし $\alpha^2 = \alpha + 1$ ) と表し、 簡単のため $\beta = \alpha + 1$ と書くことにします。

1. $\FF_4$ 上の $xy$-平面 $P$ を考えます。
2. $P$ にある16個の点を16人の雀士に対応させます。
3. $P$ 上の直線たちには次のような性質があります：
   • 各直線上には点が４個ずつ乗っている
   • 平行な直線は４本ずつある
   • 方向ベクトルは５通りある
   • ２つの点を通る直線は１本だけある
   具体的には
   • 方向ベクトル $( 0, 1 )$ :
     直線 $y = 0$ : $( 0, 0 )$, $( 1, 0 )$, $( \alpha, 0 )$, $( \beta, 0 )$
     直線 $y = 1$ : $( 0, 1 )$, $( 1, 1 )$, $( \alpha, 1 )$, $( \beta, 1 )$
     直線 $y = \alpha$ : $( 0, \alpha )$, $( 1, \alpha )$, $( \alpha, \alpha )$, $( \beta, \alpha )$
     直線 $y = \beta$ : $( 0, \beta )$, $( 1, \beta )$, $( \alpha, \beta )$, $( \beta, \beta )$
   • 方向ベクトル $( 1, 0 )$ :
     直線 $x = 0$ : $( 0, 0 )$, $( 0, 1 )$, $( 0, \alpha )$, $( 0, \beta )$
     直線 $x = 1$ : $( 1, 0 )$, $( 1, 1 )$, $( 1, \alpha )$, $( 1, \beta )$
     直線 $x = \alpha$ : $( \alpha, 0 )$, $( \alpha, 1 )$, $( \alpha, \alpha )$, $( \alpha, \beta )$
     直線 $x = \beta$ : $( \beta, 0 )$, $( \beta, 1 $), $( \beta, \alpha )$, $( \beta, \beta )$
   • 方向ベクトル $( 1, 1 )$ :
     直線 $x + y = 0$ : $( 0, 0 )$, $( 1, 1 )$, $( \alpha, \alpha )$, $( \beta, \beta )$
     直線 $x + y = 1$ : $( 0, 1 )$, $( 1, 0 )$, $( \alpha, \beta )$, $( \beta, \alpha )$
     直線 $x + y = \alpha$ : $( 0, \alpha )$, $( 1, \beta )$, $( \alpha, 0 )$, $( \beta, 1 )$
     直線 $x + y = \beta$ : $( 0, \beta )$, $( 1, \alpha )$, $( \alpha, 1 )$, $( \beta, 0 )$
   • 方向ベクトル $( 1, \alpha )$ :
     直線 $ｘ + \alpha\,y = 0$ : $( 0, 0 )$, $( 1, \beta )$, $( \alpha, 1 )$, $( \beta, \alpha )$
     直線 $ｘ + \alpha\,y = 1$ : $( 0, \beta )$, $( 1, 0 )$, $( \alpha, \alpha )$, $( \beta, 1 )$
     直線 $ｘ + \alpha\,y = \alpha$ : $( 0, 1 )$, $( 1, \alpha )$, $( \alpha, 0 )$, $( \beta, \beta )$
     直線 $ｘ + \alpha\,y = \beta$ : $( 0, \alpha )$, $( 1, 1 )$, $( \alpha, \beta )$, $( \beta, 0 )$
   • 方向ベクトル $( 1, \beta )$ :
     直線 $x + \beta\,y = 0$ : $( 0, 0 )$, $( 1, \alpha )$, $( \alpha, \beta )$, $( \beta, 1 )$
     直線 $x + \beta\,y = 1$ : $( 0, \alpha )$, $( 1, 0 )$, $( \alpha, 1 )$, $( \beta, \beta )$
     直線 $x + \beta\,y = \alpha$ : $( 0, \beta )$, $( 1, 1 )$, $( \alpha, 0 )$, $( \beta, \alpha )$
     直線 $x + \beta\,y = \beta$ : $( 0, 1 )$, $( 1, \beta )$, $( \alpha, \alpha )$, $( \beta, 0 )$
4. そこで、方向ベクトルを共有する４本の直線を雀卓、５つの方向ベクトルを時間帯と考えて対戦表を組みます。 $\alpha$, $\beta$ を $2$, $3$ に置き換えて4進数と思って雀士の番号を書けば以下の通りです：

   	卓１	卓２	卓３	卓４
   １回戦	0, 4, 8, 12	1, 5, 9, 13	2, 6, 10, 14	3, 7, 11, 15
   ２回戦	0, 1, 2, 3	4, 5, 6, 7	8, 9, 10, 11	12, 13, 14, 15
   ３回戦	0, 5, 10, 15	1, 4, 11, 14	2, 7, 8, 13	3, 6, 9, 12
   ４回戦	0, 7, 9, 14	3, 4, 10, 13	1, 6, 8, 15	2, 5, 11, 12
   ５回戦	0, 6, 11, 13	2, 4, 9, 15	3, 5, 8, 14	1, 7, 10, 12

このように有限体上の幾何学（有限幾何）を考えると、対称性を持った組合せが簡単に作れたりします。

有限体上の多項式の微分

　有限体には距離の概念がありませんので極限を用いることはできないのですが、 $$ (x^n) ' = n x^{n－1} $$ を定義として採用すれば、実数上と同じ微分の公式たちが使え、 といった定理も成り立ちます。

有限体の乗法群

　有限体 $F$ の $0$ 以外の要素からなる集合 $F^{\times} = \{\, x \in F \,|\, x \neq 0 \,\}$ は乗法に関する群となりますので、 ラグランジュの定理より ことが言えます。 更に著しい性質は ことです。（定理Ａ、定理Ｂと、元の位数の議論を用いて証明している本が多いです。） その巡回群としての生成元を $F$ の原始根と呼びます。 $F$ が素体 $\FF_p$ であるときには法 $p$ ( $\bmod p$ ) の原始根、とも呼びます。 （ 「 1 の原始 $n$ 乗根 」 というのは、全く無関係という訳ではありませんが、別物です。 ） 少し例を挙げておくと

• $\FF_3$ の原始根 : $2$
• $\FF_5$ の原始根 : $2$, $3$
• $\FF_7$ の原始根 : $3$, $5$
• $\FF_11$ の原始根 : $2$, $6$, $7$, $8$
• $\FF_4$ の原始根 : $\alpha$, $\beta$

　暗号理論では、この「巡回群である」という性質を利用して Diffie-Hellman の鍵交換システムや ElGamal 暗号が 設計されます。

有限体 $\FF_{p^n}$ の構成法

　有限体 $\FF_{p^n}$ を構成するには $\FF_p$ 上の $n$ 次既約多項式 $f(x)$ を用います ( 次項参照 ) 。 理論的には $f(x)$ の根 $\alpha$ を $\FF_p$ に付加した体 $\FF_p(\alpha)$ が $\FF_{p^n}$ になりますが、 体の項で述べたように、 $\FF_p$ 上の多項式環で $\bmod f(x)$ の計算をすることが $\FF_p(\alpha)$ を考えることになります。

　繰り返しますが、剰余環 $\FF_p[x] / ( f(x) )$ の計算は次のように行います：

• 元は $\FF_p$ 係数の $n－1$ 次以下の多項式で表す
• 加法・減法は多項式の和・差の係数を $\bmod p$ で計算する
• 乗法は多項式の積を $\bmod p$ と $\bmod f(x)$ で計算する
• $0$ でない元 $g(x)$ の逆数は次のように求める： $\FF_p$ 係数の多項式として $f(x)$ と $g(x)$ を入力とする拡張ユークリッドアルゴリズムを実行して $$ f(x) u(x) + g(x) v(x) = 1 $$ となる多項式 $u(x)$, $v(x)$ を求めれば、 $\FF_{p^n}$ の元として $v(x)$ = g(x)^{-1}$ となる
• 除法は逆数が計算できれば明らか

---

　$\FF_{p^n}$ は $\FF_p$ 上の $x^{p^n}-x$ の最小分解体として特徴付けられますので ( 定理Ｂの系 )、 位数 $p^n$ の有限体は必ず存在し、かつ、すべて同型になります。 また、分離拡大の知識を用いると、有限体の有限次代数拡大は分離的ゆえ単純拡大であることがわかり、 $\FF_{p^n}$ を生成する元の最小多項式は $\FF_p$ 上の $n$ 次既約多項式でなければなりません。

$\FF_p$ 上の $n$ 次既約多項式の求め方

　素数判定と同じ理屈で、 $\FF_p$ 上の $n$ 次多項式 $f(x)$ は、$n / 2$ 次以下の因子を持たなければ既約になります。
　$\FF_p$ 上の $m$ 次既約多項式の根は $\FF_p$ 上の $m$ 次拡大を生成し、 定理Ｂからそれは $x^{p^m-1} - 1$ の根になります。 $0$ も合わせて考えれば であることがわかります。 これを利用して $\FF_p$ 上の $n$ 次既約多項式を生成しましょう：

while 1:
    f(x) = Fp 上のランダムな n 次モニック多項式
    ok = True
    g(x) = x
    for m = 1 to (n / 2):
        g(x) = g(x)^p mod f(x)
        h(x) = gcd(g(x) - x, f(x))
        if h(x) != 1:
            ok = False
            break
    if ok:
        return f(x)

ここで $g(x)$ は $x^{p^m}$ を $f(x)$ で割った剰余を格納する変数で、 $p$ が大きいときには反復２乗法を用いて計算します：

入力：g(x), e, f(x)
出力：g(x)^e mod f(x)

h(x) = 1
while e > 0:
    if e % 2 == 1:
        h(x) = h(x) * g(x) mod f(x)
    g(x) = g(x) * g(x) mod f(x)
    e /= 2
return h(x)

また $\gcd$ は多項式のユークリッドアルゴリズムで求めます。 $x^{p^m} - x$ と $f(x)$ が互いに素でなければ $f(x)$ は $m$ 次因子を持つので既約でなくなり、 $m \leq (n / 2)$ の範囲で $m$ 次因子を持たなければ既約と判定する、という仕組みです。
　$p$ が $2$ でなければ、2次既約多項式はこんな面倒なことをしなくても、$\bmod p$ の平方非剰余 $a$ をひとつみつけて $x^2-a$ でＯＫです。 また3次既約多項式についても、 $p－1$ が $3$ の倍数ならば、3乗数でない $a$ をひとつみつけて $x^3-a$ でＯＫです。 3乗数でないことは $a^{p-1}/3 \neq 1$ という式で判定できます。

既約多項式の例

$\FF_2$ 上	$x^2 + x + 1$,  $x^3 + x + 1$,  $x^4 + x + 1$,  $x^5 + x^2 + 1$,  $x^6 + x + 1$,  $x^7 + x + 1$,  $x^8 + x^4 + x^3 + x + 1$
$\FF_3$ 上	$x^2 + 1 $,  $x^3 + x^2 + 2 $,  $x^4 + x + 2 $,  $x^5 + x^4 + 2 $,  $x^6 + x + 2 $,  $x^7 + x^2 + 2 $,  $x^8 + x^2 + 2$
$\FF_5$ 上	$x^2 + 2 $,  $x^3 + x + 1 $,  $x^4 + 2 $,  $x^5 + x^2 + 2 $,  $x^6 + x + 2 $,  $x^7 + x + 1 $,  $x^8 + 2$
$\FF_7$ 上	$x^2 + 1 $,  $x^3 + 2 $,  $x^4 + x + 1 $,  $x^5 + x + 3 $,  $x^6 + 2 $,  $x^7 + x^2 + 4 $,  $x^8 + x + 3$
$\FF_{11}$ 上	$x^2 + 1 $,  $x^3 + x + 4 $,  $x^4 + x + 2 $,  $x^5 + 2 $,  $x^6 + x + 2 $,  $x^7 + x + 4 $,  $x^8 + x + 4$