# Rechnen in Polynomringen

Diese Präsentation zeigt einige 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 sogenannte anonyme Funktionen verwenden. Diese werden mit dem Schlüsselwort lambda definiert: Nach dem lambda kommt die Parameterliste, danach ein Doppelpunkt und der Funktionswert.

    m = Poly([1,1,1], 2) # 1 + x + x²
    # Alle Polynome mod m
    #          0            1              x            1+x
    P = [Poly([0],2), Poly([1],2), Poly([0,1],2), Poly([1,1],2)]

    printTable(4, 4,
        lambda i,k: ((P[i] + P[k]) % m).pretty(), # allgemeines Tabellenelement
        rowHeadFn = lambda i: P[i].pretty(),      # Zeilenköpfe
        colHeadFn = lambda k: P[k].pretty(),      # Spaltenköpfe
        cellAlign = "left",
        title = "Addition in Z2[x]x²+x+1", corner = "+")

    printTable(4, 4,
        lambda i,k: ((P[i] * P[k]) % m).pretty(),
        rowHeadFn = lambda i: P[i].pretty(),
        colHeadFn = lambda k: P[k].pretty(),
        cellAlign = "left",
        title = "Multiplikation in Z2[x]x²+x+1", corner = "*")

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:

\mathbb Z_2[x]_{x^2+1} = \{ 0, 1, x, x+1 \}

    m = Poly([1,0,1], 2) # 1 + x²
    # Alle Polynome mod m
    #          0            1              x            1+x
    P = [Poly([0],2), Poly([1],2), Poly([0,1],2), Poly([1,1],2)]

    printTable(4, 4,
        lambda i,k: ((P[i] + P[k]) % m).pretty(),
        rowHeadFn = lambda i: P[i].pretty(),
        colHeadFn = lambda k: P[k].pretty(),
        cellAlign = "left",
        title = "Addition in Z2[x]x²+1", corner = "+")

    printTable(4, 4,
        lambda i,k: ((P[i] * P[k]) % m).pretty(),
        rowHeadFn = lambda i: P[i].pretty(),
        colHeadFn = lambda k: P[k].pretty(),
        cellAlign = "left",
        title = "Multiplikation in Z2[x]x²+1", corner = "*")

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

p(x) = x^3 + x,\; q(x) = x + 1 \; \textrm{in} \; \mathbb Z_2[x]

    p, q = Poly([0,1,0,1], 2), Poly([1,1], 2)
    p + q   # 4.3 a)
    q + q   # 4.3 b)
    p * q   # 4.3 c)

p(x) = x^2 + 2x + 1,\; q(x) = x + 2 \; \textrm{in} \; \mathbb Z_3[x]

    p, q = Poly([1,2,1], 3), Poly([2,1], 3)
    p + q   # 4.3 d)
    p * q   # 4.3 e)

### Teschl: Beispiel 4.5

    # Teschl: Beispiel 4.5 a): Division und Rest:
    print(Poly([0,-2,0,1,3]) / Poly([1,0,1]))
    print(Poly([0,-2,0,1,3]) % Poly([1,0,1]))

    # Teschl: Beispiel 4.5 b)
    print(Poly([-2,1,1]) / Poly([-1,1]))
    print(Poly([-2,1,1]) % Poly([-1,1]))

### Teschl: Beispiel 4.9

    # Teschl: Beispiel 4.9 a)
    a = 4 * Poly([-1,1])^2
    b = 8 * Poly([-1,1])
    Poly.gcd(a, b)

    # Teschl: Beispiel 4.9 b)
    a = Poly([-1,3]) * Poly([2,1])^4
    b = Poly([Rational(-1,3),1]) * Poly([2,5])
    print(a.pretty())
    print(b.pretty())
    print(Poly.gcd(a, b).pretty())

    # Teschl: Beispiel 4.9 c)
    a = 5 * Poly([-1,1])
    b = 5 * Poly([1,1])
    Poly.gcd(a, b)

### Teschl: Beispiel 4.11

    a = Poly([1,-2,0,1])
    b = Poly([-1,0,1])
    Poly.gcd(a, b)

## 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 Z2[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:

    primeList = []
    for i in fromTo(2, 63):
        f = Poly(NumeralSystem.toBase(i, 2, True), 2)
        divisible = False
        # Teiler suchen:
        for p in primeList:
            if f % p == 0:
                divisible = True
                break
        if not divisible:
            primeList.append(f)
            print("{0:3d} --> {1}".format(i, f.pretty()))

## 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 xn + 1:

x^n + 1 = g(x) * h(x)

    # Z_2[x]_x^7+1
    x7_1 = Poly([1,0,0,0,0,0,0,1], 2)

Wir testen, ob g(x) = x4 + x3 + x2 + 1 ein Teiler ist

    g = Poly([1,0,1,1,1], 2)
    print(x7_1 % g)

Ja. g ist das Generatorpolynom, der andere Faktor das Kontrollpolynom.

    h = x7_1 / g
    print(h)

Wir haben den zyklischen Code

C = \{ f(x) * g(x) | f(x) \in \mathbb Z_2[x]_{x^7+1} \}

Da deg(g) = 4 und x7 = 1 in Z2[x]x7+1, kommen für f(x) nur die Polynome vom Grad < 3 in Frage.

    # Beispiel: Codierung des Worts 101 --> f(x) = x² + 1
    m = Poly([1, 0, 1], 2)

    c = m * g % x7_1

    # Probe: Ist c ein gültiges Codewort?
    c * h % x7_1

    # Decodierung
    c / g

    # Alle Codewörter:
    for m in fromTo(0,7):
        f = Poly(NumeralSystem.binary(m, True), 2)
        c = f * g
        print(m, " --> ", c)