C'est la finale de la 3 série.
Jusqu'à la dernière fois, j'ai créé diverses classes dans la gamme des entiers et des nombres rationnels.
Cette fois, nous allons d'abord créer une classe qui gère les polynomies d'ordre $ n $, puis gérer les polynomies avec la classe d'anneau de classe restante que nous avons créée la dernière fois. Et enfin, nous élargirons le champ des nombres rationnels.
Afin d'effectuer une expansion algébrique, il est nécessaire de traiter des polynômes. Par conséquent, nous définissons ici une classe qui gère les polynomies $ n $ degrés (** anneau polymorphe **) et faisons les derniers préparatifs pour l'expansion algébrique.
Le polypole d'ordre $ n $ se compose de coefficients $ n + 1 $ et de la variable $ x $, y compris le terme constant.
Par conséquent, dans l'anneau polymorphe, le coefficient $ a_k $ se présente sous la forme d'une liste.
On peut voir que l'addition, la multiplication et la soustraction (éléments inverses supplémentaires) peuvent toujours être calculées pour les polynomies, mais elles ne sont pas toujours divisibles lorsqu'elles sont divisées par des polynomies, ce qui entraîne un ** anneau **. De plus, puisque vous pouvez définir la division de la troncature et le reste, vous pouvez voir qu'il devient le ** anneau euclidien ** qui est apparu la dernière fois.
La classe Polynomial définie ici hérite de ʻEuclidianRing et en même temps hérite de Generic [PolynomialBaseType]`. Si vous en héritez, «Polynomial» sera traité comme une classe générique, et si vous l'écrivez sous la forme de «Polynomial [T]» dans le code, le type décrit dans la partie de «T» sera affecté à «PolynomialBaseType». Est vérifié (similaire à un modèle C ++).
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)
Ici, la méthode euclidienne de division mutuelle «euclid_gcd» est remplacée et le processus de division de l'engagement maximum par le coefficient d'ordre le plus élevé est inclus. Cela permet d'obtenir des polynomies moniques lors du calcul des promesses maximales entre polynômes.
Le code est long, testons-le une fois.
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
Puisque $ 2 x ^ 3 + x ^ 2-3 x + 2 = (2 x + 1) (x ^ 2 + 1) + (-5 x + 1) $, le quotient et le reste correspondaient certainement.
Assurez-vous également que «Générique» fonctionne. Essayez de remplacer les crochets «[]» par le corps approprié.
f = Polynomial[FiniteField_11](Q(Z(1)),Q(Z(1)))
Lorsque je le vérifie avec mypy, j'obtiens une erreur indiquant que ce n'est pas le type attendu.
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"
L'anneau restant $ a \ pmod n $, et $ a $ et $ n $ étaient respectivement des anneaux euclidiens. Puisque l'anneau polymorphe est également un anneau euclidien, vous pouvez créer un anneau en vous concentrant sur le reste.
Pour créer un anneau résiduel polynomial pour un diviseur particulier, remplacez simplement ʻInteger dans l'anneau de classe résiduelle par Polynomial [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)
Dans le cas d'un anneau de classe de reste entier, si le diviseur est un "nombre premier" qui ne peut pas être davantage factorisé en premier, il s'agit d'un corps fini.
Même pour les polynômes, si le polynôme diviseur est un ** polynôme irréductible ** qui ne peut pas être davantage factorisé dans une plage de champ spécifique, alors il y aura toujours un élément inverse dans l'anneau de reste du polynôme.
Par exemple, dans la plage des nombres rationnels, $ x ^ 2 -1 $ peut être factorisé comme $ (x + 1) (x -1) $, mais $ x ^ 2-1 $ ne peut pas être factorisé. Cependant, si vous l'étendez à la plage de nombres réels, vous pouvez le factoriser en $ (x + \ sqrt 2) (x- \ sqrt 2) $. En d'autres termes, $ x ^ 2 --2 $ est un polymorphisme irréductible dans la gamme des nombres rationnels, mais pas un polymorphisme irréductible dans la gamme des nombres réels.
Maintenant, appliquons Polynomial [Q] au FiniteField précédemment créé tel quel.
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)
Allons vérifier.
$ (x + 1) (x --1) = x ^ 2 --1 = (x ^ 2 --2) + 1 $ est plus certainement $ x + 1 \ pmod {x ^ 2 --2} $ $ x --1 \ pmod {x ^ 2 --2} $.
$ N $ polymorphisme d'ordre $ f (x) = a_0 + a_1 x + a_2 x ^ 2 + \ cdots + a_n x ^ n $ racine $ x $ avec $ K $ comme élément d'un champ $ K $ Prenons le cas où il n’existe pas. Par exemple, en considérant l'équation quadratique du coefficient rationnel $ f (x) = x ^ 2 --2 = 0 $, la solution $ x $ n'existe pas dans la plage des nombres rationnels.
Dans ce cas, considérer un nouveau $ x $ qui satisfait cette équation et l'ajouter au champ $ K $ pour créer un nouveau champ $ L $ s'appelle ** expansion algébrique **.
Ce $ L $ peut être facilement exprimé en utilisant l'anneau de reste du polypole.
Ici, nous avons un polynôme $ g (x) $ et un polynôme de contraction $ f (x) $, et considérons le reste $ r (x) $ obtenu en divisant $ g (x) $ par $ f (x) $ Ensuite, l'équation suivante est vraie.
Si vous remplacez $ a $, la racine de $ f (x) $, pour $ x $, vous obtenez $ g (a) = r (a) $ à partir de $ f (a) = 0 $.
En d'autres termes, substituer la racine du polynôme irréductible $ f (x) $ dans le polynôme $ g (x) $ est le reste de $ g (x) $ divisé par $ f (x) $. Ce n'est qu'une opération à trouver.
Regardons un exemple d'ajout de la racine de $ x ^ 2 - 2 $ au champ de nombre rationnel $ 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)
Tout d'abord, nous avons créé un champ $ L $ en ajoutant les racines de $ x ^ 2 - 2 $ au champ de nombre rationnel $ Q $, et avons assigné $ x $ sur $ L $ à la variable ʻa`. Si vous mettez ce $ x $ au carré, vous pouvez voir que c'est «2».
En d'autres termes, ʻa` est $ \ pm \ sqrt 2 $. Par conséquent, ce corps $ L $ s'écrit également $ Q (\ sqrt 2) $.
Ajoutons les racines de $ x ^ 2-3 $ pour créer le corps $ M $ (c'est-à-dire $ Q (\ sqrt 2, \ sqrt 3) $). Une chose à noter ici est que les coefficients du polypole doivent être extraits de $ 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))
#Voici une erreur
#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))
La sortie est désordonnée, mais j'ai pu créer les équivalents de $ \ pm \ sqrt {2} $ et $ \ pm \ sqrt {3} $ dans la même classe.
Bien sûr, vous pouvez également créer $ \ 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))
Il convient de noter ici que les nombres ajoutés dans l'expansion algébrique sont dans une dimension différente des éléments du corps d'origine.
Par exemple, $ \ pm \ sqrt {2} $, $ \ pm \ sqrt {3} $ et $ \ pm \ sqrt {6} $ peuvent être comparés chacun par carré, mais $ \ Il n'est pas possible de savoir lequel est le plus grand, pm \ sqrt {2} $ ou $ \ pm \ sqrt {3} $ tels quels.
En fait, avant de donner l'indication de type, j'ai eu l'erreur suivante en ajoutant $ \ sqrt {3} $ à $ Q (\ sqrt {2}) $, et j'étais inquiet car je ne pouvais pas comprendre la cause même si je la lisais.
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'
Cependant, lorsque je lui ai donné un indice de type et que je l'ai vérifié avec mypy, cela m'a donné un message très facile à comprendre comme celui ci-dessous.
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"
En parlant bien sûr, c'est une erreur naturelle, mais quand je vous ai dit l'erreur pour la première fois, je me suis dit: "Oh, je vois."
Mypy est un outil qui signale les malentendus et les erreurs résultant de la complexité des programmes.
Recommended Posts