#有限体(ガロア体)とは
有限体とは簡単に言うと、
- 要素数が有限個
- 四則演算が定義可能
といった特徴を持つ代数系のことです。
以下がわかりやすく説明されていると思います。
http://funini.com/kei/math/crc_math.shtml kei@sodan「ガロア体と拡大体」
#実装
目標は、任意の素数pに対して、p個{0,1,2,...,p-1}の要素の加減乗除が定義されたgfクラスを実装することとします。
###加算
def gf_add(p,a,b):
return (a+b)%p
加算はa,bの計算結果をpで割った余りを返すだけです。
###減算
def gf_sub(p,a,b):
if (a-b)<0:
return (a-b+p)%p
else:
return (a-b)%p
減算は、a-bの結果が負の値にならないように注意して計算します。
###乗算
def gf_mul(p,a,b):
return (a*b)%p
こちらも加算と同様ですね。
###除算
こちらは少し工夫が必要です。
ある有限体$\mathbb{F}_{5}$において除算、たとえば1/3を定義したい時、
$$\frac{1}{3}\ mod\ 5\ = 1\ * \alpha\ mod\ 5\ = 1$$
を満たすような$\alpha\in\mathbb{F}_{5}$
($\alpha$は3の逆数)を探せば良いわけですが、先の乗算の定義より、以下のような演算表をつくると、
| * | $\textbf{0}$ | $\textbf{1}$ | $\textbf{2}$ | $\textbf{3}$ | $\textbf{4}$ |
|---|---|---|---|---|---|
| $\textbf{0}$ | 0 | 0 | 0 | 0 | 0 |
| $\textbf{1}$ | 0 | 1 | 2 | 3 | 4 |
| $\textbf{2}$ | 0 | 2 | 4 | 1 | 3 |
| $\textbf{3}$ | 0 | 3 | 1 | 4 | 2 |
| $\textbf{4}$ | 0 | 4 | 3 | 2 | 1 |
任意の元の乗算において(0を除く)積が1となるような元が一意に定まることがわかります。
ちなみに上の例では$\alpha\ = 2$(演算表より3の逆数が2だとわかるため)となります。
このプロセスをコンピュータ上で実装するのは非常に骨が折れるため、既存のテクニックを利用します。
それが拡張ユークリッドの互除法です。
細かい説明は省きますが、拡張ユークリッド法とは、
入力 u,v(u>v)
出力 gcd(u,v),su+tv=gcd(u,v)を満たすs,t
となるようなアルゴリズムのことです。
ここでは、入力をu=p(素数),v=bとするため、gcd(p,b)=1ということが明らか、
つまり
sp + tb=1 mod p $\Rightarrow$ t*b = 1 mod p
となるようなtが出力として得られます。
tは負の値となることがありますが、その場合、正の値になるまでpの倍数を加えます。
そして、このtという値が、先ほど乗算の演算表を用いて求めた逆数になります。
tは、bと掛けて1になる数なのですから当然bの逆数だということになりますよね。
以下、拡張ユークリッド法と除算のプログラムになります。
def ex_euclid(x, y):
c0, c1 = x, y
a0, a1 = 1, 0
b0, b1 = 0, 1
while c1 != 0:
m = c0 % c1
q = c0 // c1
c0, c1 = c1, m
a0, a1 = a1, (a0 - q * a1)
b0, b1 = b1, (b0 - q * b1)
return b0
def gf_div(p,a,b):
t=gf.ex_euclid(p,b)
if t<0:
i=1
while (t+i*p)%p<0:
i+=1
t=(t+i*p)%p
return (a*t)%p
#クラスとして実装
ここまでで、関数としての実装はできたわけなのですが、これだと例えば$\mathbb{F}_{5}$において、$2*3+3\ /\ 4$みたいな計算をしたい時、
gf_add(gf_mul(5,2,3),gf_div(5,3,4))
みたいな書き方をしなきゃならんのでみにくい。
そこで、Pythonのもつ演算子オーバーロードの機能を使って、スマートに実装します。
以下がそのコード
class gf():
space=5
def set_space(a):
gf.space=a
def __init__(self,x):
self.value=x
def __add__(self,y):
if type(y) is int:
y=gf(y)
return(gf.gf_add(gf.space,self.value,y.value))
def __sub__(self,y):
if type(y) is int:
y=gf(y)
return(gf.gf_sub(gf.space,self.value,y.value))
def __mul__(self,y):
if type(y) is int:
y=gf(y)
return(gf.gf_mul(gf.space,self.value,y.value))
def __truediv__(self,y):
if type(y) is int:
y=gf(y)
return(gf.gf_div(gf.space,self.value,y.value))
def __radd__(self,y):
if type(y) is int:
y=gf(y)
return(gf.gf_add(gf.space,self.value,y.value))
def __rsub__(self,y):
if type(y) is int:
y=gf(y)
return(gf.gf_sub(gf.space,self.value,y.value))
def __rmul__(self,y):
if type(y) is int:
y=gf(y)
return(gf.gf_mul(gf.space,self.value,y.value))
def __rtruediv__(self,y):
if type(y) is int:
y=gf(y)
return(gf.gf_div(gf.space,self.value,y.value))
※書いていませんが、上で記したgf_◯◯◯と言う名前の関数についても、このクラス内に宣言します。
これによりa.value=2,b.value=3,c.value=4のとき$2*3+3\ /\ 4$という計算をa*b+b/cと直感的にかけます。
##プログラムの説明
gf.space : $\mathbb{F}_{p}$のpにあたる数(defaultは5)
setterは用意したけれどgf.space=11といった感じで設定できます。
def __init__: : コンストラクタ
gfオブジェクト生成時にself.valueに実際の値を格納する。
ex ) a=gf(3)→aに3を代入したい時
その他の特殊メソッド : 演算子をオーバーロードしている部分です。
ほとんどは、対応するgf_◯◯◯関数を呼び出しているだけですが、ifでの分岐がポイントです。ifの部分がなくても良いのですが、その場合即値での演算が少し手間になります。
どういうことかというと、例えば、3が格納されているgfオブジェクトaと、即値4との加算をしたいとき、ifの部分がないとa+gf(4)とかく必要がありますが、上記のようにすれば自動的にintオブジェクトがgfオブジェクトにキャストされるのでa+4と書くことができます。
種々の特殊メソッドについては以下を参考にしました。
https://pknight.hatenablog.com/entry/20170321/1490061276 (void*)Pないと「Pythonでの演算子のオーバーロード」
##おわりに
上記の内容を記したファイルを”gflib.py”という名前で保存すれば、”from gflib import gf”と書くことで任意のpythonスクリプトからこのクラスを利用できて便利。
内容に何かおかしな点があったら教えてください。