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

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

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

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

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{1}$	$\textbf{2}$	$\textbf{3}$	$\textbf{4}$
$\textbf{0}$	0	0	0	0
$\textbf{1}$	1	2	3	4
$\textbf{2}$	2	4	1	3
$\textbf{3}$	3	1	4	2
$\textbf{4}$	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スクリプトからこのクラスを利用できて便利。

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