Aufgabe 2.6: GF(P hoch m). Welches P, welches m?

Additions– und Multiplikationstabelle

Es soll ein Galoisfeld ${\rm GF}(q)$ mit $q = P^m$ Elementen analysiert werden, das durch die nebenstehenden Tabellen für Addition (gekennzeichnet mit „$+$”) und Multiplikation (gekennzeichnet mit „$\cdot$”) vorgegeben ist. Dieses Galoisfeld

$${\rm GF}(q) = \{\hspace{0.1cm}z_0,\hspace{0.1cm} z_1,\hspace{0.1cm} ... , \hspace{0.1cm}z_{q-1}\}$$

erfüllt alle Anforderungen an einen endlichen Körper, die im Kapitel 2.1 aufgeführt sind. Kommutativ–, Assoziativ– und Distributivgesetz werden erfüllt. Weiterhin gibt es

ein neutrales Element hinsichtlich Addition ⇒ $N_{\rm A}$:

$$\exists \hspace{0.15cm} z_j \in {\rm GF}(q) : \hspace{0.25cm}z_i + z_j = z_i $$

$$\hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_j = N_{\rm A} = {\rm "0"} \hspace{0.25cm}{\rm (Nullelement)} \hspace{0.05cm},$$

ein neutrales Element hinsichtlich Multiplikation ⇒ $N_{\rm M}$:

$$\exists \hspace{0.15cm} z_j \in {\rm GF}(q) : \hspace{0.25cm}z_i \cdot z_j = z_i $$

$$ \Rightarrow \hspace{0.25cm} z_j = N_{\rm M} = {\rm "1"} \hspace{0.25cm}{\rm (Einselement)} \hspace{0.05cm},$$

für alle Elemente $z_i$ eine additive Inverse ⇒ ${\rm Inv_A}(z_i)$:

$$\forall \hspace{0.15cm} z_i \in {\rm GF}(q)\hspace{0.15cm} \exists \hspace{0.15cm} {\rm Inv_A}(z_i) \in {\rm GF}(q):$$

$$z_i + {\rm Inv_A}(z_i) = N_{\rm A} = {\rm "0"}\hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm kurz:}\hspace{0.15cm} {\rm Inv_A}(z_i) = - z_i \hspace{0.05cm}, $$

für alle Elemente $z_i$ mit Ausnahme des Nullelements eine multiplikative Inverse ⇒ ${\rm Inv_M}(z_i)$:

$$\forall \hspace{0.15cm} z_i \in {\rm GF}(q),\hspace{0.15cm} z_i \ne N_{\rm A} \hspace{0.15cm} \exists \hspace{0.15cm} {\rm Inv_M}(z_i) \in {\rm GF}(q):$$

$$z_i \cdot {\rm Inv_M}(z_i) = N_{\rm M} = {\rm "1"} \hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm kurz:}\hspace{0.15cm} {\rm Inv_M}(z_i) = z_i^{-1} \hspace{0.05cm}. $$

Hinweise:

Die Aufgabe bezieht sich auf das Kapitel Erweiterungskörper.
In den Tabellen sind die Elemente $z_0, \ ... \ , \ z_8$ als Koeffizientenvektoren bezeichnet. So steht zum Beispiel „$21$” für die ausführliche Schreibweise $2 \cdot \alpha + 1$.
Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

Musterlösung

(1) Jedes Element besteht aus zwei Ternärzahlen ⇒ $\underline{P = 3}, \ \underline{m = 2}$. Es gibt $q = P^m = 3^8 = \underline{9 \ \rm Elemente}$.

(2) Das neutrale Element der Addition $(N_{\rm A})$ erfüllt für alle $z_i ∈ {\rm GF}(P^m)$ die Bedingung $z_i + N_{\rm A} = z_i$. Aus der Additionstabelle kann abgelesen werden, dass „$00$” diese Bedingung erfült ⇒ Lösungsvorschlag 1.

(3) Das neutrale Element der Multiplikation $(N_{\rm M})$ muss stets die Bedingung $z_i \cdot N_{\rm M} = z_i$ erfüllen. Aus der Multiplikationstabelle ergibt sich $N_{\rm M} = \, „01”$ ⇒ Lösungsvorschlag 2. In der Polynomschreibweise entspricht dies mit $k_1 = 0$ und $k_0 = 1$:

$$k_1 \cdot \alpha + k_0 = 1 \hspace{0.05cm}.$$

(4) Mit der Polynomdarstellung ergeben sich folgende Berechnungen:

$${\rm Inv_A}("02") \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm Inv_A}(2) = (-2) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3 = 1 \hspace{0.25cm}\Rightarrow \hspace{0.25cm}{\rm Vektor}\hspace{0.15cm}"01"\hspace{0.05cm},$$

$${\rm Inv_A}("11") \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm Inv_A}(\alpha + 1) = [(-\alpha) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3] + [(-1) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3] =$$

$$ \hspace{-0.15cm} \ = \ \hspace{-0.15cm}2\alpha + 2 \hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Vektor}\hspace{0.15cm}"22"\hspace{0.05cm},$$

$${\rm Inv_A}("22") \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm Inv_A}(2\alpha + 2) = [(-2\alpha) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3] + [(-2) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3] =$$

$$\hspace{-0.15cm} \ = \ \hspace{-0.15cm}\alpha + 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Vektor}\hspace{0.15cm}"11"\hspace{0.05cm}.$$

Demzufolge sind nur die beiden ersten Lösungsvorschläge richtig. Die Aufgabe kann aber auch ohne Rechnung allein anhand der Additionstabelle gelöst werden. Beispielsweise findet man die Inverse zu „$22$”, indem man in der letzten Zeile die Spalte mit dem Eintrag „$00$” sucht. Man findet die mit „$11$” bezeichnete Spalte und damit ${\rm Inv_A}(„22”) = \, „11”$.

(5) Die Multiplikation von $\alpha$ (Vektor „$10$”) mit sich selbst ergibt $\alpha^2$.

Würde der erste Lösungsvorschlag gültig sein, so müsste sich aus der Bedingung $\alpha^2 + 2 = 0$ und damit $\alpha^2 = (-2) \, {\rm mod} \, 3 = 1$ ergeben, also der Vektor „$01$”.
Geht man vom zweiten Lösungsvorschlag aus, so folgt aus der Bedingung $\alpha^2 + 2\alpha + 2 = 0$ in der Polynomschreibweise

$$\alpha^2 = [(-2\alpha) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3] + [(-2) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3] = \alpha + 1 $$

und damit der Koeffizientenvektor „$11$”.

In der Multiplikationstabelle findet man in Zeile 4, Spalte 4 genau den Eintrag „$11$” → Richtig ist also der Lösungsvorschlag 2.

(6) Die multiplikative Inverse zu „$12$” findet man in der Zeile 6 der Multiplikationstabelle als diejenige Spalte mit dem Eintrag „$01$” ⇒ Der Lösungsvorschlag 2 ist also richtig im Gegensatz zu Vorschlag 3. Es gilt nämlich ${\rm Inv_M}(„21”) = \, „20”$.

Wir überprüfen diese Ergebnisse unter Berücksichtigung von $\alpha^2 + 2\alpha + 2 = 0$ durch Multiplikationen:

$$"12" \cdot "10" \hspace{0.15cm} \ \Rightarrow \ \hspace{0.15cm} (\alpha + 2) \cdot \alpha = \alpha^2 + 2\alpha = (-2\alpha-2) + 2\alpha = -2 \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3 = 1 $$

$$\ \Rightarrow \ {\rm Vektor}\hspace{0.15cm}"01" \hspace{0.15cm} \Rightarrow \hspace{0.15cm}{\rm multiplikative \hspace{0.15cm}Inverse}\hspace{0.05cm}.$$

$$"21" \cdot "12" \hspace{0.15cm} \ \Rightarrow \ \hspace{0.15cm} (2\alpha + 1) \cdot (\alpha + 2) = 2 \alpha^2 + \alpha + 4\alpha + 2 = 2 \alpha^2 + 5\alpha + 2 = $$

$$\ \Rightarrow \ \hspace{0.15cm}2 \cdot (-2\alpha - 2) + 5\alpha + 2 = (\alpha - 2) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3 = \alpha +1 $$

$$\ \Rightarrow \ {\rm Vektor}\hspace{0.15cm}"11" \hspace{0.15cm} \Rightarrow \hspace{0.15cm}{\rm keine \hspace{0.15cm}multiplikative \hspace{0.15cm}Inverse}\hspace{0.05cm}.$$

Der Lösungsvorschlag 1 ist deshalb nicht richtig, weil es für „$00$” keine multiplikative Inverse gibt.

(7) Die beiden Ausdrücke stimmen überein ⇒ Ja, wie die folgenden Berechnungen zeigen:

$$("20" + "12") \ \cdot "12" \hspace{-0.15cm} \ = \ \hspace{-0.15cm} "02"\cdot "12" \hspace{-0.15cm} \ = \ \hspace{-0.15cm} "21"\hspace{0.05cm},$$

$$"20" \cdot "12" + "12" \cdot "12" \hspace{-0.15cm} \ = \ \hspace{-0.15cm} "02" + "22" = "21"\hspace{0.05cm}.$$

Das bedeutet: Das Distributivgesetz wurde zumindest an einem einzigen Beispiel nachgewiesen.

	Das neutrale Element der Addition ist $N_{\rm A} = \, „00”$,
	Das neutrale Element der Addition ist $N_{\rm A} = \, „01”$.

	Das neutrale Element der Multiplikation ist $N_{\rm M} = \, „00”$,
	Das neutrale Element der Multiplikation ist $N_{\rm M} = \, „01”$.

	Es gilt ${\rm Inv_A} \, („02”) = \, „01”$,
	Es gilt ${\rm Inv_A} \, („11”) = \, „22”$,
	Es gilt ${\rm Inv_A} \, („22”) = \, „00”$.

	Die Multiplikation erfolgt modulo $p(\alpha) = \alpha^2 + 2$.
	Die Multiplikation erfolgt modulo $p(\alpha) = \alpha^2 + 2\alpha + 2$.

	Es gibt für alle Elemente $z_i ∈ {\rm GF}(P^m)$ eine multiplikative Inverse.
	Es gilt ${\rm Inv_M}(„12”) = \, „10”$.
	Es gilt ${\rm Inv_M}(„21”) = \, „12”$.

	Ja,
	Nein.