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.
The body is a set that meets the following conditions
- A ring about multiplication $ \ star $ and addition $ \ oplus $
- Sets other than the additive identity element $ 0 $ form a group for multiplication $ \ star $
If you replace this with a familiar word,
- There are $ 1 $ and $ 0 $, and you can perform three operations: addition, subtraction, and multiplication.
- 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()
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.
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.
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)
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)
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.
From the congruence definition above, using the integer $ q $
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.
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
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, 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