Dies ist das Finale der 3er Serie.
Bis zum letzten Mal habe ich verschiedene Klassen im Bereich von ganzen Zahlen und rationalen Zahlen erstellt.
Dieses Mal erstellen wir zuerst eine Klasse, die Polynome der Ordnung $ n $ behandelt, und dann Polynome mit der Ringklasse der restlichen Klasse, die wir zuletzt erstellt haben. Und schließlich werden wir das Feld der rationalen Zahlen erweitern.
Um eine algebraische Expansion durchzuführen, müssen Polynome behandelt werden. Daher definieren wir hier eine Klasse, die Polynome mit einem Grad von $ n $ (** polymorpher Ring **) behandelt und die endgültigen Vorbereitungen für die algebraische Expansion trifft.
Das $ n $ -Ordnungspolypoly besteht aus $ n + 1 $ -Koeffizienten und der Variablen $ x $ einschließlich des konstanten Terms.
Daher wird im polymorphen Ring der Koeffizient $ a_k $ in Form einer Liste gehalten.
Es ist ersichtlich, dass Addition, Multiplikation und Subtraktion (zusätzliche inverse Elemente) immer für Polynome berechnet werden können, aber sie sind nicht immer teilbar, wenn sie durch Polynome geteilt werden, was zu einem ** Ring ** führt. Da Sie die Kürzungsteilung und den Rest definieren können, können Sie auch sehen, dass es sich um den ** euklidischen Ring ** handelt, der beim letzten Mal aufgetreten ist.
Die hier definierte Klasse "Polynom" erbt von "EuclidianRing" und gleichzeitig von "Generic [PolynomialBaseType]". Wenn Sie dies erben, wird "Polynom" als generische Klasse behandelt, und wenn Sie es in Form von "Polynom [T]" in den Code schreiben, wird der im Teil von "T" beschriebene Typ "PolynomialBaseType" zugewiesen. Wird aktiviert (ähnlich einer C ++ - Vorlage).
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)
Hier wird die euklidische Methode der gegenseitigen Teilung "euclid_gcd" überschrieben, und die Verarbeitung der Division des maximalen Versprechens durch den Koeffizienten höchster Ordnung wird eingeschlossen. Dies ermöglicht es, monische Polynome zu erhalten, wenn die maximalen Versprechen zwischen Polynomen berechnet werden.
Der Code ist lang, also testen wir ihn einmal.
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
Da $ 2 x ^ 3 + x ^ 2-3 x + 2 = (2 x + 1) (x ^ 2 + 1) + (-5 x + 1) $, stimmten der Quotient und der Rest sicher überein.
Stellen Sie außerdem sicher, dass "Generic" funktioniert. Versuchen Sie, die eckigen Klammern [] durch den entsprechenden Körper zu ersetzen.
f = Polynomial[FiniteField_11](Q(Z(1)),Q(Z(1)))
Wenn ich es mit mypy überprüfe, erhalte ich die Fehlermeldung, dass es sich nicht um den erwarteten Typ handelt.
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"
Der Restring war $ a \ pmod n $, und $ a $ und $ n $ waren euklidische Ringe. Da der polymorphe Ring auch ein euklidischer Ring ist, können Sie einen Ring erstellen, indem Sie sich auf den Rest konzentrieren.
Um einen Polynomrestring für einen bestimmten Divisor zu erstellen, ersetzen Sie einfach die im Restklassenring angegebene "Ganzzahl" durch ein "Polynom [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)
Wenn im Fall eines Restklassenrings von ganzen Zahlen der Divisor eine "Primzahl" ist, die nicht mehr in Primfaktoren zerlegt werden kann, ist er ein endliches Feld.
Selbst im Fall von Polynomen gibt es im Restring des Polynoms immer ein inverses Element, wenn das Divisor-Polynom ein ** irreduzibles Polynom ** ist, das innerhalb eines bestimmten Feldbereichs nicht weiter faktorisiert werden kann.
Zum Beispiel kann im Bereich rationaler Zahlen $ x ^ 2 -1 $ wie $ (x + 1) (x -1) $ berücksichtigt werden, aber $ x ^ 2-1 $ kann nicht berücksichtigt werden. Wenn es jedoch auf den realen Bereich erweitert wird, kann es in $ (x + \ sqrt 2) (x- \ sqrt 2) $ zerlegt werden. Mit anderen Worten, $ x ^ 2 - 2 $ ist ein irreduzibles Polymorph im Bereich rationaler Zahlen, aber kein irreduzibles Polymorph im Bereich reeller Zahlen.
Wenden wir nun "Polynom [Q]" auf das zuvor erstellte "FiniteField" an.
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)
Lass uns nachsehen.
$ (x + 1) (x - 1) = x ^ 2 - 1 = (x ^ 2 - 2) + 1 $ ist mit Sicherheit $ x + 1 \ pmod {x ^ 2 - 2} $ $ x - 1 \ pmod {x ^ 2 - 2} $.
$ N $ Ordnungspolymorphismus $ f (x) = a_0 + a_1 x + a_2 x ^ 2 + \ cdots + a_n x ^ n $ root $ x $ mit $ K $ als Element eines Feldes $ K $ Betrachten Sie den Fall, in dem es nicht existiert. Unter Berücksichtigung der quadratischen Gleichung des rationalen Koeffizienten $ f (x) = x ^ 2 - 2 = 0 $ existiert die Lösung $ x $ beispielsweise nicht im Bereich der rationalen Zahlen.
In diesem Fall wird die Betrachtung eines neuen $ x $, das diese Gleichung erfüllt, und das Hinzufügen zum Feld $ K $, um ein neues Feld $ L $ zu erstellen, als ** algebraische Erweiterung ** bezeichnet.
Dieses $ L $ kann leicht mit dem Restring des Polypolys ausgedrückt werden.
Hier haben wir ein Polynom $ g (x) $ und ein irreduzibles Polypoly $ f (x) $ und betrachten den Rest $ r (x) $, der durch Teilen von $ g (x) $ durch $ f (x) $ erhalten wird. Dann gilt die folgende Gleichung.
Wenn Sie $ x $ durch $ a $, die Wurzel von $ f (x) $, ersetzen, erhalten Sie $ g (a) = r (a) $ aus $ f (a) = 0 $.
Mit anderen Worten, das Ersetzen der Wurzel des a priori-Polynoms $ f (x) $ durch das Polynom $ g (x) $ ist der Rest von $ g (x) $ geteilt durch $ f (x) $. Es ist nichts anderes als eine Operation zu finden.
Schauen wir uns ein Beispiel für das Hinzufügen der Wurzel von $ x ^ 2 - 2 $ zum rationalen Zahlenfeld $ Q $ an.
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)
Zuerst haben wir das Feld $ L $ erstellt, indem wir die Wurzeln von $ x ^ 2 - 2 $ zum Feld $ Q $ mit rationalen Zahlen hinzugefügt und der Variablen a $ x $ auf $ L $ zugewiesen haben. Wenn Sie dieses $ x $ quadrieren, können Sie sehen, dass es "2" ist.
Mit anderen Worten, a ist $ \ pm \ sqrt 2 $. Daher wird dieser Körper $ L $ auch als $ Q (\ sqrt 2) $ geschrieben.
Fügen wir die Wurzel von $ x ^ 2-3 $ hinzu, um den Körper $ M $ zu machen (dh $ Q (\ sqrt 2, \ sqrt 3) $). Hierbei ist zu beachten, dass die Koeffizienten des Polypolys aus $ L $ extrahiert werden müssen.
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))
#Unten ist ein Fehler
#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))
Die Ausgabe ist chaotisch, aber ich konnte die Entsprechungen von $ \ pm \ sqrt {2} $ und $ \ pm \ sqrt {3} $ in derselben Klasse erstellen.
Natürlich können Sie auch $ \ pm \ sqrt {6} $ erstellen.
d = b * c
print(d * d) # -> 6 (mod x ^ 2 - 2) (mod 1 (mod x ^ 2 - 2) x ^ 2 - 3 (mod x ^ 2 - 2))
Hierbei ist zu beachten, dass die in der algebraischen Erweiterung hinzugefügten Zahlen eine andere Dimension aufweisen als die ursprünglichen Körperelemente.
Daher können beispielsweise $ \ pm \ sqrt {2} $, $ \ pm \ sqrt {3} $ und $ \ pm \ sqrt {6} $ jeweils nach Quadrat verglichen werden, aber $ \ Es ist nicht möglich herauszufinden, welche größer sind, pm \ sqrt {2} $ oder $ \ pm \ sqrt {3} $, wie sie sind.
Bevor ich den Typ-Hinweis gab, als ich $ \ sqrt {3} $ zu $ Q (\ sqrt {2}) $ hinzufügte, bekam ich den folgenden Fehler und war besorgt, weil ich die Ursache nicht verstehen konnte, selbst wenn ich sie las.
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'
Als ich ihm jedoch einen Tipp gab und ihn mit mypy überprüfte, erhielt ich eine sehr leicht verständliche Nachricht wie die folgende.
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"
Apropos, es ist ein natürlicher Fehler, aber als ich Ihnen den Fehler zum ersten Mal erzählte, dachte ich: "Oh, ich verstehe."
Mypy ist ein Tool, das auf Missverständnisse und Fehler hinweist, die sich aus der Komplexität von Programmen ergeben.