Pythonで整数剰余環

これは、代数構造を実装しようとして四苦八苦して生み出された謎の記録である。

複雑なプログラミング、大規模な開発を会社から指示される前に自分でやってみたいと思い、題材として代数を選んだ。まずは一番簡単そうな有理整数環の剰余環を実装しようと思い立った。それが思いのほか大変であった。大変だったのはイデアルを固定したまま整数剰余環の元を生成するところである。

最初はクラス内部にクラス（継承ではない）を作成するのはどうかと思い立ったが一向に上手くいかず、仕方なくクラスを返す函数を作った。部分函数を返すfunctools.partialにクラスを突っ込むと言う不思議な方法を取っている。使い方はdoctestを見れば察しがつくと思う。

なお、以下のサイトを大いに参考にしている。こちらもクラスを返す函数を作成している。

import functools

def IntegerMod(p):
    """
    整数剰余環

    >>> mod7 = IntegerMod(7)
    >>> mod7(5)
    5 (mod 7)
    >>> mod7(3) * mod7(5)
    1 (mod 7)
    >>> mod7(5) + mod7(4)
    2 (mod 7)
    >>> mod7(2) - mod7(3)
    6 (mod 7)
    >>> mod7(0) == mod7(3) + mod7(4)
    True
    >>> mod7(0) != (mod7(3) + mod7(6))
    True
    >>> mod7(1) / mod7(3)
    5 (mod 7)
    >>> mod7(3) * mod7(1)
    3 (mod 7)
    >>> str(mod7(2))
    '2'
    >>> int(mod7(4))
    4
    """
    @functools.lru_cache(maxsize=128)
    class IntegerModElement:
        """
        整数剰余環の元
        """
        def __init__(self, n, p):
            self.n = n % p
            self.p = p
            
        def __eq__(self, other):
            return (self.n == other.n) and (self.p == other.p)
        
        def __ne__(self, other):
            return not (self.n != other.n) or not (self.p != other.p)
        
        def __neg__(self):
            return IntegerModElement(self.p - self.n, self.p)

        def __add__(self, other):
            assert self.p == other.p
            return IntegerModElement(self.n + other.n, self.p)

        def __sub__(self, other):
            assert self.p == other.p
            return IntegerModElement((self.n - other.n) , self.p)

        def __mul__(self, other):
            assert self.p == other.p
            return IntegerModElement(self.n * other.n, self.p)

        def __truediv__(self, other):
            assert self.p == other.p
            return self.__mul__(other.inverse())

        def __repr__(self):
            return "{0} (mod {1})".format(self.n, self.p)

        def __str__(self):
            return str(self.n)

        def __int__(self):
            return int(self.n)

        def __egcd__(self, a, b):
            x, y, u, v = 0, 1, 1, 0
            while a != 0:
                q, r = (b // a), (b % a)
                m, n = x - (u * q), y - (v * q)
                b, a, x, y, u ,v = a ,r, u, v, m, n
            gcd = b
            return gcd, x, y
            
        def inverse(self):
            gcd , x, y = self.__egcd__(self.n, self.p)
            if gcd == 1:
                return IntegerModElement(x , self.p)
            else:
                raise RuntimeError("Don't exist modulo inverse value...")

    f = functools.partial(IntegerModElement, p=p)
    
    return f

if __name__ == "__main__":
    import doctest
    doctest.testmod()

最初の目標は有限体である。有限体の素体はこれでよいが、拡大体も当然扱いたい。