Type in Python to implement algebraic extension (2) ~ Field, rational number field, Euclidean ring, modulo ring, finite field ~

Last time, I implemented an integer ring after creating an abstract basis class for monoids, groups, and rings. This time, after creating the abstract basis class of the field, we will implement the rational number field, the modulo ring, and the finite field.

table of contents

  1. Monoids / groups / rings / integer rings
  2. Field, rational number field, Euclidean ring, modulo ring, finite field
  3. Polynomial ring / quotient ring of polynomial / field extension

Implementation

body

The body is a set that meets the following conditions

  1. A ring about multiplication $ \ star $ and addition $ \ oplus $
  2. Sets other than the additive identity element $ 0 $ form a group for multiplication $ \ star $

If you replace this with a familiar word,

  1. There are $ 1 $ and $ 0 $, and you can perform three operations: addition, subtraction, and multiplication.
  2. Elements other than $ 0 $ have a multiplicative inverse element, that is, they can be divided by other than $ 0 $

In other words, it is a set that can perform four arithmetic operations (addition, subtraction, multiplication and division).

When implementing a class, inherit the groups and rings created so far, and return True if it is $ 0 $ only when performing the inverse element test.

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

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

Rational number field

Now, let's make a rational number. A rational number is a number that can be represented in the form $ \ frac {p} {q} $ using the two integers $ p $ and $ q $. Therefore, an instance of a rational number class always holds these $ p $ and $ q $.

When looking for equal fractions, simply comparing $ p $ with $ q $ causes problems. This is because even if the fraction is the same, the denominator may differ depending on the instance. There are two possible ways to deal with this.

It can be reduced by using the Euclidean algorithm, which will be implemented later, but here we will use the simple method of evaluating $ ps = qr $. It's basically the calculation of fractions as you learned in elementary and junior high school, so you don't need to explain it.

class Rational(Field):
    def __init__(self: "Rational", p: Integer, q: Integer = Integer(1)) -> None:
        self.p = p
        self.q = q

    def __repr__(self: "Rational") -> str:
        if self.q == self.q.identity():
            return "%s" % self.p
        return "%s/%s" % (self.p, self.q)

    def __mul__(self: "Rational", x: "Rational") -> "Rational":
        return Rational(self.p * x.p, self.q * x.q)

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

    def __eq__(self, x):
        if not isinstance(x, Rational):
            return NotImplemented
        return self.p * x.q == x.p * self.q

    def __neg__(self: "Rational") -> "Rational":
        return Rational(-self.p, self.q)

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

    def inverse(self: "Rational") -> "Rational":
        return Rational(self.q, self.p)

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

Q = Rational

The alias for Rational is Q.

Now, let's check the operation of rational numbers.

a = Q(Z( 8), Z(3))
b = Q(Z(-5), Z(4))
c = Q(Z( 3), Z(7))
y = a * b + c
print(y)
# -> -244/84

print(y.inverse())
# -> 84/-244

It worked.

At the moment, the reduction is not implemented, but it can be reduced at the time of display by using the Euclidean algorithm described later.

The practice of rational numbers (fractions) in Python

Python has a class fractions.Fraction for expressing fractions. If you just want to work with fractions, this class will suffice.

from fractions import Fraction

a = 0
for i in range(10):
    a += 1/10
print(a == 1)
# -> False

a = 0
for i in range(10):
    a += Fraction(1, 10)
print(a == 1)
# -> True

An example of software that uses Fraction is the Python interface of the video conversion software FFMPEG, PyAV. Fractions are used in the frame rate calculation.

Euclidean ring

From now on, there will be more opportunities for truncation division and remainders. Therefore, it would be convenient to create an abstract base class of the Euclidean ring as a "ring that can be truncated and divided and the remainder can be obtained".

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

class EuclidianRing(Ring, metaclass=ABCMeta):
    @abstractmethod
    def __floordiv__(self: EuclidianRingType, x: EuclidianRingType) -> EuclidianRingType:
        pass

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

Then replace the parent class of ʻIntegerfromRing to ʻEuclidianRing to define truncation division and remainder.

class Integer(EuclidianRing):

    # ~~ snip ~~

    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)

Remains modulo ring

For the integers $ a $, $ b $ and the natural number $ n $, when $ a --b = n \ mathbb {Z} $ ($ \ mathbb {Z} $ is an arbitrary integer) holds, "$ a $ and $ b $ is congruent with $ n $ as the law, "says $ a \ equiv b \ pmod n $. A set that treats these two numbers as the same is called "the ring of cosets modulo $ n $".

Now, let's implement the coset ring class ModRing.

Instances of the ring of coset classes hold $ a $ and the law $ n $. Make sure that $ a $ and $ n $ accept arbitrary Euclidean rings, not just integers. Also, since we want $ a $ to be the smallest congruence number of 0 or more when displaying on the screen, we will calculate $ a \ bmod n $ when creating the instance.

Next, you need to make it impossible to calculate numbers with different methods. Therefore, ModRing should be the base class of all coset rings, and subclasses should be created for each different method. This allows type checking to fail if you try to calculate numbers with different methods. In addition, set __init__ to @abstractmethod so that ModRing itself cannot be instantiated.

ModRingType = TypeVar("ModRingType", bound="ModRing")
ModRingBaseType = TypeVar("ModRingBaseType", bound="EuclidianRing")

class ModRing(Ring, metaclass=ABCMeta):
    @abstractmethod
    def __init__(self: ModRingType, a: ModRingBaseType, n: ModRingBaseType) -> None:
        self.a = a % n
        self.n = n

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

    def __mul__(self: ModRingType, x: ModRingType) -> ModRingType:
        return self.__class__(self.a * x.a)

    def __add__(self: ModRingType, x: ModRingType) -> ModRingType:
        return self.__class__(self.a + x.a)

    def __neg__(self: ModRingType) -> ModRingType:
        return self.__class__(-self.a)

    def __eq__(self, x):
        if not isinstance(x, self.__class__):
            return NotImplemented
        return self.a == x.a

    def identity(self: ModRingType) -> ModRingType:
        return self.__class__(self.a.identity())

    def zero(self: ModRingType) -> ModRingType:
        return self.__class__(self.a.zero())

By setting self.__class__ in each method, you can refer to an instance of a child class with a divisor, not the modulo ring class itself.

For example, when creating a coset ring class with a divisor of 5, do as follows.

class ModRing_5(ModRing):
    def __init__(self, a: Integer) -> None:
        super().__init__(a, Integer(5))

Now, let's check the operation of the coset ring.

First is the calculation of numbers with different methods.

mr_3_5 = ModRing_5(Z(3))
mr_2_4 = ModRing_4(Z(2))
print(mr_3_5 + mr_2_4)
$ mypy ./field_extension.py
field_extension.py:238: error: Unsupported operand types for + ("ModRing_5" and "ModRing_4")

I got an error in mypy. If the method is the same, no error will occur and the calculation can be performed without any problem.

mr_3_5 = ModRing_5(Z(3))
mr_4_5 = ModRing_5(Z(4))
print(mr_3_5 + mr_4_5) # -> 2 (mod 5)

The condition that the coset ring is a field

Of the rings, the elements other than $ 0 $ have the reciprocal of the multiplication, that is, the one that meets the following conditions is called the body.

$ x \ star x ^ {-1} = x ^ {-1} \ star x = e $ exists $ x ^ {-1} $

When applied to the modulo ring, finding the integer $ p $ that satisfies the following equation for $ a \ pmod n $ is the inverse element.

a p \equiv 1 \pmod n

From the congruence definition above, using the integer $ q $

a p - n q = 1

The sum (difference) of a multiple of $ a $ and a multiple of $ n $ is a multiple of the greatest common divisor of $ a $ and $ n $ $ GCD (a, n) $. This is called Bezout's equation. That is, $ GCD (a, n) = 1 $ (disjoint).

Any $ a $ less than $ n $ and $ n $ relatively prime are prime numbers, so if $ n $ is a prime number, the ring of coprime is a field. This is called a finite field because it is a body consisting of a finite number of elements.

Euclidean algorithm

Using the Euclidean algorithm, we can find a set of integers $ p $, $ q $, and $ r $ that satisfy Becquerel's equation $ a p + b q = r = GCD (a, b) $.

The Euclidean algorithm can be performed within the Euclidean ring. Therefore, the Euclidean algorithm is implemented in the Euclidean ring class.

In the type hint, if there is a tuple in the argument or return value of the function, use typing.Tuple and specify the type of each element in square brackets.

from typing import Tuple

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

class EuclidianRing(Ring, metaclass=ABCMeta):
    
    # ~~ snip ~~

    def euclid_gcd(self: EuclidianRingType, b: EuclidianRingType) -> Tuple[EuclidianRingType, EuclidianRingType, EuclidianRingType]:
        a = self
        p = a.zero()
        q = a.identity()
        p_1 = a.identity()
        q_1 = a.zero()
        while True:
            c = a % b
            if c == c.zero():
                break
            p_2 = p_1
            q_2 = q_1
            p_1 = p
            q_1 = q
            p = p_2 - p_1 * (a // b)
            q = q_2 - q_1 * (a // b)
            a = b
            b = c
        return (p, q, b)

Now that we have implemented the Euclidean algorithm, let's reduce it with the rational number __init__.

class Rational(Field):
    def __init__(self: "Rational", p: Integer, q: Integer = Integer(1)) -> None:
        _, _, r =  p.euclid_gcd(q)
        self.p = p // r
        self.q = q // r

Finite field

Now, let's create a finite field class. The finite field class inherits from ModRing and defines the ʻinverse method. The finite field $ n $ must be a prime number, but since it is difficult to determine exactly that it is a prime number, we do not check it when creating an instance, and we do not check each other in ʻinverse. I will check if it is.

FiniteFieldType = TypeVar("FiniteFieldType", bound="FiniteField")

class FiniteField(Field, ModRing, metaclass=ABCMeta):
    def inverse(self: FiniteFieldType) -> FiniteFieldType:
        p, q, r = self.a.euclid_gcd(self.n)
        if r == r.identity():
            return self.__class__(p)
        raise Exception("a and n are not co-prime")

Let's test it.

class FiniteField_11(FiniteField):
    def __init__(self, a: Integer) -> None:
        super().__init__(a, Integer(11))

ff_5_11 = FiniteField_11(Z(5))
print(ff_5_11.inverse())
# -> 9 (mod 11)

Since $ 5 \ times 9 = 45 \ equiv 1 \ pmod {11} $, the multiplication inverse of $ 5 \ pmod {11} $ is certainly $ 9 \ pmod {11} $.

Next time preview

Next time, we will define a polynomial ring and apply the ModRing and FiniteField classes, which were based only on integers this time, to polynomials. And finally, we will expand the rational number field.

Recommended Posts

Type in Python to implement algebraic extension (2) ~ Field, rational number field, Euclidean ring, modulo ring, finite field ~
Type in Python to implement algebraic extension (3) ~ Polynomial ring / Polynomial quotient ring / Field extension ~
Type in Python to implement algebraic extension (1) ~ Monoids, groups, rings, ring of integers ~
Implement extension field in Python
Implement a deterministic finite automaton in Python to determine multiples of 3
I tried to implement PLSA in Python
I tried to implement permutation in Python
I tried to implement PLSA in Python 2
I tried to implement ADALINE in Python
I tried to implement PPO in Python
Try to implement Oni Maitsuji Miserable in python
How to implement Discord Slash Command in Python
Type Python scripts to run in QGIS Processing
How to implement shared memory in Python (mmap.mmap)
I tried to implement TOPIC MODEL in Python
I tried to implement selection sort in python
How to handle datetime type in python sqlite3
I want to easily implement a timeout in python
How to get the number of digits in Python
I tried to implement a pseudo pachislot in Python
I tried to implement Dragon Quest poker in Python
Implement the solution of Riccati algebraic equations in Python
I tried to implement GA (genetic algorithm) in Python
Convert Webpay Entity type to Dict type (recursively in Python)