Pythonで書く簡単な有限体理論

この記事について

筆者は大学で暗号理論，特に楕円曲線暗号に関する研究をしているので，暗号理論の土台となる代数学の基礎などについて簡単にまとめておきます．またサンプルコードには，Python3を使用しています．Pythonを使用するのは，intで多倍長整数を使用でき暗号計算を組む際に便利なためです．(C,GMP等と比較すると，計算速度はかなり遅くなるが...)
誤植やご指摘等ありましたら，コメントまたは編集リクエストまでお願いします．

群 (Group)

定義

集合 $G$ が二項演算 $\circ$ について以下を満たすとき，$\langle G, \circ \rangle$ を 群 (Group) と呼ぶ．

G1. (閉性)

$\forall a,b \in G$ について，$a \circ b \in G$ を満たす．

G2. (結合則)

$\forall a,b,c \in G$ について，$a \circ (b \circ c) = (a \circ b) \circ c$ を満たす．

G3. (単位元の存在)

$\forall a \in G$ について，$a \circ e = e \circ a = a$ となる単位元 $e \in G$ が存在する．

G4. (逆元の存在)

$\forall a \in G$ について，$a \circ a^{-1} = a^{-1} \circ a = e$ となる逆元 $a^{-1} \in G$ が存在する．

加えて，次を満たす場合は 可換群 (Commutative group) または アーベル群 (Abelian group) と呼ぶ．

AG5. (交換則)

$\forall a,b \in G$ について，$a \circ b = b \circ a$ を満たす．

一般に，加法 $+$ について群を成す場合は 加法群 (Additive group) ，乗法 $\cdot$ について群を成す場合は 乗法群 (Multiplicative group) と呼ぶ．
整数の集合 $\mathbb{Z}$, 有理数の集合 $\mathbb{Q}$, 実数の集合 $\mathbb{R}$, 複素数の集合 $\mathbb{C}$ は加法群を成し，有理数の集合 $\mathbb{Q}$, 実数の集合 $\mathbb{R}$, 複素数の集合 $\mathbb{C}$ は乗法群も成す．

e.g.

まずは，加法について．
$n$ 未満の正の整数を元とする有限集合 $\mathbb{Z_n} = \{0,1,2,...,n-1 \}$ において，法を $n$ とする加法(足して $n$ で割った余りをとる演算で，$+$ (mod $n$) と表記する)を考える．
$n = 6$ のとき，$\langle \mathbb{Z_6}, +$ (mod $6$)$\rangle$ の全通りの計算を次のサンプルコードで確認する．

test.py

n = 6   # order
for i in range(0, n):
  for j in range(0, n):
    print('{0} + {1} = {2} (mod {3}); '.format(i, j, (i + j) % n, n), end='')
  print()

実行結果

0 + 0 = 0 (mod 6); 0 + 1 = 1 (mod 6); 0 + 2 = 2 (mod 6); 0 + 3 = 3 (mod 6); 0 + 4 = 4 (mod 6); 0 + 5 = 5 (mod 6); 
1 + 0 = 1 (mod 6); 1 + 1 = 2 (mod 6); 1 + 2 = 3 (mod 6); 1 + 3 = 4 (mod 6); 1 + 4 = 5 (mod 6); 1 + 5 = 0 (mod 6); 
2 + 0 = 2 (mod 6); 2 + 1 = 3 (mod 6); 2 + 2 = 4 (mod 6); 2 + 3 = 5 (mod 6); 2 + 4 = 0 (mod 6); 2 + 5 = 1 (mod 6); 
3 + 0 = 3 (mod 6); 3 + 1 = 4 (mod 6); 3 + 2 = 5 (mod 6); 3 + 3 = 0 (mod 6); 3 + 4 = 1 (mod 6); 3 + 5 = 2 (mod 6); 
4 + 0 = 4 (mod 6); 4 + 1 = 5 (mod 6); 4 + 2 = 0 (mod 6); 4 + 3 = 1 (mod 6); 4 + 4 = 2 (mod 6); 4 + 5 = 3 (mod 6); 
5 + 0 = 5 (mod 6); 5 + 1 = 0 (mod 6); 5 + 2 = 1 (mod 6); 5 + 3 = 2 (mod 6); 5 + 4 = 3 (mod 6); 5 + 5 = 4 (mod 6);

以上より G1 - G4, AG5 を満たしていることが分かるため，$\langle \mathbb{Z_6}, +$ (mod $6$)$\rangle$ は可換群を成す．

次に，乗法について．
整数集合における乗法の単位元は $1$ であり，$0$ の逆元は存在しない．
したがって，$0$ を除く $n$ 未満の正の整数を元とする有限集合 $\mathbb{Z_n^*} = \{1,2,...,n-1 \}$ における，法を $n$ とする乗法について考える．
$n = 6$ のとき，$\langle \mathbb{Z_6^*}, $ $\cdot$ (mod $6$)$\rangle$ の全通りの計算を次のサンプルコードで確認する．

test1.py

n = 6   # order
for i in range(1, n):
  for j in range(1, n):
    print('{0} * {1} = {2} (mod {3}); '.format(i, j, (i * j) % n, n), end='')
  print()

実行結果

1 * 1 = 1 (mod 6); 1 * 2 = 2 (mod 6); 1 * 3 = 3 (mod 6); 1 * 4 = 4 (mod 6); 1 * 5 = 5 (mod 6); 
2 * 1 = 2 (mod 6); 2 * 2 = 4 (mod 6); 2 * 3 = 0 (mod 6); 2 * 4 = 2 (mod 6); 2 * 5 = 4 (mod 6); 
3 * 1 = 3 (mod 6); 3 * 2 = 0 (mod 6); 3 * 3 = 3 (mod 6); 3 * 4 = 0 (mod 6); 3 * 5 = 3 (mod 6); 
4 * 1 = 4 (mod 6); 4 * 2 = 2 (mod 6); 4 * 3 = 0 (mod 6); 4 * 4 = 4 (mod 6); 4 * 5 = 2 (mod 6); 
5 * 1 = 5 (mod 6); 5 * 2 = 4 (mod 6); 5 * 3 = 3 (mod 6); 5 * 4 = 2 (mod 6); 5 * 5 = 1 (mod 6); 

実行結果から，$0$ が出現していて G1. (閉性) を満たしておらず，$6$ と互いに素でない元 $2,3,4$ の逆元が存在せず G3. (逆元の存在) を満たしていないため，$\langle \mathbb{Z_6^*}, $ $\cdot$ (mod $6$)$\rangle$ は群でない．よって，$n$ が素数である場合のみ，乗法に対して可換群を成す．

体 (Field)

定義

(体を考える際には，環について言及しなくてはならないが，簡単化のために省略している．)

集合 $F$ が加法 $+$ と乗法 $\cdot$ について以下を満たすとき，$\langle F, +,$ $\cdot$ $\rangle$ を 体 (Field) と呼ぶ．

F1.

$\langle F, + \rangle$ が可換群を成す．

F2.

$F^* = F - \{0\}$ として，$\langle F^*, \cdot$ $\rangle$ が可換群を成す．

F3. (分配則)

$\forall a, b, c \in G$ について，$$a \cdot (b + c) = a \cdot b + a \cdot c$$ $$(a + b) \cdot c = a \cdot c + b \cdot c$$を満たす．

また，集合 $F$ が有限集合である体 $\langle F, +,$ $\cdot$ $\rangle$ を，有限体 (Finite field) または ガロア体 (Galois field) と呼ぶ．

e.g.

乗法群となる条件から $p$ を素数として，有限集合 $F_p = \{0,1,2,...,p-1 \}$ における，法を $p$ とする加法と乗法を考える．
$p = 7$ のとき，$\langle F_7, +,$ $\cdot$ (mod $7$)$\rangle$ の全通りの計算を次のサンプルコードで確認する．

test2.py

p = 7   # order
print('[Addition]')
for i in range(0, p):
  for j in range(0, p):
    print('{0} + {1} = {2} (mod {3}); '.format(i, j, (i + j) % p, p), end='')
  print()
print('\n[Multiplication]')
for i in range(1, p):
  for j in range(1, p):
    print('{0} * {1} = {2} (mod {3}); '.format(i, j, (i * j) % p, p), end='')
  print()

実行結果

[Addition]
0 + 0 = 0 (mod 7); 0 + 1 = 1 (mod 7); 0 + 2 = 2 (mod 7); 0 + 3 = 3 (mod 7); 0 + 4 = 4 (mod 7); 0 + 5 = 5 (mod 7); 0 + 6 = 6 (mod 7); 
1 + 0 = 1 (mod 7); 1 + 1 = 2 (mod 7); 1 + 2 = 3 (mod 7); 1 + 3 = 4 (mod 7); 1 + 4 = 5 (mod 7); 1 + 5 = 6 (mod 7); 1 + 6 = 0 (mod 7); 
2 + 0 = 2 (mod 7); 2 + 1 = 3 (mod 7); 2 + 2 = 4 (mod 7); 2 + 3 = 5 (mod 7); 2 + 4 = 6 (mod 7); 2 + 5 = 0 (mod 7); 2 + 6 = 1 (mod 7); 
3 + 0 = 3 (mod 7); 3 + 1 = 4 (mod 7); 3 + 2 = 5 (mod 7); 3 + 3 = 6 (mod 7); 3 + 4 = 0 (mod 7); 3 + 5 = 1 (mod 7); 3 + 6 = 2 (mod 7); 
4 + 0 = 4 (mod 7); 4 + 1 = 5 (mod 7); 4 + 2 = 6 (mod 7); 4 + 3 = 0 (mod 7); 4 + 4 = 1 (mod 7); 4 + 5 = 2 (mod 7); 4 + 6 = 3 (mod 7); 
5 + 0 = 5 (mod 7); 5 + 1 = 6 (mod 7); 5 + 2 = 0 (mod 7); 5 + 3 = 1 (mod 7); 5 + 4 = 2 (mod 7); 5 + 5 = 3 (mod 7); 5 + 6 = 4 (mod 7); 
6 + 0 = 6 (mod 7); 6 + 1 = 0 (mod 7); 6 + 2 = 1 (mod 7); 6 + 3 = 2 (mod 7); 6 + 4 = 3 (mod 7); 6 + 5 = 4 (mod 7); 6 + 6 = 5 (mod 7); 

[Multiplication]
1 * 1 = 1 (mod 7); 1 * 2 = 2 (mod 7); 1 * 3 = 3 (mod 7); 1 * 4 = 4 (mod 7); 1 * 5 = 5 (mod 7); 1 * 6 = 6 (mod 7); 
2 * 1 = 2 (mod 7); 2 * 2 = 4 (mod 7); 2 * 3 = 6 (mod 7); 2 * 4 = 1 (mod 7); 2 * 5 = 3 (mod 7); 2 * 6 = 5 (mod 7); 
3 * 1 = 3 (mod 7); 3 * 2 = 6 (mod 7); 3 * 3 = 2 (mod 7); 3 * 4 = 5 (mod 7); 3 * 5 = 1 (mod 7); 3 * 6 = 4 (mod 7); 
4 * 1 = 4 (mod 7); 4 * 2 = 1 (mod 7); 4 * 3 = 5 (mod 7); 4 * 4 = 2 (mod 7); 4 * 5 = 6 (mod 7); 4 * 6 = 3 (mod 7); 
5 * 1 = 5 (mod 7); 5 * 2 = 3 (mod 7); 5 * 3 = 1 (mod 7); 5 * 4 = 6 (mod 7); 5 * 5 = 4 (mod 7); 5 * 6 = 2 (mod 7); 
6 * 1 = 6 (mod 7); 6 * 2 = 5 (mod 7); 6 * 3 = 4 (mod 7); 6 * 4 = 3 (mod 7); 6 * 5 = 2 (mod 7); 6 * 6 = 1 (mod 7); 

以上より F1 - F3 を満たしていることが分かるため，$\langle F_7, +,$ $\cdot$ (mod $7$)$\rangle$ は有限体を成す．