有限体   ― 塩田研一覚書帳 ―

 有限個の要素からなるを有限体と呼びます。 加減乗除の四則演算ができて、しかも要素が有限個しかないので、 計算機上で扱うには「もってこい」の代物です。 どうやって作るのか、どんな使い方ができるのか、といったことをお話します。

標数と位数

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

 素数 p と自然数 n を与えると、
  • 位数 pn の有限体が必ず存在する
  • 位数 pn の有限体はお互いに全て同型である
ことが知られています。 そこで位数 pn の有限体を Fpn あるいは GF(pn) と表します ( GF は Galois field の頭文字 )。 有限体が Fq と表記されているときは q は必ず素数べきを表しています。

位数という用語はよく使うので混乱しないようにしましょう。
  • 群には、群の位数と、元の位数の2通りがあります。 群の位数は、体と同じく、要素の個数を表しますが、 元 x の位数とは
    xn = 単位元 e
    となる最小の自然数 n のことです。 元 x の位数が n ならば、x の生成する巡回部分群
    < x > = { e, x, x2, ... }
    の群位数も n になることから同じ用語を使っているようです。
  • 環の位数は、体と同じく、要素の個数を表します。
  • グラフ理論では頂点の個数を指します。

F4

 4個の要素を持つ有限体 ( 4元体 ) F4 を作ってみましょう。
  1. 4 = 22 ですので F4 の標数は 2 でなければなりません。 つまり、mod 2 の計算がベースにあります。
  2. 素体 F2 には属さない F4 の元 α をひとつ取りましょう。
  3. 1 と α が F4F2 上の基底になりますので、 F4 の4つの元は 0, 1, α, α + 1 です。
  4. α2 も F4 の元ですから 0, 1, α, α + 1 のいずれかに一致しますが、 体は零因子を持たないことから
    α2 = α + 1
    であることがわかります。実際、
    • もし α2 = 0 なら α ≠ 0 に矛盾
    • もし α2 = 1 なら α = ±1 = 1 となり α ≠ 1 に矛盾
    • もし α2 = α なら α = 0 or 1 となり 「 α ≠ 0 and α ≠ 1 」 に矛盾
  5. という訳で、F4 とは、mod 2 の上で α2 = α + 1 を満たす数を考えることになります。 少し計算例を書いておきましょう:
    • (α + 1)2 = α2 + 2 α + 1 = α2 + 1 = (α + 1) + 1 = α
    • α3 = α × α2 = α (α + 1) = α2 + α = (α + 1) + α = 1
    mod 2 は係数には使えますが、べき指数に使ってはいけません、お間違えなく。

16人麻雀

 16人で麻雀大会を開こうと思います。 全ての人が自分以外の15人と丁度1回ずつ対戦するような組合せ表を F4 を利用して作ってみましょう。 上のように F4 = F2(α) ( ただし α2 = α + 1 ) と表し、 簡単のため β = α + 1 と書くことにします。
  1. F4 上の xy-平面 P を考えます。
  2. P にある16個の点を16人の雀士に対応させます。
  3. P 上の直線たちには次のような性質があります:
    • 各直線上には点が4個ずつ乗っている
    • 平行な直線は4本ずつある
    • 方向ベクトルは5通りある
    • 2つの点を通る直線は1本だけある
    具体的には
    • 方向ベクトル ( 0, 1 ) :
      直線 y = 0 : ( 0, 0 ), ( 1, 0 ), ( α, 0 ), ( β, 0 )
      直線 y = 1 : ( 0, 1 ), ( 1, 1 ), ( α, 1 ), ( β, 1 )
      直線 y = α : ( 0, α ), ( 1, α ), ( α, α ), ( β, α )
      直線 y = β : ( 0, β ), ( 1, β ), ( α, β ), ( β, β )
    • 方向ベクトル ( 1, 0 ) :
      直線 x = 0 : ( 0, 0 ), ( 0, 1 ), ( 0, α ), ( 0, β )
      直線 x = 1 : ( 1, 0 ), ( 1, 1 ), ( 1, α ), ( 1, β )
      直線 x = α : ( α, 0 ), ( α, 1 ), ( α, α ), ( α, β )
      直線 x = β : ( β, 0 ), ( β, 1 ), ( β, α ), ( β, β )
    • 方向ベクトル ( 1, 1 ) :
      直線 x + y = 0 : ( 0, 0 ), ( 1, 1 ), ( α, α ), ( β, β )
      直線 x + y = 1 : ( 0, 1 ), ( 1, 0 ), ( α, β ), ( β, α )
      直線 x + y = α : ( 0, α ), ( 1, β ), ( α, 0 ), ( β, 1 )
      直線 x + y = β : ( 0, β ), ( 1, α ), ( α, 1 ), ( β, 0 )
    • 方向ベクトル ( 1, α ) :
      直線 x + α y = 0 : ( 0, 0 ), ( 1, β ), ( α, 1 ), ( β, α )
      直線 x + α y = 1 : ( 0, β ), ( 1, 0 ), ( α, α ), ( β, 1 )
      直線 x + α y = α : ( 0, 1 ), ( 1, α ), ( α, 0 ), ( β, β )
      直線 x + α y = β : ( 0, α ), ( 1, 1 ), ( α, β ), ( β, 0 )
    • 方向ベクトル ( 1, β ) :
      直線 x + β y = 0 : ( 0, 0 ), ( 1, α ), ( α, β ), ( β, 1 )
      直線 x + β y = 1 : ( 0, α ), ( 1, 0 ), ( α, 1 ), ( β, β )
      直線 x + β y = α : ( 0, β ), ( 1, 1 ), ( α, 0 ), ( β, α )
      直線 x + β y = β : ( 0, 1 ), ( 1, β ), ( α, α ), ( β, 0 )
  4. そこで、方向ベクトルを共有する4本の直線を雀卓、5つの方向ベクトルを時間帯と考えて対戦表を組みます。 α, β を 2, 3 に置き換えて4進数と思って雀士の番号を書けば以下の通りです:
    卓1卓2卓3卓4
    1回戦 0, 4, 8, 12 1, 5, 9, 13 2, 6, 10, 14 3, 7, 11, 15
    2回戦 0, 1, 2, 3 4, 5, 6, 7 8, 9, 10, 11 12, 13, 14, 15
    3回戦 0, 5, 10, 15 1, 4, 11, 14 2, 7, 8, 13 3, 6, 9, 12
    4回戦 0, 7, 9, 14 3, 4, 10, 13 1, 6, 8, 15 2, 5, 11, 12
    5回戦 0, 6, 11, 13 2, 4, 9, 15 3, 5, 8, 14 1, 7, 10, 12
このように有限体上の幾何学(有限幾何)を考えると、対称性を持った組合せが簡単に作れたりします。

有限体上の多項式の微分

 有限体には距離の概念がありませんので極限を用いることはできないのですが、
(xn) ' = n xn-1
を定義として採用すれば、実数上と同じ微分の公式たちが使え、
定理A α が多項式 f(x) の重根である ⇔ f(α) = f '(α) = 0
といった定理も成り立ちます。

有限体の乗法群

 有限体 F の 0 以外の要素からなる集合 F× = { x ∈ F | x ≠ 0 } は乗法に関する群となりますので、 ラグランジュの定理より
定理B 有限体 Fq の 0 以外の任意の元は xq-1 = 1 を満たす
系 有限体 Fq の任意の元は xq - x の根である
ことが言えます。 更に著しい性質は
定理C 有限体 F の乗法群 F× は巡回群である
ことです。(定理A、定理Bと、元の位数の議論を用いて証明している本が多いです。) その巡回群としての生成元を F の原始根と呼びます。 F が素体 Fp であるときには法 p ( mod p ) の原始根、とも呼びます。 ( 「 1 の原始 n 乗根 」 というのは、全く無関係という訳ではありませんが、別物です。 ) 少し例を挙げておくと
  • F3 の原始根 : 2
  • F5 の原始根 : 2, 3
  • F7 の原始根 : 3, 5
  • F11 の原始根 : 2, 6, 7, 8
  • F4 の原始根 : α, β
 暗号理論では、この「巡回群である」という性質を利用して Diffie-Hellman の鍵交換システムや ElGamal 暗号が 設計されます。

有限体 Fpn の構成法

 有限体 Fpn を構成するには Fp 上の n 次既約多項式 f(x) を用います ( 次項参照 ) 。 理論的には f(x) の根 α を Fp に付加した体 Fp(α) が Fpn になりますが、 体の項で述べたように、 Fp 上の多項式環で mod f(x) の計算をすることが Fp(α) を考えることになります。

 繰り返しますが、剰余環 Fp[x] / ( f(x) ) の計算は次のように行います:
  • 元は Fp 係数の n-1 次以下の多項式で表す
  • 加法・減法は多項式の和・差の係数を mod p で計算する
  • 乗法は多項式の積を mod p と mod f(x) で計算する
  • 0 でない元 g(x) の逆数は次のように求める: Fp 係数の多項式として f(x) と g(x) を入力とする拡張ユークリッドアルゴリズムを実行して
    f(x) u(x) + g(x) v(x) = 1
    となる多項式 u(x), v(x) を求めれば、 Fpn の元として v(x) = g(x)-1 となる
  • 除法は逆数が計算できれば明らか

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

Fp 上の n 次既約多項式の求め方

 試し割り算法による素数判定と同じ理屈で、 Fp 上の n 次多項式 f(x) は、n / 2 次以下の因子を持たなければ既約になります。
 Fp 上の m 次既約多項式の根は Fp 上の m 次拡大を生成し、 定理Bからそれは xpm-1 - 1 の根になります。 0 も合わせて考えれば
定理D Fp 上の m 次既約多項式は全て xpm - x の因子である
であることがわかります。 これを利用して Fp 上の 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) は xpm を f(x) で割った剰余を格納する変数で、 p が大きいときには反復2乗法を用いて計算します:
入力: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 は多項式のユークリッドアルゴリズムで求めます。 xpm - x と f(x) が互いに素でなければ f(x) は m 次因子を持つので既約でなくなり、 m ≦ (n / 2) の範囲で m 次因子を持たなければ既約と判定する、という仕組みです。
 p が 2 でなければ、2次既約多項式はこんな面倒なことをしなくても、mod p の平方非剰余 a をひとつみつけて x2-a でOKです。 また3次既約多項式についても、 p-1 が 3 の倍数ならば、3乗数でない a をひとつみつけて x3-a でOKです。 3乗数でないことは a(p-1)/3 ≠ 1 という式で判定できます。

既約多項式の例

F2 x2 + x + 1,  x3 + x + 1,  x4 + x + 1,  x5 + x2 + 1, 
x6 + x + 1,  x7 + x + 1,  x8 + x4 + x3 + x + 1
F3 x2 + 1 ,  x3 + x2 + 2 ,  x4 + x + 2 ,  x5 + x4 + 2 , 
x6 + x + 2 ,  x7 + x2 + 2 ,  x8 + x2 + 2
F5 x2 + 2 ,  x3 + x + 1 ,  x4 + 2 ,  x5 + x2 + 2 , 
x6 + x + 2 ,  x7 + x + 1 ,  x8 + 2
F7 x2 + 1 ,  x3 + 2 ,  x4 + x + 1 ,  x5 + x + 3 , 
x6 + 2 ,  x7 + x2 + 4 ,  x8 + x + 3
F11 x2 + 1 ,  x3 + x + 4 ,  x4 + x + 2 ,  x5 + 2 , 
x6 + x + 2 ,  x7 + x + 4 ,  x8 + x + 4

フロベニウス自己同型

 執筆中

戻る