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 i­n 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 i­n 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)