field_extension.py

#!/usr/bin/env python3

from typing import TypeVar, Generic, Any, List
from abc import ABCMeta, abstractmethod
from itertools import dropwhile, zip_longest


def euclid_gcd(a, b):
    x = a.zero()
    y = a.identity()
    x_1 = a.identity()
    y_1 = a.zero()
    cnt = 0
    while True:
        c = a % b
        if c == c.zero():
            break
        x_2 = x_1
        y_2 = y_1
        x_1 = x
        y_1 = y
        x = x_2 - x_1 * (a // b)
        y = y_2 - y_1 * (a // b)
        a = b
        b = c
        cnt += 1
    return (x, y, b)


def mul_poly(a, b):
    c = [a[0].zero() for i in range(len(a) + len(b) - 1)]
    for i, aa in enumerate(reversed(a)):
        for j, bb in enumerate(reversed(b)):
            c[i + j] += aa * bb
    return list(reversed(c))


def div_poly(a, b):
    q = [a[0].zero() for i in range(max(len(a) - len(b) + 1, 0))]
    r = a[:]
    for i in range(len(q)):
        q[i] = r[i] / b[0]
        for k in range(len(b)):
            r[i + k] -= b[k] * q[i]
    return ([a[0].zero()] + q, r)


MonoidType = TypeVar('MonoidType', bound="Monoid")

class Monoid(Generic[MonoidType], metaclass = ABCMeta):
    @abstractmethod
    def __mul__(self: MonoidType, x: MonoidType) -> MonoidType:
        pass

    @abstractmethod
    def identity(self: MonoidType) -> MonoidType:
        pass

    @abstractmethod
    def __eq__(self: Any, x: Any) -> bool:
        pass

    def testAssociativity(self: MonoidType, a: MonoidType, b: MonoidType) -> bool:
        return (self * a) * b == self * (a * b)

    def testIdentity(self: MonoidType) -> bool:
        return self * self.identity() == self


GroupType = TypeVar('GroupType', bound="Group")

class Group(Generic[GroupType], metaclass = ABCMeta):
    @abstractmethod
    def __mul__(self: GroupType, x: GroupType) -> GroupType:
        pass

    @abstractmethod
    def identity(self: GroupType) -> GroupType:
        pass

    @abstractmethod
    def inverse(self: GroupType) -> GroupType:
        pass

    def __truediv__(self: GroupType, x: GroupType) -> GroupType:
        return self * x.inverse()

    @abstractmethod
    def __eq__(self: Any, x: Any) -> bool:
        pass

    def testAssociativity(self: GroupType, a: GroupType, b: GroupType) -> bool:
        return (self * a) * b == self * (a * b)

    def testIdentity(self: GroupType) -> bool:
        return self * self.identity() == self

    def testInverse(self: GroupType) -> bool:
        return self * self.inverse() == self.identity()


AdditiveGroupType = TypeVar('AdditiveGroupType', bound="AdditiveGroup")

class AdditiveGroup(Generic[AdditiveGroupType], metaclass = ABCMeta):
    @abstractmethod
    def __add__(self: AdditiveGroupType, x: AdditiveGroupType) -> AdditiveGroupType:
        pass

    @abstractmethod
    def zero(self: AdditiveGroupType) -> AdditiveGroupType:
        pass

    @abstractmethod
    def __neg__(self: AdditiveGroupType) -> AdditiveGroupType:
        pass

    def __sub__(self: AdditiveGroupType, x: AdditiveGroupType) -> AdditiveGroupType:
        return self + (-x)

    @abstractmethod
    def __eq__(self: Any, x: Any) -> bool:
        pass

    def testAdditiveAssociativity(self: AdditiveGroupType, a: AdditiveGroupType, b: AdditiveGroupType) -> bool:
        return (self + a) + b == self + (a + b)

    def testZero(self: AdditiveGroupType) -> bool:
        return self + self.zero() == self

    def testNegative(self: AdditiveGroupType) -> bool:
        return self + (-self) == self.zero()

    def testAbelian(self: AdditiveGroupType, a: AdditiveGroupType) -> bool:
        return self + a == a + self


RingType = TypeVar('RingType', bound="Ring")

class Ring(Monoid, AdditiveGroup, Generic[RingType]):
    def testDistributive(self: RingType, a: RingType, b: RingType) -> bool:
        return self * (a + b) == self * a + self * b


FieldType = TypeVar('FieldType', bound="Field")

class Field(Group, Ring, Generic[FieldType]):
    def testInverse(self: FieldType) -> bool:
        if self * self.identity() == super().zero():
            return super().testInverse()
        else:
            return True


EuclidianRingType = TypeVar('EuclidianRingType', bound="EuclidianRing")

class EuclidianRing(Ring, Generic[EuclidianRingType]):
    @abstractmethod
    def __floordiv__(self: EuclidianRingType, x: EuclidianRingType) -> EuclidianRingType:
        pass

    @abstractmethod
    def __mod__(self: EuclidianRingType, x: EuclidianRingType) -> EuclidianRingType:
        pass


class Integer(EuclidianRing["Integer"]):
    def __init__(self: "Integer", v: int) -> None:
        self.v = v

    def __repr__(self: "Integer") -> str:
        return str(self.v)

    def __floordiv__(self: "Integer", x: "Integer") -> "Integer":
        return Integer(self.v // x.v)

    def __mod__(self: "Integer", x: "Integer") -> "Integer":
        return Integer(self.v % x.v)

    def __mul__(self: "Integer", x: "Integer") -> "Integer":
        return Integer(self.v * x.v)

    def __add__(self: "Integer", x: "Integer") -> "Integer":
        return Integer(self.v + x.v)

    def __neg__(self: "Integer") -> "Integer":
        return Integer(-self.v)

    def __eq__(self, x: Any) -> bool:
        if not isinstance(x, Integer):
            return NotImplemented
        return self.v == x.v

    def identity(self: "Integer") -> "Integer":
        return Integer(1)

    def zero(self: "Integer") -> "Integer":
        return Integer(0)

Z = Integer


class Rational(Field["Rational"]):
    def __init__(self: "Rational", a: Integer, b: Integer) -> None:
        _, _, p = euclid_gcd(a, b)
        self.a = a // p
        self.b = b // p

    def __repr__(self):
        if self.b == self.b.identity():
            return "%s" % self.a
        return "%s/%s" % (self.a, self.b)

    def __mul__(self: "Rational", x: "Rational") -> "Rational":
        return Rational(self.a * x.a, self.b * x.b)

    def __add__(self: "Rational", x: "Rational") -> "Rational":
        return Rational(self.a * x.b + x.a * self.b, self.b * x.b)

    def __eq__(self: Any, x: Any) -> bool:
        if not isinstance(x, Rational):
            return NotImplemented
        return self.a == x.a and self.b == x.b

    def __neg__(self: "Rational") -> "Rational":
        return Rational(-self.a, self.b)

    def identity(self: "Rational") -> "Rational":
        return Rational(self.a.identity(), self.a.identity())

    def inverse(self: "Rational") -> "Rational":
        return Rational(self.b, self.a)

    def zero(self: "Rational") -> "Rational":
        return Rational(self.a.zero(), self.a.identity())

Q = Rational


class ModRing(Ring["ModRing"]):
    def __init__(self: "ModRing", a: "Integer", n: "Integer") -> None:
        self.a = a % n
        self.n = n

    def __repr__(self: "ModRing") -> str:
        return "%s (mod %s)" % (str(self.a), str(self.n))

    def __floordiv__(self: "ModRing", x: "ModRing") -> "ModRing":
        if self.n != x.n:
            return NotImplemented
        return ModRing(self.a // x.a, self.n)

    def __mod__(self: "ModRing", x: "ModRing") -> "ModRing":
        if self.n != x.n:
            return NotImplemented
        return ModRing(self.a % x.a, self.n)

    def __mul__(self: "ModRing", x: "ModRing") -> "ModRing":
        if self.n != x.n:
            return NotImplemented
        return ModRing(self.a * x.a, self.n)

    def __add__(self: "ModRing", x: "ModRing") -> "ModRing":
        if self.n != x.n:
            return NotImplemented
        return ModRing(self.a + x.a, self.n)

    def __neg__(self: "ModRing") -> "ModRing":
        return ModRing(-self.a, self.n)

    def __eq__(self, x: Any) -> bool:
        if not isinstance(x, ModRing) or self.n != x.n:
            return NotImplemented
        return self.a == x.a

    def identity(self: "ModRing") -> "ModRing":
        return ModRing(self.a.identity(), self.n)

    def zero(self: "ModRing") -> "ModRing":
        return ModRing(self.a.zero(), self.n)


class FiniteField(Field["FiniteField"]):
    def __init__(self: "FiniteField", a: "Integer", n: "Integer") -> None:
        self.a = a % n
        self.n = n

    def __repr__(self: "FiniteField") -> str:
        return "%s (mod %s)" % (str(self.a), str(self.n))

    def __mul__(self: "FiniteField", x: "FiniteField") -> "FiniteField":
        if self.n != x.n:
            return NotImplemented
        return FiniteField(self.a * x.a, self.n)

    def __add__(self: "FiniteField", x: "FiniteField") -> "FiniteField":
        if self.n != x.n:
            return NotImplemented
        return FiniteField(self.a + x.a, self.n)

    def __neg__(self: "FiniteField") -> "FiniteField":
        return FiniteField(-self.a, self.n)

    def __eq__(self, x: Any) -> bool:
        if not isinstance(x, FiniteField) or self.n != x.n:
            return NotImplemented
        return self.a == x.a

    def identity(self: "FiniteField") -> "FiniteField":
        return FiniteField(self.a.identity(), self.n)

    def zero(self: "FiniteField") -> "FiniteField":
        return FiniteField(self.a.zero(), self.n)

    def inverse(self: "FiniteField") -> "FiniteField":
        y, _, p = euclid_gcd(self.a, self.n)
        if p == -p.identity():
            y = -y
        elif p != p.identity():
            raise Exception("Not finite field")
        return FiniteField(y, self.n)


class Polynominal(EuclidianRing["Polynominal"]):
    def __init__(self: "Polynominal", coeffs: List[Rational]) -> None:
        self.coeffs = list(dropwhile(lambda x: x == x.zero(), coeffs))
        if not self.coeffs:
            self.coeffs = [coeffs[0].zero()]
        self.n = len(self.coeffs)

    def __repr__(self: "Polynominal") -> str:
        return "(" + " + ".join("%s x ^ %d" % (repr(c), len(self.coeffs) - i - 1) for i, c in enumerate(self.coeffs)) + ")"

    def __floordiv__(self: "Polynominal", x: "Polynominal") -> "Polynominal":
        q, r = div_poly(self.coeffs, x.coeffs)
        return Polynominal(q)

    def __mod__(self: "Polynominal", x: "Polynominal") -> "Polynominal":
        q, r = div_poly(self.coeffs, x.coeffs)
        return Polynominal(r)

    def __mul__(self: "Polynominal", x: "Polynominal") -> "Polynominal":
        y = mul_poly(self.coeffs, x.coeffs)
        return Polynominal(y)

    def __add__(self: "Polynominal", x: "Polynominal") -> "Polynominal":
        y = list(a + b for a, b in zip_longest(reversed(self.coeffs), reversed(x.coeffs), fillvalue=self.coeffs[0].zero()))
        y.reverse()
        return Polynominal(y)

    def __neg__(self: "Polynominal") -> "Polynominal":
        return Polynominal([-a for a in self.coeffs])

    def __eq__(self, x: Any) -> bool:
        if not isinstance(x, Polynominal):
            return NotImplemented
        return self.coeffs == x.coeffs

    def identity(self: "Polynominal") -> "Polynominal":
        return Polynominal([self.coeffs[0].identity()])

    def zero(self: "Polynominal") -> "Polynominal":
        return Polynominal([self.coeffs[0].zero()])


class PolynominalModRing(Ring["PolynominalModRing"]):
    def __init__(self: "PolynominalModRing", a: "Polynominal", n: "Polynominal") -> None:
        self.a = a % n
        self.n = n

    def __repr__(self: "PolynominalModRing") -> str:
        return "%s (mod %s)" % (str(self.a), str(self.n))

    def __floordiv__(self: "PolynominalModRing", x: "PolynominalModRing") -> "PolynominalModRing":
        if self.n != x.n:
            return NotImplemented
        return PolynominalModRing(self.a // x.a, self.n)

    def __mod__(self: "PolynominalModRing", x: "PolynominalModRing") -> "PolynominalModRing":
        if self.n != x.n:
            return NotImplemented
        return PolynominalModRing(self.a % x.a, self.n)

    def __mul__(self: "PolynominalModRing", x: "PolynominalModRing") -> "PolynominalModRing":
        if self.n != x.n:
            return NotImplemented
        return PolynominalModRing(self.a * x.a, self.n)

    def __add__(self: "PolynominalModRing", x: "PolynominalModRing") -> "PolynominalModRing":
        if self.n != x.n:
            return NotImplemented
        return PolynominalModRing(self.a + x.a, self.n)

    def __neg__(self: "PolynominalModRing") -> "PolynominalModRing":
        return PolynominalModRing(-self.a, self.n)

    def __eq__(self, x: Any) -> bool:
        if not isinstance(x, PolynominalModRing) or self.n != x.n:
            return NotImplemented
        return self.a == x.a

    def identity(self: "PolynominalModRing") -> "PolynominalModRing":
        return PolynominalModRing(self.a.identity(), self.n)

    def zero(self: "PolynominalModRing") -> "PolynominalModRing":
        return PolynominalModRing(self.a.zero(), self.n)


class PolynominalFiniteField(Field["PolynominalFiniteField"]):
    def __init__(self: "PolynominalFiniteField", a: "Polynominal", n: "Polynominal") -> None:
        self.a = a % n
        self.n = n

    def __repr__(self: "PolynominalFiniteField") -> str:
        return "%s (mod %s)" % (str(self.a), str(self.n))

    def __mul__(self: "PolynominalFiniteField", x: "PolynominalFiniteField") -> "PolynominalFiniteField":
        if self.n != x.n:
            return NotImplemented
        return PolynominalFiniteField(self.a * x.a, self.n)

    def __add__(self: "PolynominalFiniteField", x: "PolynominalFiniteField") -> "PolynominalFiniteField":
        if self.n != x.n:
            return NotImplemented
        return PolynominalFiniteField(self.a + x.a, self.n)

    def __neg__(self: "PolynominalFiniteField") -> "PolynominalFiniteField":
        return PolynominalFiniteField(-self.a, self.n)

    def __eq__(self, x: Any) -> bool:
        if not isinstance(x, PolynominalFiniteField) or self.n != x.n:
            return NotImplemented
        return self.a == x.a

    def identity(self: "PolynominalFiniteField") -> "PolynominalFiniteField":
        return PolynominalFiniteField(self.a.identity(), self.n)

    def zero(self: "PolynominalFiniteField") -> "PolynominalFiniteField":
        return PolynominalFiniteField(self.a.zero(), self.n)

    def inverse(self: "PolynominalFiniteField") -> "PolynominalFiniteField":
        y, _, p = euclid_gcd(self.a, self.n)
        if p.n == 1:
            return PolynominalFiniteField(y * Polynominal([p.coeffs[0].inverse()]), self.n)
        else:
            raise Exception("Not finite field")


def main() -> None:
    int_6 = Integer(6)
    int_9 = Integer(9)
    int_4 = Integer(4)

    a = Q(Z( 8), Z(3))
    b = Q(Z(-5), Z(4))
    c = Q(Z( 3), Z(7))
    print(a * b + c)

    mr_3_5 = ModRing(Z(3), Z(5))
    mr_4_5 = ModRing(Z(4), Z(5))
    print(mr_3_5 + mr_4_5)

    mr_3_5 = ModRing(Z(3), Z(5))
    mr_2_5 = ModRing(Z(2), Z(5))
    print(mr_3_5 * mr_2_5)

    ff_3_5 = FiniteField(Z(5), Z(11))
    print(ff_3_5.inverse())

    f = Polynominal([Q(Z(1), Z(1)), Q(Z(0), Z(1))])
    g = Polynominal([Q(Z(1), Z(1)), Q(Z(0), Z(1)), Q(Z(-2), Z(1))])
    r = PolynominalFiniteField(f, g)
    print(r)
    print(r * r)


if __name__ == "__main__":
    main()