Polynome über GF(5): Summe, Produkt und Inverse

Die Aufgabe

In der Datencodierung spielen Polynome über endlichen Körpern eine wichtige Rolle. Man definiert: Sei K ein endlicher Körper, dann heißt

P(x) = a_n x^n + a_{n-1} x^{n-1} + a_{n-2} x^{n-2} + \dots + a_1 x + a_0 \quad \text{mit } a_i \in K,\ i = 0, 1, 2, \dots, n

ein Polynom über $K$ mit der Variablen $x$ . Die $a_i$ heißen Koeffizienten von $P(x)$ .

Sei im Folgenden $K[x]$ die Menge aller Polynome über $K$ . Dann kann in gewohnter Weise eine Addition und eine Multiplikation auf $K[x]$ definiert werden. Sei im Folgenden $K = \mathbb{Z}_5$ .

a) Geben Sie die Verknüpfungstabellen für Addition (+) und Multiplikation ( $\cdot$ ) des Galois-Feldes GF(5) an.
b) Welche algebraische Struktur hat der Raum $(\mathbb{Z}_5[x], +, \cdot)$ ?
c) Seien $A(x), B(x) \in K[x]$ mit

\begin{aligned} A(x) &= 2x^4 + 2x^3 + x^2 + 4 \\ B(x) &= x^3 + 2x^2 + 3x + 1. \end{aligned}

Berechnen Sie $A + B$ und $A \cdot B$ .
d) Gibt es Polynome $A_{+}^{-1}$ und $B_{+}^{-1}$ (additive Inverse) mit der Eigenschaft $A + A_{+}^{-1} = A_{+}^{-1} + A = 0$ bzw. $B + B_{+}^{-1} = B_{+}^{-1} + B = 0$ ? Falls ja, wie lauten $A_{+}^{-1}$ und $B_{+}^{-1}$ ? Falls nein, warum gibt es diese nicht?
e) Gibt es Polynome $A_{\cdot}^{-1}$ und $B_{\cdot}^{-1}$ (multiplikative Inverse) mit der Eigenschaft $A \cdot A_{\cdot}^{-1} = A_{\cdot}^{-1} \cdot A = 1$ bzw. $B \cdot B_{\cdot}^{-1} = B_{\cdot}^{-1} \cdot B = 1$ ? Falls ja, wie lauten $A_{\cdot}^{-1}$ und $B_{\cdot}^{-1}$ ? Falls nein, warum gibt es diese nicht?

Gegeben sind Polynome, deren Koeffizienten aus $\mathbb{Z}_5$ stammen. Der Koeffizient ist die Zahl vor einer Potenz von $x$ : In $2x^4$ ist 2 der Koeffizient von $x^4$ . Was $\mathbb{Z}_5$ ist, klärt Teil a).

Aus Ü2 A2 („Der Vektorraum ℤ₃ × ℤ₃: Rechnen mit Resten“): In

\mathbb{Z}_3

rechnet man wie gewohnt und nimmt am Ende den Rest bei Division durch 3. Hier geschieht dasselbe mit der Zahl 5 statt 3. Ein Körper ist eine Zahlenmenge, in der man addieren, subtrahieren, multiplizieren und durch jede Zahl außer 0 teilen kann.

Gesucht ist in fünf Teilen:

a) Die Rechentafeln von $\mathbb{Z}_5$ : Wie addiert und wie multipliziert man dort?

b) Welche Struktur haben die Polynome mit Addition und Multiplikation? Gemeint ist die Frage, welche Rechengesetze gelten.

c) Zwei konkrete Rechnungen: $A + B$ und $A \cdot B$ .

d) Gibt es zu $A$ und $B$ ein Polynom, das man addieren kann, sodass 0 herauskommt?

e) Gibt es zu $A$ und $B$ ein Polynom, das man multiplizieren kann, sodass 1 herauskommt?

Merke: Man rechnet mit den Polynomen wie gewohnt. Jede Rechnung mit Koeffizienten führt aber zum Rest bei Division durch 5.

GF(5) ist ℤ₅ = {0, 1, 2, 3, 4}

Beispiele: die Zahlen von 5 bis 8 und ihr Rest bei Division durch 5

\begin{aligned} 5 &= 1 \cdot 5 + 0 &&\Rightarrow\ 5 = 0 \\ 6 &= 1 \cdot 5 + 1 &&\Rightarrow\ 6 = 1 \\ 7 &= 1 \cdot 5 + 2 &&\Rightarrow\ 7 = 2 \\ 8 &= 1 \cdot 5 + 3 &&\Rightarrow\ 8 = 3 \end{aligned}

Die fünf Elemente

\mathbb{Z}_5 = \{0, 1, 2, 3, 4\}

GF(5) steht für „Galois-Feld mit 5 Elementen“. Ein Galois-Feld ist ein Körper mit endlich vielen Zahlen, benannt nach dem Mathematiker Évariste Galois. Es ist derselbe Körper wie $\mathbb{Z}_5$ aus der Aufgabe, nur mit anderem Namen.

$\mathbb{Z}_5$ sind die Reste bei Division durch 5. Teilt man eine ganze Zahl durch 5, bleibt als Rest 0, 1, 2, 3 oder 4. Einen anderen Rest gibt es nicht. Darum hat $\mathbb{Z}_5$ genau fünf Elemente.

Zwei ganze Zahlen mit demselben Rest zählen als dieselbe Zahl: Die 5 hat Rest 0, also ist $5 = 0$ . Die 7 hat Rest 2, also ist $7 = 2$ . Dass $\mathbb{Z}_5$ ein Körper ist, liegt an der Primzahl 5. Das prüfen wir in Schritt 4 an den Tafeln.

Merke: In

\mathbb{Z}_5

ist

5 = 0

. Jede Zahl wird durch ihren Rest bei Division durch 5 ersetzt.

Die Tafel der Addition

Regel

x + y = \text{Rest von } (x + y) \text{ bei Division durch } 5 \qquad (x, y \in \mathbb{Z}_5)

Beispiele

\begin{aligned} 2 + 2 &= 4 \\ 2 + 3 &= 5 = 0 \\ 4 + 3 &= 7 = 2 \\ 4 + 4 &= 8 = 3 \end{aligned}

+	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

Die Addition hat zwei Schritte. Erst addiert man ganz normal. Dann ersetzt man das Ergebnis durch seinen Rest bei Division durch 5, damit es wieder in $\{0, 1, 2, 3, 4\}$ liegt.

Beispiel $4 + 3$ : Normal ist das 7. Der Rest von 7 bei Division durch 5 ist 2, denn $7 = 1 \cdot 5 + 2$ . Also gilt $4 + 3 = 2$ . Die Tafel enthält alle 25 Summen: Die Zeile nennt den ersten, die Spalte den zweiten Summanden. Man trägt jede Summe so ein.

Polynome über GF(5): Summe, Produkt und Inverse

Die Aufgabe

GF(5) ist ℤ₅ = {0, 1, 2, 3, 4}

Die Tafel der Addition

Die Rechentafeln von ℤ₅

Abbildung 1Die Rechentafeln von ℤ₅

Schritt 0Die Aufgabe

Schritt 1GF(5) ist ℤ₅ = {0, 1, 2, 3, 4}

Schritt 2Die Tafel der Addition

Die Rechentafeln von ℤ₅

Abbildung 1Die Rechentafeln von ℤ₅

Die Aufgabe

GF(5) ist ℤ₅ = {0, 1, 2, 3, 4}

Die Tafel der Addition