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

From LNTwww

Zugrunde liegende Tabellen für Addition und Multiplikation

Es soll ein Galoisfeld  ${\rm GF}(q)$  mit  $q = P^m$  Elementen analysiert werden, das durch die nebenstehenden Tabellen definiert ist

  • für Addition  (gekennzeichnet mit "$+$"),  und
  • für Multiplikation  (gekennzeichnet mit "$\hspace{0.05cm}\cdot\hspace{0.05cm}$").


Dieses Galoisfeld  ${\rm GF}(q) = \{\hspace{0.1cm}z_0,\hspace{0.1cm} z_1,\hspace{0.05cm} \text{...} , \hspace{0.1cm}z_{q-1}\}$  erfüllt alle Anforderungen an einen endlichen Körper, die im Kapitel  Einige Grundlagen der Algebra  aufgeführt sind. So werden auch Kommutativ–, Assoziativ– und Distributivgesetz erfüllt.

Weiterhin gibt es

  • ein neutrales Element hinsichtlich Addition   ⇒   $N_{\rm A}$:
$$\exists \hspace{0.15cm} z_j \in {\rm GF}(q)\text{:} \hspace{0.25cm}z_i + z_j = z_i \hspace{0.3cm} \Rightarrow \hspace{0.3cm} z_j = N_{\rm A} \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)\text{:} \hspace{0.25cm}z_i \cdot z_j = z_i \hspace{0.3cm} \Rightarrow \hspace{0.3cm} z_j = N_{\rm M} \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)\text{:}$$
$$z_i + {\rm Inv_A}(z_i) = N_{\rm A} = {\rm "0"}\hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm kurz}\text{:}\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)\text{:}$$
$$z_i \cdot {\rm Inv_M}(z_i) = N_{\rm M} = {\rm "1"} \hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm kurz}\text{:}\hspace{0.15cm} {\rm Inv_M}(z_i) = z_i^{-1} \hspace{0.05cm}. $$





Hinweise:

  • Die Aufgabe gehört zum Kapitel  Erweiterungskörper.
  • In den Tabellen sind die Elemente  $z_0, \hspace{0.05cm} \text{...} \hspace{0.1cm} , \ z_8$  als Koeffizientenvektoren bezeichnet. Zum Beispiel steht "$2\hspace{0.03cm}1$" für "$2 \cdot \alpha + 1$".



Fragebogen

1

Geben Sie die Parameter des hier betrachteten Galoisfeldes an.

$P \ = \ $

$m \ = \ $

$q \ = \ $

2

Wie lautet das neutrale Element für die Addition?

Das neutrale Element der Addition ist  $N_{\rm A} = \,$ "$0\hspace{0.03cm}0$",
Das neutrale Element der Addition ist  $N_{\rm A} = \,$ "$0\hspace{0.03cm}1$".

3

Wie lautet das neutrale Element für die Multiplikation?

Das neutrale Element der Multiplikation ist  $N_{\rm M} = \,$ "$0\hspace{0.03cm}0$",
Das neutrale Element der Multiplikation ist  $N_{\rm M} = \,$ "$0\hspace{0.03cm}1$".

4

Welche Aussagen gelten hinsichtlich der additiven Inversen?

Es gilt  ${\rm Inv_A} ($"$0\hspace{0.03cm}2$") $\, = \, $ "$0\hspace{0.03cm}1$",
Es gilt  ${\rm Inv_A} ($"$1\hspace{0.03cm}1$") $\, = \, $ "$2\hspace{0.03cm}2$",
Es gilt  ${\rm Inv_A} ($"$2\hspace{0.03cm}2$") $\, = \, $ "$0\hspace{0.03cm}0$".

5

Welche der folgenden Aussagen treffen für die Multiplikation zu?

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

6

Welche Aussagen gelten hinsichtlich der multiplikativen Inversen?

Es gibt für alle Elemente  $z_i ∈ {\rm GF}(P^m)$  eine multiplikative Inverse.
Es gilt  ${\rm Inv_M} ($"$1\hspace{0.03cm}2$") $\, = \, $ "$1\hspace{0.03cm}0$".
Es gilt  ${\rm Inv_A} ($"$2\hspace{0.03cm}1$") $\, = \, $ "$1\hspace{0.03cm}2$".

7

Gilt ("$2\hspace{0.03cm}0$" $\, + \,$ "$1\hspace{0.03cm}2$") $\, \cdot\, $ "$1\hspace{0.03cm}2$" $\, = \, $"$2\hspace{0.03cm}0$" $\, \cdot\, $ "$1\hspace{0.03cm}2$" $\, + \, $"$1\hspace{0.03cm}2$" $\, \cdot\, $ "$1\hspace{0.03cm}2$"?

Ja.
Nein.


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)  Richtig ist der Lösungsvorschlag 1:

  • 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 "$0\hspace{0.03cm}0$" diese Bedingung erfült.


(3)  Richtig ist der Lösungsvorschlag 2:

  • 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} = \, "0\hspace{0.03cm}1"$.
  • 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}("\hspace{-0.05cm}0\hspace{0.03cm}2") \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}"\hspace{-0.05cm}0\hspace{0.03cm}1"\hspace{0.05cm},$$
$${\rm Inv_A}("\hspace{-0.05cm}1\hspace{0.03cm}1")\hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm Inv_A}(\alpha + 1) = \big[(-\alpha) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3\big] + \big[(-1) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3\big] =2\alpha + 2 \hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Vektor}\hspace{0.15cm}"\hspace{-0.05cm}2\hspace{0.03cm}2"\hspace{0.05cm},$$
$${\rm Inv_A}("\hspace{-0.05cm}2\hspace{0.03cm}2")\hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm Inv_A}(2\alpha + 2) = \big[(-2\alpha) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3\big] + \big[(-2) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3\big] =\alpha + 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Vektor}\hspace{0.15cm}"\hspace{-0.05cm}1\hspace{0.03cm}1"\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 "$2\hspace{0.03cm}2$", indem man in der letzten Zeile die Spalte mit dem Eintrag "$0\hspace{0.03cm}0$" sucht.
  • Man findet die mit "$1\hspace{0.03cm}1$" bezeichnete Spalte und damit ${\rm Inv_A}("2\hspace{0.03cm}2") = \, "1\hspace{0.03cm}1"$.


(5)  Die Multiplikation von $\alpha$ (Vektor "$1\hspace{0.03cm}0$") 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 "$0\hspace{0.03cm}1$".
  • 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 "$1\hspace{0.03cm}1$".

In der Multiplikationstabelle findet man in Zeile 4, Spalte 4 genau den Eintrag "$1\hspace{0.03cm}1$" → Richtig ist also der Lösungsvorschlag 2.


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

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

$$"1\hspace{0.03cm}2" \hspace{0.05cm}\cdot \hspace{0.05cm}"1\hspace{0.03cm}0" \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 \hspace{0.15cm} \Rightarrow \hspace{0.15cm} {\rm Vektor}\hspace{0.15cm}"0\hspace{0.03cm}1" \hspace{0.15cm} \Rightarrow \hspace{0.15cm}{\rm multiplikative \hspace{0.15cm}Inverse}\hspace{0.05cm}.$$
$$"2\hspace{0.03cm}1" \hspace{0.05cm}\cdot \hspace{0.05cm}"1\hspace{0.03cm}2" "21" \hspace{0.05cm}\cdot \hspace{0.05cm} "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 = 2 \cdot (-2\alpha - 2) + 5\alpha + 2 = (\alpha - 2) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3 = \alpha +1 $$
$$\hspace{2.725cm} \Rightarrow \ {\rm Vektor}\hspace{0.15cm}"1\hspace{0.03cm}1" \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" \hspace{-0.15cm} \ = \ \hspace{-0.15cm} "21"\hspace{0.05cm}.$$

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