Dieser Streifzug führt zu einigen der in mathGUIde eingebauten Möglichkeiten des Rechnens in Polynomringen
Die Beispiele stammen aus dem Buch Teschl, Gerald; Teschl, Susanne: Mathematik für Informatiker, Band 1: Diskrete Mathematik und Lineare Algebra, Springer, Berlin, 3. Aufl., 2008, ISBN: 978-3-540-77431-0.
Teschl, Beispiel 4.19
Wir untersuchen die Addition und Multiplikation im Polynomring
\mathbb Z_2[x]_{x^2+x+1} = \{ 0, 1, x, x+1 \}
Die folgenden Programmzeilen geben die Additionstafel und die Multiplikationstafel in diesem Ring aus.
Der mathGUIde-Funktion printTable werden Funktionen
zur Berechnung der Zellelemente übergeben.
Wir ersparen uns die separate Definition dieser Funktionen, indem wir anonyme Funktionen verwenden.
Diese werden mit dem Pfeiloperator (=>) definiert:
Vor dem Pfeil steht die Parameterliste (bei mehreren Parametern in Klammern), dahinter der Funktionswert.
In der Multiplikationstabelle finden Sie in jeder Zeile (außer für Null) eine Eins als Multiplikationsergebnis. Mit anderen Worten: Jedes von Null verschiedene Element hat ein multiplikatives Inverses. Daher ist der Ring sogar ein Körper.
Zum Vergleich machen wir das gleiche Experiment modulo eines anderen Polyonms:
Teschl, Beispiel 4.20
\mathbb Z_2[x]_{x^2+1} = \{ 0, 1, x, x+1 \}
Hier sieht man, dass es zu x+1 kein multiplikatives Inverses gibt und der Ring daher kein Körper ist.
Weitere Beispiele
Teschl: Beispiel 4.3 a bis c
p(x) = x^3 + x,\; q(x) = x + 1 \; \textrm{in} \; \mathbb Z_2[x]
Teschl: Beispiel 4.3 d bis e
p(x) = x^2 + 2x + 1,\; q(x) = x + 2 \; \textrm{in} \; \mathbb Z_3[x]
Teschl: Beispiel 4.5 a
Teschl: Beispiel 4.5 b
Teschl: Beispiel 4.9
Teschl: Beispiel 4.9 b
Teschl: Beispiel 4.9 c
Teschl: Beispiel 4.11
Irreduzible Polynome
Definition
Ein Polynom vom Grad > 0 heißt irreduzibel (Primpolynom), wenn es nicht Produkt von Polynomen niedrigerer Grade ist.
Das folgende Programmstück findet alle irreduziblen Polynome aus \mathbb Z_2[x] bis zum Grad 5.
Dazu erzeugt es der Reihe nach die Polynome aus den Bitmustern der Binärzahlen bis 63 (26-1) und prüft, ob es durch eines der bisher gefundenen irreduziblen Polynome teilbar ist:
Zyklische Codes (CRC = Cyclic Redundancy Code)
Dieser Abschnitt ist noch unfertig.
Um Blöcke von n Bits zu codieren, wählt man zunächst eine Faktorisierung dex Polynoms x^n+1:
x^n + 1 = g(x) \cdot h(x)
Für n = 7 testen wir, ob g(x) = x^4 + x^3 +x^2 + 1 ein Teiler von f(x) = x^n + 1 ist:
Ja. g(x) ist das Generatorpolynom, der andere Faktor, h(x), das Kontrollpolynom.
Wir haben damit den zyklischen Code
C = \{ f(x) * g(x) | f(x) \in \mathbb Z_2[x]_{x^7+1} \}
Da \mathrm{deg}(g) = 4 und x^7 = 1
in \mathbb Z_2[x]_{x^7+1},
kommen für f(x) nur die Polynome vom Grad <3 in Frage.
