Aufgaben:Aufgabe 2.6: GF(P hoch m). Welches P, welches m?: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(41 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
 
{{quiz-Header|Buchseite=Kanalcodierung/Erweiterungskörper}}
 
{{quiz-Header|Buchseite=Kanalcodierung/Erweiterungskörper}}
  
[[Datei:P_ID2510__KC_A_2_6_neu.png|right|frame|Additions– und Multiplikationstabelle]]
+
[[Datei:P_ID2510__KC_A_2_6_neu.png|right|frame|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 für Addition (gekennzeichnet mit „$+$”) und Multiplikation (gekennzeichnet mit „$\cdot$”) vorgegeben ist. Dieses Galoisfeld
+
Es soll ein Galoisfeld  ${\rm GF}(q)$  mit  $q = P^m$  Elementen analysiert werden,  das durch die nebenstehenden Tabellen definiert ist
:$${\rm GF}(q) = \{\hspace{0.1cm}z_0,\hspace{0.1cm} z_1,\hspace{0.1cm}  ... , \hspace{0.1cm}z_{q-1}\}$$
+
*für Addition  (gekennzeichnet mit „$+$”),  und
  
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 s
+
*für Multiplikation  (gekennzeichnet mit „$\hspace{0.05cm}\cdot\hspace{0.05cm}$”).
* 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 $$
+
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  [[Kanalcodierung/Einige_Grundlagen_der_Algebra|"Einige Grundlagen der Algebra"]]  aufgeführt sind.  So werden auch Kommutativ–, Assoziativ– und Distributivgesetz erfüllt.  
:$$\hspace{0.25cm} \Rightarrow \hspace{0.25cm} z_j = N_{\rm A} = {\rm "0"}  \hspace{0.25cm}{\rm (Nullelement)}
+
 
 +
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},$$
 
\hspace{0.05cm},$$
* ein neutrales Element hinsichtlich Multiplikation  ⇒  $N_{\rm M}$:
+
* ein neutrales Element hinsichtlich Multiplikation   ⇒   $N_{\rm M}$:
:$$\exists \hspace{0.15cm} z_j \in {\rm GF}(q) :
+
:$$\exists \hspace{0.15cm} z_j \in {\rm GF}(q)\text{:}
\hspace{0.25cm}z_i \cdot z_j  = z_i $$
+
\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)}
:$$ \Rightarrow \hspace{0.25cm}   z_j = N_{\rm M} = {\rm "1"} \hspace{0.25cm}{\rm (Einselement)}
 
 
\hspace{0.05cm},$$
 
\hspace{0.05cm},$$
* für alle Elemente $z_i$ eine additive Inverse  ⇒  ${\rm Inv_A}(z_i)$:
+
* 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):$$
+
:$$\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:}\hspace{0.15cm}
+
::$$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}, $$
 
{\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)$:
+
* 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):$$
+
:$$\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"}
+
::$$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}
+
\hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm kurz}\text{:}\hspace{0.15cm}
 
{\rm Inv_M}(z_i) = z_i^{-1}
 
{\rm Inv_M}(z_i) = z_i^{-1}
 
\hspace{0.05cm}. $$
 
\hspace{0.05cm}. $$
  
''Hinweise:''
+
 
* Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Erweiterungsk%C3%B6rper| 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$.
+
 
 +
Hinweise:
 +
* Die Aufgabe gehört zum Kapitel  [[Kanalcodierung/Erweiterungsk%C3%B6rper| "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$”.
 +
  
  
Zeile 36: Zeile 44:
 
===Fragebogen===
 
===Fragebogen===
 
<quiz display=simple>
 
<quiz display=simple>
{Multiple-Choice
+
{Geben Sie die Parameter des hier betrachteten Galoisfeldes an.
 +
|type="{}"}
 +
$P \ = \ ${ 3 }
 +
$m \ = \ ${ 2 }
 +
$q \ = \ ${ 9 }
 +
 
 +
{Wie lautet das neutrale Element für die Addition?
 +
|type="()"}
 +
+ Das neutrale Element der Addition ist&nbsp; $N_{\rm A} = \,$ &bdquo;$0\hspace{0.03cm}0$&rdquo;,
 +
- Das neutrale Element der Addition ist&nbsp; $N_{\rm A} = \,$ &bdquo;$0\hspace{0.03cm}1$&rdquo;.
 +
 
 +
{Wie lautet das neutrale Element für die Multiplikation?
 +
|type="()"}
 +
- Das neutrale Element der Multiplikation ist&nbsp; $N_{\rm M} = \,$ &bdquo;$0\hspace{0.03cm}0$&rdquo;,
 +
+ Das neutrale Element der Multiplikation ist&nbsp; $N_{\rm M} = \,$ &bdquo;$0\hspace{0.03cm}1$&rdquo;.
 +
 
 +
{Welche Aussagen gelten hinsichtlich der additiven Inversen?
 +
|type="[]"}
 +
+ Es gilt&nbsp; ${\rm Inv_A}  ($&bdquo;$0\hspace{0.03cm}2$&rdquo;)  $\, = \, $ &bdquo;$0\hspace{0.03cm}1$&rdquo;,
 +
+ Es gilt&nbsp; ${\rm Inv_A} ($&bdquo;$1\hspace{0.03cm}1$&rdquo;) $\, = \, $ &bdquo;$2\hspace{0.03cm}2$&rdquo;,
 +
- Es gilt&nbsp; ${\rm Inv_A} ($&bdquo;$2\hspace{0.03cm}2$&rdquo;) $\, = \, $ &bdquo;$0\hspace{0.03cm}0$&rdquo;.
 +
 
 +
{Welche der folgenden Aussagen treffen für die Multiplikation zu?
 +
|type="()"}
 +
- Die Multiplikation erfolgt modulo&nbsp; $p(\alpha) = \alpha^2 + 2$.
 +
+ Die Multiplikation erfolgt modulo&nbsp; $p(\alpha) = \alpha^2 + 2\alpha + 2$.
 +
 
 +
{Welche Aussagen gelten hinsichtlich der multiplikativen Inversen?
 
|type="[]"}
 
|type="[]"}
+ correct
+
- Es gibt für alle Elemente&nbsp; $z_i &#8712; {\rm GF}(P^m)$&nbsp; eine multiplikative Inverse.
- false
+
+ Es gilt&nbsp; ${\rm Inv_M}  ($&bdquo;$1\hspace{0.03cm}2$&rdquo;) $\, = \, $ &bdquo;$1\hspace{0.03cm}0$&rdquo;.
 +
- Es gilt&nbsp; ${\rm Inv_A}  ($&bdquo;$2\hspace{0.03cm}1$&rdquo;) $\, = \, $ &bdquo;$1\hspace{0.03cm}2$&rdquo;.
  
{Input-Box Frage
+
{Gilt (&bdquo;$2\hspace{0.03cm}0$&rdquo; $\, + \,$ &bdquo;$1\hspace{0.03cm}2$&rdquo;) $\, \cdot\, $ &bdquo;$1\hspace{0.03cm}2$&rdquo; $\, = \, $&bdquo;$2\hspace{0.03cm}0$&rdquo; $\, \cdot\, $ &bdquo;$1\hspace{0.03cm}2$&rdquo; $\, + \, $&bdquo;$1\hspace{0.03cm}2$&rdquo;  $\, \cdot\, $ &bdquo;$1\hspace{0.03cm}2$&rdquo;?
|type="{}"}
+
|type="()"}
$xyz \ = \ ${ 5.4 3% } $ab$
+
+ Ja.
 +
- Nein.
 
</quiz>
 
</quiz>
  
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp;  
+
'''(1)'''&nbsp; Jedes Element besteht aus zwei Ternärzahlen &nbsp; &#8658; &nbsp; $\underline{P = 3}, \ \underline{m = 2}$.&nbsp; Es gibt $q = P^m = 3^8 = \underline{9 \ \rm Elemente}$.
'''(2)'''&nbsp;  
+
 
'''(3)'''&nbsp;  
+
 
'''(4)'''&nbsp;  
+
'''(2)'''&nbsp; Richtig ist der&nbsp; <u>Lösungsvorschlag 1</u>:
'''(5)'''&nbsp;  
+
*Das neutrale Element der Addition&nbsp; $(N_{\rm A})$&nbsp; erfüllt für alle&nbsp; $z_i &#8712; {\rm GF}(P^m)$&nbsp; die Bedingung&nbsp; $z_i + N_{\rm A} = z_i$.
 +
 +
*Aus der Additionstabelle kann abgelesen werden,&nbsp; dass&nbsp; &bdquo;$0\hspace{0.03cm}0$&rdquo;&nbsp; diese Bedingung erfült.
 +
 
 +
 
 +
'''(3)'''&nbsp; Richtig ist der&nbsp; <u>Lösungsvorschlag 2</u>:
 +
*Das neutrale Element der Multiplikation&nbsp; $(N_{\rm M})$&nbsp; muss stets die Bedingung&nbsp; $z_i \cdot N_{\rm M} = z_i$&nbsp; erfüllen.
 +
 +
*Aus der Multiplikationstabelle ergibt sich&nbsp; $N_{\rm M} = \, &bdquo;0\hspace{0.03cm}1&rdquo;$.
 +
 
 +
* In der Polynomschreibweise entspricht dies mit&nbsp; $k_1 = 0$&nbsp; und&nbsp; $k_0 = 1$:
 +
:$$k_1 \cdot \alpha + k_0 = 1 \hspace{0.05cm}.$$
 +
 
 +
 
 +
'''(4)'''&nbsp; Mit der Polynomdarstellung ergeben sich folgende Berechnungen:
 +
:$${\rm Inv_A}(&bdquo;\hspace{-0.05cm}0\hspace{0.03cm}2&rdquo;) \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}&bdquo;\hspace{-0.05cm}0\hspace{0.03cm}1&rdquo;\hspace{0.05cm},$$
 +
:$${\rm Inv_A}(&bdquo;\hspace{-0.05cm}1\hspace{0.03cm}1&rdquo;)\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}&bdquo;\hspace{-0.05cm}2\hspace{0.03cm}2&rdquo;\hspace{0.05cm},$$
 +
:$${\rm Inv_A}(&bdquo;\hspace{-0.05cm}2\hspace{0.03cm}2&rdquo;)\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}&bdquo;\hspace{-0.05cm}1\hspace{0.03cm}1&rdquo;\hspace{0.05cm}.$$
 +
 
 +
Demzufolge sind nur die <u>beiden ersten Lösungsvorschläge</u> richtig.
 +
 
 +
Die Aufgabe kann aber auch ohne Rechnung allein anhand der Additionstabelle gelöst werden.
 +
*Beispielsweise findet man die Inverse zu &bdquo;$2\hspace{0.03cm}2$&rdquo;,&nbsp; indem man in der letzten Zeile die Spalte mit dem Eintrag&nbsp; &bdquo;$0\hspace{0.03cm}0$&rdquo;&nbsp; sucht.
 +
 +
*Man findet die mit&nbsp; &bdquo;$1\hspace{0.03cm}1$&rdquo;&nbsp; bezeichnete Spalte und damit&nbsp; ${\rm Inv_A}(&bdquo;2\hspace{0.03cm}2&rdquo;) = \, &bdquo;1\hspace{0.03cm}1&rdquo;$.
 +
 
 +
 
 +
'''(5)'''&nbsp; Die Multiplikation von&nbsp; $\alpha$&nbsp; $($Vektor &bdquo;$1\hspace{0.03cm}0$&rdquo;$)$&nbsp; mit sich selbst ergibt&nbsp; $\alpha^2$.
 +
* Würde der erste Lösungsvorschlag gültig sein,&nbsp; so müsste sich aus der Bedingung&nbsp; $\alpha^2 + 2 = 0$&nbsp; und damit&nbsp; $\alpha^2 = (-2) \, {\rm mod} \, 3 = 1$&nbsp; ergeben,&nbsp; also der Vektor &bdquo;$0\hspace{0.03cm}1$&rdquo;.
 +
 
 +
* Geht man vom zweiten Lösungsvorschlag aus,&nbsp; so folgt aus der Bedingung&nbsp; $\alpha^2 + 2\alpha + 2 = 0$&nbsp; 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&nbsp; &bdquo;$1\hspace{0.03cm}1$&rdquo;.
 +
 
 +
In der Multiplikationstabelle findet man in Zeile 4, Spalte 4 genau den Eintrag &bdquo;$1\hspace{0.03cm}1$&rdquo; &nbsp; &rArr; &nbsp; Richtig ist also der&nbsp; <u>Lösungsvorschlag 2</u>.
 +
 
 +
 
 +
'''(6)'''&nbsp; Die multiplikative Inverse zu&nbsp; &bdquo;$1\hspace{0.03cm}2$&rdquo;&nbsp; findet man in der Zeile 6 der Multiplikationstabelle als diejenige Spalte mit dem Eintrag &bdquo;$0\hspace{0.03cm}1$&rdquo; &nbsp;<br>&#8658;&nbsp; Der&nbsp; <u>Lösungsvorschlag 2</u>&nbsp; ist also richtig im Gegensatz zu Vorschlag 3.&nbsp; Es gilt nämlich ${\rm Inv_M}(&bdquo;21&rdquo;) = \, &bdquo;2\hspace{0.03cm}0&rdquo;$.
 +
 
 +
Wir überprüfen diese Ergebnisse unter Berücksichtigung von&nbsp; $\alpha^2 + 2\alpha + 2 = 0$&nbsp; durch Multiplikationen:
 +
:$$&bdquo;\hspace{-0.1cm}1\hspace{0.03cm}2&rdquo; \hspace{0.05cm}\cdot \hspace{0.05cm}&bdquo;\hspace{-0.1cm}1\hspace{0.03cm}0&rdquo; \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}&bdquo;\hspace{-0.1cm}0\hspace{0.03cm}1&rdquo; \hspace{0.15cm} \Rightarrow  \hspace{0.15cm}{\rm multiplikative \hspace{0.15cm}Inverse}\hspace{0.05cm}.$$
 +
:$$&bdquo;\hspace{-0.1cm}2\hspace{0.03cm}1&rdquo; \hspace{0.05cm}\cdot \hspace{0.05cm}&bdquo;\hspace{-0.1cm}1\hspace{0.03cm}2&rdquo;
 +
\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}&bdquo;\hspace{-0.1cm}1\hspace{0.03cm}1&rdquo; \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 &bdquo;$00$&rdquo; keine multiplikative Inverse gibt.
 +
 
 +
 
 +
'''(7)'''&nbsp; Die beiden Ausdrücke stimmen überein &nbsp; &#8658; &nbsp; <u>JA</u>,&nbsp; wie die folgenden Berechnungen zeigen:
 +
:$$(&bdquo;\hspace{-0.1cm}20&rdquo; + \ &bdquo;\hspace{-0.1cm}12&rdquo;) \ \cdot \ &bdquo;\hspace{-0.1cm}12&rdquo; \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \ &bdquo;\hspace{-0.1cm}02&rdquo;\cdot \ &bdquo;\hspace{-0.1cm}12&rdquo; \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \ &bdquo;\hspace{-0.1cm}21&rdquo;\hspace{0.05cm},$$
 +
:$$&bdquo;\hspace{-0.1cm}20&rdquo; \cdot  \ &bdquo;\hspace{-0.1cm}12&rdquo; + \ &bdquo;\hspace{-0.1cm}12&rdquo; \cdot \ &bdquo;\hspace{-0.1cm}12&rdquo; \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \ &bdquo;\hspace{-0.1cm}02&rdquo; + \ &bdquo;\hspace{-0.1cm}22&rdquo; \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \ &bdquo;\hspace{-0.1cm}21&rdquo;\hspace{0.05cm}.$$
 +
 
 +
Das bedeutet: &nbsp; Das Distributivgesetz wurde zumindest an einem einzigen Beispiel nachgewiesen.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 4. Oktober 2022, 15:30 Uhr

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:

  • 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:

$$„\hspace{-0.1cm}1\hspace{0.03cm}2” \hspace{0.05cm}\cdot \hspace{0.05cm}„\hspace{-0.1cm}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}„\hspace{-0.1cm}0\hspace{0.03cm}1” \hspace{0.15cm} \Rightarrow \hspace{0.15cm}{\rm multiplikative \hspace{0.15cm}Inverse}\hspace{0.05cm}.$$
$$„\hspace{-0.1cm}2\hspace{0.03cm}1” \hspace{0.05cm}\cdot \hspace{0.05cm}„\hspace{-0.1cm}1\hspace{0.03cm}2” \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}„\hspace{-0.1cm}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:

$$(„\hspace{-0.1cm}20” + \ „\hspace{-0.1cm}12”) \ \cdot \ „\hspace{-0.1cm}12” \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \ „\hspace{-0.1cm}02”\cdot \ „\hspace{-0.1cm}12” \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \ „\hspace{-0.1cm}21”\hspace{0.05cm},$$
$$„\hspace{-0.1cm}20” \cdot \ „\hspace{-0.1cm}12” + \ „\hspace{-0.1cm}12” \cdot \ „\hspace{-0.1cm}12” \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \ „\hspace{-0.1cm}02” + \ „\hspace{-0.1cm}22” \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \ „\hspace{-0.1cm}21”\hspace{0.05cm}.$$

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