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

Aus LNTwww
Wechseln zu:Navigation, Suche
K (Textersetzung - „* Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.“ durch „ “)
 
(4 dazwischenliegende Versionen desselben Benutzers 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|Zugrunde liegende Tabellen für Additions und Multiplikation]]
+
[[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 definiert ist  
+
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 Addition  (gekennzeichnet mit „$+$”),  und
*für Multiplikation (gekennzeichnet mit „$\cdot$”).
 
  
 +
*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 [[Kanalcodierung/Einige_Grundlagen_der_Algebra|Einige Grundlagen der Algebra]] aufgeführt sind. Kommutativ–, Assoziativ– und Distributivgesetz werden erfüllt. Weiterhin gibt es
+
 
 +
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.  
 +
 
 +
Weiterhin gibt es
 
* ein neutrales Element hinsichtlich Addition   ⇒   $N_{\rm A}$:
 
* ein neutrales Element hinsichtlich Addition   ⇒   $N_{\rm A}$:
 
:$$\exists \hspace{0.15cm} z_j \in {\rm GF}(q)\text{:}
 
:$$\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} = {\rm "0"}  \hspace{0.25cm}{\rm (Nullelement)}
+
\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)\text{:}
 
:$$\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} = {\rm "1"} \hspace{0.25cm}{\rm (Einselement)}
+
\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},$$
 
\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)\text{:}$$
 
:$$\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}
 
::$$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)\text{:}$$
 
:$$\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"}
Zeile 30: Zeile 33:
  
  
''Hinweise:''
+
Hinweise:
* Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Erweiterungsk%C3%B6rper| Erweiterungskörper]].  
+
* 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 „$21$” für „$2 \cdot \alpha + 1$”.
+
 +
* 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 48: Zeile 52:
 
{Wie lautet das neutrale Element für die Addition?
 
{Wie lautet das neutrale Element für die Addition?
 
|type="()"}
 
|type="()"}
+ Das neutrale Element der Addition ist $N_{\rm A} = \,$ „$00$”,
+
+ Das neutrale Element der Addition ist  $N_{\rm A} = \,$ „$0\hspace{0.03cm}0$”,
- Das neutrale Element der Addition ist $N_{\rm A} = \,$ „$01$”.
+
- Das neutrale Element der Addition ist  $N_{\rm A} = \,$ „$0\hspace{0.03cm}1$”.
  
 
{Wie lautet das neutrale Element für die Multiplikation?
 
{Wie lautet das neutrale Element für die Multiplikation?
 
|type="()"}
 
|type="()"}
- Das neutrale Element der Multiplikation ist $N_{\rm M} = \,$ „$00$”,
+
- Das neutrale Element der Multiplikation ist  $N_{\rm M} = \,$ „$0\hspace{0.03cm}0$”,
+ Das neutrale Element der Multiplikation ist $N_{\rm M} = \,$ „$01$”.
+
+ Das neutrale Element der Multiplikation ist  $N_{\rm M} = \,$ „$0\hspace{0.03cm}1$”.
  
 
{Welche Aussagen gelten hinsichtlich der additiven Inversen?
 
{Welche Aussagen gelten hinsichtlich der additiven Inversen?
 
|type="[]"}
 
|type="[]"}
+ Es gilt ${\rm Inv_A}  ($„$02$”) $= \,$ „$01$”,
+
+ Es gilt  ${\rm Inv_A}  ($„$0\hspace{0.03cm}2$”) $\, = \, $ „$0\hspace{0.03cm}1$”,
+ Es gilt ${\rm Inv_A} ($„$11$”) $= \,$ „$22$”,
+
+ Es gilt  ${\rm Inv_A} ($„$1\hspace{0.03cm}1$”) $\, = \, $ „$2\hspace{0.03cm}2$”,
- Es gilt ${\rm Inv_A} ($„$22$”) $= \,$ „$00$”.
+
- Es gilt  ${\rm Inv_A} ($„$2\hspace{0.03cm}2$”) $\, = \, $ „$0\hspace{0.03cm}0$”.
  
 
{Welche der folgenden Aussagen treffen für die Multiplikation zu?
 
{Welche der folgenden Aussagen treffen für die Multiplikation zu?
|type="[]"}
+
|type="()"}
- Die Multiplikation erfolgt modulo $p(\alpha) = \alpha^2 + 2$.
+
- Die Multiplikation erfolgt modulo  $p(\alpha) = \alpha^2 + 2$.
+ Die Multiplikation erfolgt modulo $p(\alpha) = \alpha^2 + 2\alpha + 2$.
+
+ Die Multiplikation erfolgt modulo  $p(\alpha) = \alpha^2 + 2\alpha + 2$.
  
 
{Welche Aussagen gelten hinsichtlich der multiplikativen Inversen?
 
{Welche Aussagen gelten hinsichtlich der multiplikativen Inversen?
 
|type="[]"}
 
|type="[]"}
- Es gibt für alle Elemente $z_i ∈ {\rm GF}(P^m)$ eine multiplikative Inverse.
+
- 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}  ($„$1\hspace{0.03cm}2$”) $\, = \, $ „$1\hspace{0.03cm}0$”.
- Es gilt ${\rm Inv_A}  ($„$21$”) $= \,$ „$12$”.
+
- Es gilt  ${\rm Inv_A}  ($„$2\hspace{0.03cm}1$”) $\, = \, $ „$1\hspace{0.03cm}2$”.
  
{Gilt („$20$” $\, + \,$ „$12$”) $\, \cdot\, $ („$12$”) $= \,$„$20$” $\, \cdot\, $ „$12$” $\, + \, $„$12$”  $\, \cdot\, $ „$12$”?
+
{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$”?
 
|type="()"}
 
|type="()"}
 
+ Ja.
 
+ Ja.
Zeile 81: Zeile 85:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(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}$.
+
'''(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)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 1</u>:
+
'''(2)'''&nbsp; Richtig ist der&nbsp; <u>Lösungsvorschlag 1</u>:
*Das neutrale Element der Addition $(N_{\rm A})$ erfüllt für alle $z_i &#8712; {\rm GF}(P^m)$ die Bedingung $z_i + N_{\rm A} = z_i$.  
+
*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, dass &bdquo;$00$&rdquo; diese Bedingung erfült.
+
 +
*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 <u>Lösungsvorschlag 2</u>:
+
'''(3)'''&nbsp; Richtig ist der&nbsp; <u>Lösungsvorschlag 2</u>:
*Das neutrale Element der Multiplikation $(N_{\rm M})$ muss stets die Bedingung $z_i \cdot N_{\rm M} = z_i$ erfüllen.  
+
*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 $N_{\rm M} = \, &bdquo;01&rdquo;$.
+
* In der Polynomschreibweise entspricht dies mit $k_1 = 0$ und $k_0 = 1$:
+
*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}.$$
 
:$$k_1 \cdot \alpha + k_0 = 1 \hspace{0.05cm}.$$
  
  
 
'''(4)'''&nbsp; Mit der Polynomdarstellung ergeben sich folgende Berechnungen:
 
'''(4)'''&nbsp; 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}(&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}("11") \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm Inv_A}(\alpha + 1) = [(-\alpha) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3] +  
+
:$${\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] +  
[(-1) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3] =2\alpha + 2 \hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Vektor}\hspace{0.15cm}"22"\hspace{0.05cm},$$
+
\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}("22") \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm Inv_A}(2\alpha + 2) = [(-2\alpha) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3] +  
+
:$${\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] +  
[(-2) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3] =\alpha + 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Vektor}\hspace{0.15cm}"11"\hspace{0.05cm}.$$
+
\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.  
 
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.  
 
Die Aufgabe kann aber auch ohne Rechnung allein anhand der Additionstabelle gelöst werden.  
*Beispielsweise findet man die Inverse zu &bdquo;$22$&rdquo;, indem man in der letzten Zeile die Spalte mit dem Eintrag &bdquo;$00$&rdquo; sucht.  
+
*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 &bdquo;$11$&rdquo; bezeichnete Spalte und damit ${\rm Inv_A}(&bdquo;22&rdquo;) = \, &bdquo;11&rdquo;$.
+
 +
*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;.
  
'''(5)'''&nbsp; Die Multiplikation von $\alpha$ (Vektor &bdquo;$10$&rdquo;) mit sich selbst ergibt $\alpha^2$.
+
* Geht man vom zweiten Lösungsvorschlag aus,&nbsp; so folgt aus der Bedingung&nbsp; $\alpha^2 + 2\alpha + 2 = 0$&nbsp; in der Polynomschreibweise
* 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 &bdquo;$01$&rdquo;.
 
* 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 $$
 
:$$\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 &bdquo;$11$&rdquo;.
+
: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;$11$&rdquo; &#8594; Richtig ist also der <u>Lösungsvorschlag 2</u>.
+
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 &bdquo;$12$&rdquo; findet man in der Zeile 6 der Multiplikationstabelle als diejenige Spalte mit dem Eintrag &bdquo;$01$&rdquo; &nbsp;&#8658;&nbsp; Der <u>Lösungsvorschlag 2</u> ist also richtig im Gegensatz zu Vorschlag 3. Es gilt nämlich ${\rm Inv_M}(&bdquo;21&rdquo;) = \, &bdquo;20&rdquo;$.
+
'''(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 $\alpha^2 + 2\alpha + 2 = 0$ durch Multiplikationen:
+
Wir überprüfen diese Ergebnisse unter Berücksichtigung von&nbsp; $\alpha^2 + 2\alpha + 2 = 0$&nbsp; 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 \hspace{0.15cm} \Rightarrow  \hspace{0.15cm} {\rm Vektor}\hspace{0.15cm}"01" \hspace{0.15cm} \Rightarrow  \hspace{0.15cm}{\rm multiplikative \hspace{0.15cm}Inverse}\hspace{0.05cm}.$$
+
:$$&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}.$$
:$$"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 = 2 \cdot (-2\alpha  - 2) + 5\alpha  + 2 = (\alpha  - 2) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3 =  \alpha  +1 $$
+
:$$&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{2.725cm} \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}.$$
+
\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.
 
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>, wie die folgenden Berechnungen zeigen:
+
'''(7)'''&nbsp; Die beiden Ausdrücke stimmen überein &nbsp; &#8658; &nbsp; <u>JA</u>,&nbsp; 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},$$
+
:$$(&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},$$
:$$"20" \cdot  "12" + "12" \cdot "12" \hspace{-0.15cm} \ = \ \hspace{-0.15cm} "02" + "22" \hspace{-0.15cm} \ = \ \hspace{-0.15cm} "21"\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: Das Distributivgesetz wurde zumindest an einem einzigen Beispiel nachgewiesen.
+
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.