This is the final episode of the 3-part series.
Until the last time, I have created various classes in the range of integers and rational numbers.
This time, we will first create a class that handles the $ n $ degree polynomial, and then handle the polynomial with the ring of dissituation class that we created last time. And finally, we will expand the rational number field.
In order to perform algebraic extension, we need to deal with polynomials. Therefore, here we define a class (** polynomial ring **) that handles $ n $ degree polynomials and make the final preparations for algebraic extension.
The $ n $ order polynomial consists of $ n + 1 $ coefficients and the variable $ x $, including the constant term.
Therefore, in the polynomial ring, the coefficient $ a_k $ is held in the form of a list.
Polynomials can always be added, multiplied, and subtracted (additive inverse), but they are not always divisible when divided by polynomials, and it turns out that they are ** rings **. Also, since you can define truncation division and remainder, you can see that it becomes the ** Euclidean ring ** that appeared last time.
The Polynomial class defined here inherits from ʻEuclidianRing and at the same time inherits from Generic [PolynomialBaseType] . If you inherit this, Polynomial will be treated as a generic class, and if you write it in the form of Polynomial [T] in the code, the type described in the part of Twill be assigned toPolynomialBaseType`. Is checked (similar to a C ++ template).
from typing import Generic, List
from itertools import dropwhile, zip_longest
PolynomialBaseType = TypeVar("PolynomialBaseType", bound=Field)
class Polynomial(EuclidianRing, Generic[PolynomialBaseType]):
def __init__(self: "Polynomial[PolynomialBaseType]", *args: PolynomialBaseType) -> None:
self.coeffs = list(dropwhile(lambda x: x == x.zero(), args))
if not self.coeffs:
self.coeffs = [args[0].zero()]
@staticmethod
def _mul_poly(a: List[PolynomialBaseType], b: List[PolynomialBaseType]) -> List[PolynomialBaseType]:
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))
@staticmethod
def _div_poly(a: List[PolynomialBaseType], b: List[PolynomialBaseType]) -> Tuple[List[PolynomialBaseType], List[PolynomialBaseType]]:
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)
def __repr__(self: "Polynomial") -> str:
s = " " + " + ".join("%s x ^ %d" % (repr(c), len(self.coeffs) - i - 1) for i, c in enumerate(self.coeffs) if c != c.zero()) + " "
s = s.replace(" + -", " - ")
s = s.replace(" x ^ 0 ", " ")
s = s.replace(" x ^ 1 ", " x ")
s = s.replace(" 1 x ", " x ")
return s.strip()
def __floordiv__(self: "Polynomial[PolynomialBaseType]", x: "Polynomial[PolynomialBaseType]") -> "Polynomial[PolynomialBaseType]":
q, r = Polynomial._div_poly(self.coeffs, x.coeffs)
return Polynomial[PolynomialBaseType](*q)
def __mod__(self: "Polynomial[PolynomialBaseType]", x: "Polynomial[PolynomialBaseType]") -> "Polynomial[PolynomialBaseType]":
q, r = Polynomial._div_poly(self.coeffs, x.coeffs)
return Polynomial[PolynomialBaseType](*r)
def __mul__(self: "Polynomial[PolynomialBaseType]", x: "Polynomial[PolynomialBaseType]") -> "Polynomial[PolynomialBaseType]":
y = Polynomial._mul_poly(self.coeffs, x.coeffs)
return Polynomial[PolynomialBaseType](*y)
def __add__(self: "Polynomial[PolynomialBaseType]", x: "Polynomial[PolynomialBaseType]") -> "Polynomial[PolynomialBaseType]":
y = list(a + b for a, b in zip_longest(reversed(self.coeffs), reversed(x.coeffs), fillvalue=self.coeffs[0].zero()))
y.reverse()
return Polynomial[PolynomialBaseType](*y)
def __neg__(self: "Polynomial[PolynomialBaseType]") -> "Polynomial[PolynomialBaseType]":
return Polynomial[PolynomialBaseType](*(-aforainself.coeffs))
def __eq__(self, x):
if not isinstance(x, Polynomial):
return NotImplemented
return self.coeffs == x.coeffs
def identity(self: "Polynomial[PolynomialBaseType]") -> "Polynomial[PolynomialBaseType]":
return Polynomial[PolynomialBaseType](self.coeffs[0].identity())
def zero(self: "Polynomial[PolynomialBaseType]") -> "Polynomial[PolynomialBaseType]":
return Polynomial[PolynomialBaseType](self.coeffs[0].zero())
def euclid_gcd(self: "Polynomial[PolynomialBaseType]", b: "Polynomial[PolynomialBaseType]") -> Tuple["Polynomial[PolynomialBaseType]", "Polynomial[PolynomialBaseType]", "Polynomial[PolynomialBaseType]"]:
p, q, r = super().euclid_gcd(b)
r.coeffs = [x / r.coeffs[0] for x in r.coeffs]
return (p, q, r)
Here, the Euclidean algorithm ʻeuclid_gcd` is overridden to divide the greatest common divisor by the highest-order coefficient. This makes it possible to obtain monic polynomials when calculating the greatest common divisor between polynomials.
The code is long, so let's test it once.
f = Polynomial[Q](Q(Z(1)),Q(Z(1))) # x + 1
g = Polynomial[Q](Q(Z(1)),-Q(Z(1))) # x - 1
print(f * g) # -> x ^ 2 - 1
x = Polynomial[Q](Q(Z(2)),Q(Z(1)),Q(Z(-3)),Q(Z(2))) # 2 x ^ 3 + x ^ 2 - 3 x + 2
y = Polynomial[Q](Q(Z(1)),Q(Z(0)),Q(Z(1))) # x ^ 2 + 1
print(x // y) # -> 2 x + 1
print(x % y) # -> -5 x + 1
Since $ 2 x ^ 3 + x ^ 2-3 x + 2 = (2 x + 1) (x ^ 2 + 1) + (-5 x + 1) $, the quotient and the remainder certainly matched.
Also, make sure that Generic is working. Try replacing the square brackets [] with the appropriate body.
f = Polynomial[FiniteField_11](Q(Z(1)),Q(Z(1)))
When I check it with mypy, I get an error that it is not the expected type.
field_extension.py:347: error: Argument 1 to "Polynomial" has incompatible type "Rational"; expected "FiniteField_11"
field_extension.py:347: error: Argument 2 to "Polynomial" has incompatible type "Rational"; expected "FiniteField_11"
The coset ring $ a \ pmod n $, and $ a $ and $ n $ were Euclidean rings, respectively. Since polynomial rings are also Euclidean rings, you can create rings by focusing on the remainder.
To create a polynomial remainder ring for a particular divisor, simply replace ʻIntegerin the remainder class ring withPolynomial [Q]`.
class MR_x2_1(ModRing): # (mod x ^ 2 + 1)
def __init__(self: "MR_x2_1", a: Polynomial[Q]) -> None:
super().__init__(a, Polynomial[Q](Q(Z(1)),Q(Z(0)),Q(Z(1))))
u = MR_x2_1(Polynomial[Q](Q(Z(2)),Q(Z(1)),Q(Z(-3)),Q(Z(2))))
print(u) # -> -5 x + 1 (mod x ^ 2 + 1)
In the case of an integer modulo ring, if the divisor is a "prime number" that cannot be further factorized, it is a finite field.
Even for polynomials, if the polynomial that corresponds to the divisor is a ** irreducible polynomial ** that cannot be further factored within a specific field range, there will always be an inverse element in the quotient ring of the polynomial.
For example, in the range of rational numbers, $ x ^ 2 -1 $ can be factored like $ (x + 1) (x -1) $, but $ x ^ 2-1 $ cannot be factored. However, if you expand it to the range of real numbers, you can factor it like $ (x + \ sqrt 2) (x-\ sqrt 2) $. In other words, $ x ^ 2 --2 $ is an irreducible polynomial in the range of rational numbers, but not an irreducible polynomial in the range of real numbers.
Now, let's apply Polynomial [Q] to the previously created FiniteField as it is.
class F_x2_n2(FiniteField): # (mod x ^ 2 - 2)
def __init__(self: "F_x2_n2", a: Polynomial[Q]) -> None:
super().__init__(a, Polynomial[Q](Q(Z(1)),Q(Z(0)),Q(Z(-2))))
v = F_x2_n2(Polynomial[Q](Q(Z(1)),Q(Z(1)))) # x + 1 (mod x ^ 2 - 2)
print(v.inverse()) # -> x - 1 (mod x ^ 2 - 2)
Let's check.
$ (x + 1) (x --1) = x ^ 2 --1 = (x ^ 2 --2) + 1 $ is more certainly the multiplication inverse of $ x + 1 \ pmod {x ^ 2 --2} $ $ x --1 \ pmod {x ^ 2 --2} $.
$ N $ order polynomial $ f (x) = a_0 + a_1 x + a_2 x ^ 2 + \ cdots + a_n x ^ n $ root $ x $ with a coefficient of the element of a field $ K $ becomes $ K $ Consider the case where it does not exist. For example, considering the rational coefficient quadratic equation $ f (x) = x ^ 2 --2 = 0 $, the solution $ x $ does not exist in the range of rational numbers.
In that case, adding $ x $ that satisfies this equation to the field $ K $ to create a new field $ L $ is called ** algebraic extension **.
This $ L $ can be easily expressed using the quotient ring of the polynomial.
Here we have a polynomial $ g (x) $ and an irreducible polynomial $ f (x) $, and consider the remainder $ r (x) $ obtained by dividing $ g (x) $ by $ f (x) $. Then, the following equation holds.
If you substitute $ a $, the root of $ f (x) $, for $ x $, you get $ g (a) = r (a) $ from $ f (a) = 0 $.
In other words, substituting the root of the irreducible polynomial $ f (x) $ into the polynomial $ g (x) $ is the remainder of dividing $ g (x) $ by $ f (x) $ $ r (x) $ It is nothing but an operation to find.
Let's look at an example of adding the root of $ x ^ 2 − 2 $ to the rational number field $ Q $.
class L(FiniteField): # Q(√2)
def __init__(self: "L", a: Polynomial[Q]) -> None:
super().__init__(a, Polynomial[Q](Q(Z(1)),Q(Z(0)),Q(Z(-2)))) # x^2 - 2
a = L(Polynomial[Q](Q(Z(1)),Q(Z(0))))
print(a * a) # -> 2 (mod x ^ 2 - 2)
First, we created the field $ L $, which is the rational number field $ Q $ plus the root of $ x ^ 2 − 2 $, and assigned $ x $ on $ L $ to the variable ʻa. If you square this $ x $, you can see that it is 2`.
In other words, ʻa` is $ \ pm \ sqrt 2 $. Therefore, we also write this body $ L $ as $ Q (\ sqrt 2) $.
Let's add the roots of $ x ^ 2-3 $ to make the body $ M $ (that is, $ Q (\ sqrt 2, \ sqrt 3) $). One thing to note here is that we need to extract the coefficients of the polynomial from $ L $.
L_1 = L(Polynomial[Q](Q(Z(1))))#1inQ(√2)
L_3 = L(Polynomial[Q](Q(Z(3))))#3inQ(√2)
L_0 = L(Polynomial[Q](Q(Z(0))))#0inQ(√2)
class M(FiniteField): # Q(√2, √3)
def __init__(self, a: Polynomial[L]) -> None:
super().__init__(a, Polynomial[L](L_1,L_0,-L_3))
#Below is an error
#super().__init__(a, Polynomial[L](Q(Z(1)),Q(Z(0)),-Q(Z(3))))
b = M(Polynomial[L](a))
print(b * b) # -> 2 (mod x ^ 2 - 2) (mod 1 (mod x ^ 2 - 2) x ^ 2 - 3 (mod x ^ 2 - 2))
c = M(Polynomial[L](L_1,L_0))
print(c * c) # -> 3 (mod x ^ 2 - 2) (mod 1 (mod x ^ 2 - 2) x ^ 2 - 3 (mod x ^ 2 - 2))
The output is messy, but I was able to create the equivalents of $ \ pm \ sqrt {2} $ and $ \ pm \ sqrt {3} $ in the same class.
Of course, you can also make $ \ pm \ sqrt {6} $.
d = b * c
print(d * d) # -> 6 (mod x ^ 2 - 2) (mod 1 (mod x ^ 2 - 2) x ^ 2 - 3 (mod x ^ 2 - 2))
It should be noted here that the numbers added in the algebraic extension are in a different dimension from the original body elements.
Therefore, for example, $ \ pm \ sqrt {2} $, $ \ pm \ sqrt {3} $, and $ \ pm \ sqrt {6} $ can be compared in size by squared, but $ \ You can't just look at pm \ sqrt {2} $ or $ \ pm \ sqrt {3} $ to see which is larger.
Actually, before giving the type hint, I got the following error when adding $ \ sqrt {3} $ to $ Q (\ sqrt {2}) $, and I was worried because I could not understand the cause even if I read it.
Traceback (most recent call last):
File "./field_extension.py", line 370, in <module>
print(c * c) # -> 3 (mod x ^ 2 - 2) (mod 1 (mod x ^ 2 - 2) x ^ 2 - 3 (mod x ^ 2 - 2))
File "./field_extension.py", line 214, in __mul__
return self.__class__(self.a * x.a)
File "./field_extension.py", line 364, in __init__
super().__init__(a, Polynomial(Q(Z(1)),Q(Z(0)),-Q(Z(3))))
File "./field_extension.py", line 207, in __init__
self.a = a % n
File "./field_extension.py", line 283, in __mod__
q, r = Polynomial._div_poly(self.coeffs, x.coeffs)
File "./field_extension.py", line 265, in _div_poly
q[i] = r[i] / b[0]
File "./field_extension.py", line 37, in __truediv__
return self * x.inverse()
File "./field_extension.py", line 214, in __mul__
return self.__class__(self.a * x.a)
AttributeError: 'Rational' object has no attribute 'a'
However, when I gave a type hint and checked it with mypy, it told me with a very easy-to-understand message like the following.
field_extension.py:364: error: Argument 1 to "Polynomial" has incompatible type "Rational"; expected "L"
field_extension.py:364: error: Argument 2 to "Polynomial" has incompatible type "Rational"; expected "L"
field_extension.py:364: error: Argument 3 to "Polynomial" has incompatible type "Rational"; expected "L"
Speaking of course, it is a natural mistake, but when I first told you the mistake, I thought, "Oh, I see."
Mypy is a tool that points out misunderstandings and mistakes that result from the complexity of programs.
Recommended Posts