剰余数を保持する数値クラス

a, p を整数として

v = a % p

p と v の情報を保持し、各演算子を使うためのクラスです。例えば、次の計算は

7754077^{16307003-1} \equiv 1 \pmod{16307003}

>>> a = ModNumber(16307003, 7754077)
>>> a
(7754077 % 16307003)
>>> a ** (a.divisor - 1)
(1 % 16307003)

となります。保持される値 (a.value) は "[0, a.divisor)" です。

クラスが __repr__() 関数で返す文字列は
　　"(value % divisor)"
形式です。

因みに「7754077 ** (16307003 - 1) % 16307003」の実行はやめましょう。

プログラム

modnum.py

from numbers import Integral


class ModNumber(Integral):
    def __init__(self, divisor, value=0):
        if divisor <= 0:
            raise ArithmeticError
        self.divisor = int(divisor)
        self.set_value(value)

    def get_divisor(self): return self.divisor
    def get_value(self): return self.value

    def set_value(self, value):
        divisor = self.divisor
        value = int(value) % divisor
        if value < 0:
            value += divisor
        self.value = value
        return self

    # override

    def __int__(self): return self.value
    def __repr__(self): return '(%d %% %d)' % (self.value, self.divisor)
    def __str__(self): return self.__repr__()

    def __eq__(self, other):
        if type(other) == ModNumber:
            if self.divisor != other.divisor:
                raise ArithmeticError
            value = other.value
        else:
            value = int(value)
        return (((self.value - value) % self.divisor) == 0)

    def __lt__(self, other): raise NotImplemented
    def __le__(self, other): raise NotImplemented

    def __neg__(self): return ModNumber(self.divisor, -self.value)
    def __pos__(self): return ModNumber(self.divisor, +self.value)
    def __invert__(self): raise NotImplemented

    def __add__(self, other): return ModNumber(self.divisor, self.value + other)
    def __sub__(self, other): return ModNumber(self.divisor, self.value - other)
    def __mul__(self, other): return ModNumber(self.divisor, self.value * other)
    def __pow__(self, other): return ModNumber(self.divisor, pow(self.value, other, self.divisor))

    def __divmod__(self, other):
        l, d = self.value, self.divisor
        return tuple(ModNumber(d, t) for t in (l / other, l % other))

    def __truediv__(self, other): return ModNumber(self.divisor, self.value / other)
    def __floordiv__(self, other): return ModNumber(self.divisor, self.value // other)
    def __mod__(self, other): return ModNumber(self.divisor, self.value % other)

    def __and__(self, other): return ModNumber(self.divisor, self.value & int(other))
    def __xor__(self, other): return ModNumber(self.divisor, self.value ^ int(other))
    def __or__(self, other): return ModNumber(self.divisor, self.value | int(other))

    def __lshift__(self, other): return self * ModNumber(self.divisor, 2)**other
    def __rshift__(self, other): return ModNumber(self.divisor, self.value >> int(other))

    def __radd__(self, other): return other + self.value
    def __rsub__(self, other): return other - self.value
    def __rmul__(self, other): return other * self.value
    def __rmod__(self, other): return other % self.value
    def __rtruediv__(self, other): return other % self.value
    def __rfloordiv__(self, other): return other // self.value
    def __rpow__(self, other): return other ** self.value

    def __rand__(self, other): return other & self.value
    def __rxor__(self, other): return other ^ self.value
    def __ror__(self, other): return other | self.value

    def __rlshift__(self, other): return other << self.value
    def __rrshift__(self, other): return other >> self.value

    def __iadd__(self, other): return self.set_value(self.value + int(other))
    def __isub__(self, other): return self.set_value(self.value - int(other))
    def __imul__(self, other): return self.set_value(self.value * other)
    def __itruediv__(self, other): return self.set_value(self.value // other)
    def __imod__(self, other): return self.set_value(self.value % other)

    def __abs__(self): return self
    def __ceil__(self): return self
    def __floor__(self): return self
    def __round__(self): return self
    def __trunc__(self): return self