有限体(ガロア体)計算をPythonで実装する

#有限体(ガロア体)とは
有限体とは簡単に言うと、

* 要素数が有限個
* 四則演算が定義可能

といった特徴を持つ代数系のことです。

以下がわかりやすく説明されていると思います。

>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),s*u+t*v=gcd(u,v)を満たすs,t

となるようなアルゴリズムのことです。

ここでは、入力を`u=p(素数),v=b`とするため、`gcd(p,b)=1`ということが明らか、
つまり
s*p + t*b=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スクリプトからこのクラスを利用できて便利。

内容に何かおかしな点があったら教えてください。