Difference between revisions of "Aufgaben:Exercise 2.6: GF(P power m). Which P, which m?"

From LNTwww
Line 46: Line 46:
 
===Fragebogen===
 
===Fragebogen===
 
<quiz display=simple>
 
<quiz display=simple>
−
{Geben Sie die Parameter des hier betrachteten Galoisfeldes an.
+
{Specify the parameters of the Galois field considered here.
 
|type="{}"}
 
|type="{}"}
 
$P \ = \ ${ 3 }
 
$P \ = \ ${ 3 }
Line 52: Line 52:
 
$q \ = \ ${ 9 }
 
$q \ = \ ${ 9 }
  
−
{Wie lautet das neutrale Element für die Addition?
+
{What is the neutral element of addition?
 
|type="()"}
 
|type="()"}
 
+ Das neutrale Element der Addition ist&nbsp; $N_{\rm A} = \,$ "$0\hspace{0.03cm}0$",
 
+ Das neutrale Element der Addition ist&nbsp; $N_{\rm A} = \,$ "$0\hspace{0.03cm}0$",
 
- Das neutrale Element der Addition ist&nbsp; $N_{\rm A} = \,$ "$0\hspace{0.03cm}1$".
 
- Das neutrale Element der Addition ist&nbsp; $N_{\rm A} = \,$ "$0\hspace{0.03cm}1$".
  
−
{Wie lautet das neutrale Element für die Multiplikation?
+
{What is the neutral element of multiplication?
 
|type="()"}
 
|type="()"}
 
- Das neutrale Element der Multiplikation ist&nbsp; $N_{\rm M} = \,$ "$0\hspace{0.03cm}0$",
 
- Das neutrale Element der Multiplikation ist&nbsp; $N_{\rm M} = \,$ "$0\hspace{0.03cm}0$",
 
+ Das neutrale Element der Multiplikation ist&nbsp; $N_{\rm M} = \,$ "$0\hspace{0.03cm}1$".
 
+ Das neutrale Element der Multiplikation ist&nbsp; $N_{\rm M} = \,$ "$0\hspace{0.03cm}1$".
  
−
{Welche Aussagen gelten hinsichtlich der additiven Inversen?
+
{What statements are true regarding additive inverses?
 
|type="[]"}
 
|type="[]"}
 
+ Es gilt&nbsp; ${\rm Inv_A}  ($"$0\hspace{0.03cm}2$")  $\, = \, $ "$0\hspace{0.03cm}1$",
 
+ Es gilt&nbsp; ${\rm Inv_A}  ($"$0\hspace{0.03cm}2$")  $\, = \, $ "$0\hspace{0.03cm}1$",
Line 68: Line 68:
 
- Es gilt&nbsp; ${\rm Inv_A} ($"$2\hspace{0.03cm}2$") $\, = \, $ "$0\hspace{0.03cm}0$".
 
- Es gilt&nbsp; ${\rm Inv_A} ($"$2\hspace{0.03cm}2$") $\, = \, $ "$0\hspace{0.03cm}0$".
  
−
{Welche der folgenden Aussagen treffen für die Multiplikation zu?
+
{Which of the following statements are true about multiplication?
 
|type="()"}
 
|type="()"}
−
- Die Multiplikation erfolgt modulo&nbsp; $p(\alpha) = \alpha^2 + 2$.
+
- The multiplication is modulo&nbsp; $p(\alpha) = \alpha^2 + 2$.
−
+ Die Multiplikation erfolgt modulo&nbsp; $p(\alpha) = \alpha^2 + 2\alpha + 2$.
+
+ The multiplication is modulo&nbsp; $p(\alpha) = \alpha^2 + 2\alpha + 2$.
  
−
{Welche Aussagen gelten hinsichtlich der multiplikativen Inversen?
+
{What statements are true regarding multiplicative inverses?
 
|type="[]"}
 
|type="[]"}
−
- Es gibt für alle Elemente&nbsp; $z_i &#8712; {\rm GF}(P^m)$&nbsp; eine multiplikative Inverse.
+
- There is a multiplicative inverse for all elements&nbsp; $z_i &#8712; {\rm GF}(P^m)$&nbsp; .
−
+ Es gilt&nbsp; ${\rm Inv_M} ($"$1\hspace{0.03cm}2$") $\, = \, $ "$1\hspace{0.03cm}0$".
+
+ It holds&nbsp; ${\rm Inv_M} ($"$1\hspace{0.03cm}2$") $\, = \, $"$1\hspace{0.03cm}0$".
−
- Es gilt&nbsp; ${\rm Inv_A} ($"$2\hspace{0.03cm}1$") $\, = \, $ "$1\hspace{0.03cm}2$".
+
- It holds&nbsp; ${\rm Inv_A} ($"$2\hspace{0.03cm}1$") $\, = \, $ "$1\hspace{0.03cm}2$".
  
−
{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$"?
+
{Does ("$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$" hold?
 
|type="()"}
 
|type="()"}
−
+ Ja.
+
+ Yes.
−
- Nein.
+
- No.
 
</quiz>
 
</quiz>
  
−
===Musterlösung===
+
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
−
'''(1)'''&nbsp; Jedes Element besteht aus zwei Ternärzahlen &nbsp; &#8658; &nbsp; $\underline{P = 3}, \ \underline{m = 2}$. Es gibt $q = P^m = 3^8 = \underline{9 \ \rm Elemente}$.
+
'''(1)'''&nbsp; Each element consists of two ternaries &nbsp; &#8658; &nbsp; $\underline{P = 3}, \ \underline{m = 2}$. There are $q = P^m = 3^8 = \underline{9 \rm elements}$.
  
  
−
'''(2)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 1</u>:
+
'''(2)'''&nbsp; Correct is the <u>proposed solution 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$.  
+
*The neutral element of the addition $(N_{\rm A})$ satisfies for all $z_i &#8712; {\rm GF}(P^m)$ the condition $z_i + N_{\rm A} = z_i$.  
−
*Aus der Additionstabelle kann abgelesen werden, dass "$0\hspace{0.03cm}0$" diese Bedingung erfült.
+
*From the addition table it can be read that "$0\hspace{0.03cm}0$" satisfies this condition.
  
  
−
'''(3)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>:
+
'''(3)'''&nbsp; Correct is the <u>proposed solution 2</u>:
−
*Das neutrale Element der Multiplikation $(N_{\rm M})$ muss stets die Bedingung $z_i \cdot N_{\rm M} = z_i$ erfüllen.  
+
*The neutral element of the multiplication $(N_{\rm M})$ must always satisfy the condition $z_i \cdot N_{\rm M} = z_i$.  
−
*Aus der Multiplikationstabelle ergibt sich $N_{\rm M} = \, "0\hspace{0.03cm}1"$.
+
*From the multiplication table, $N_{\rm M} = \, "0\hspace{0.03cm}1"$.
−
* In der Polynomschreibweise entspricht dies mit $k_1 = 0$ und $k_0 = 1$:
+
*In polynomial notation, this corresponds to $k_1 = 0$ and $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; With the polynomial representation, the following calculations result:
−
:$${\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}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 Vector}\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] +  
 
:$${\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},$$
+
\big[(-1) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3\big] =2\alpha + 2 \hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Vector}\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] +  
 
:$${\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}.$$
+
\big[(-2) \hspace{0.1cm}{\rm mod} \hspace{0.1cm} 3\big] =\alpha + 1 \hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm Vector}\hspace{0.15cm}"\hspace{-0.05cm}1\hspace{0.03cm}1"\hspace{0.05cm}.$$
  
−
Demzufolge sind nur die <u>beiden ersten Lösungsvorschläge</u> richtig.  
+
Consequently, only the <u>first two proposed solutions</u> are correct.  
  
−
Die Aufgabe kann aber auch ohne Rechnung allein anhand der Additionstabelle gelöst werden.  
+
However, the exercise can also be solved without calculation using the addition table alone.  
−
*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.  
+
*For example, you can find the inverse of "$2\hspace{0.03cm}2$" by looking for the column with the entry "$0\hspace{0.03cm}0$" in the last row.  
−
*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"$.
+
*You find the column labeled "$1\hspace{0.03cm}1$" and thus ${\rm Inv_A}("2\hspace{0.03cm}2") = \, "1\hspace{0.03cm}1"$.
  
  
−
'''(5)'''&nbsp; Die Multiplikation von $\alpha$ (Vektor "$1\hspace{0.03cm}0$") mit sich selbst ergibt $\alpha^2$.
+
'''(5)'''&nbsp; Multiplying $\alpha$ (vector "$1\hspace{0.03cm}0$") by itself gives $\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$".
+
* If the first proposed solution were valid, the condition $\alpha^2 + 2 = 0$ and thus $\alpha^2 = (-2) \, {\rm mod} \, 3 = 1$, thus yielding the vector "$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
+
* Assuming the second proposed solution, it follows from the condition $\alpha^2 + 2\alpha + 2 = 0$ in polynomial notation.
 
:$$\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 "$1\hspace{0.03cm}1$".
+
:and thus the coefficient vector "$1\hspace{0.03cm}1$".
  
−
In der Multiplikationstabelle findet man in Zeile 4, Spalte 4 genau den Eintrag "$1\hspace{0.03cm}1$" &#8594; Richtig ist also der <u>Lösungsvorschlag 2</u>.
+
In the multiplication table, in row 4, column 4, we find exactly the entry "$1\hspace{0.03cm}1$" &#8594; So, the correct one is <u>proposed solution 2</u>.
  
  
−
'''(6)'''&nbsp; 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$" &nbsp;<br>&#8658;&nbsp; Der <u>Lösungsvorschlag 2</u> ist also richtig im Gegensatz zu Vorschlag 3. Es gilt nämlich ${\rm Inv_M}("21") = \, "2\hspace{0.03cm}0"$.
+
'''(6)'''&nbsp; The multiplicative inverse to "$1\hspace{0.03cm}2$" can be found in row 6 of the multiplication table as the column with the entry "$0\hspace{0.03cm}1$" &nbsp;<br>&#8658;&nbsp; So the <u>proposed solution 2</u> is correct in contrast to proposal 3. Namely, ${\rm Inv_M}("21") = \, "2\hspace{0.03cm}0"$ holds.
  
−
Wir überprüfen diese Ergebnisse unter Berücksichtigung von $\alpha^2 + 2\alpha + 2 = 0$ durch Multiplikationen:
+
We check these results considering $\alpha^2 + 2\alpha + 2 = 0$ by multiplications:
−
:$$"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}.$$
+
:$$"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 Vector}\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"
 
:$$"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 $$
 
"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}.$$
+
:$$\hspace{2.725cm} \Rightarrow \ {\rm Vector}\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.
+
The solution suggestion 1 is therefore not correct, because there is no multiplicative inverse for "$00$".
  
  
−
'''(7)'''&nbsp; Die beiden Ausdrücke stimmen überein &nbsp; &#8658; &nbsp; <u>JA</u>, wie die folgenden Berechnungen zeigen:
+
'''(7)'''&nbsp; The two expressions agree &nbsp; &#8658; &nbsp; <u>YES</u>, as the following calculations show:
 
:$$("20" + "12") \ \cdot "12" \hspace{-0.15cm} \ = \ \hspace{-0.15cm} "02"\cdot "12" \hspace{-0.15cm} \ = \ \hspace{-0.15cm} "21"\hspace{0.05cm},$$
 
:$$("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}.$$
 
:$$"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: &nbsp; Das Distributivgesetz wurde zumindest an einem einzigen Beispiel nachgewiesen.
+
This means: &nbsp; The distributive law has been proved at least on a single example.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Revision as of 23:44, 31 August 2022

Underlying tables for addition and multiplication

A Galois field  ${\rm GF}(q)$  with  $q = P^m$  elements defined by the adjacent tables is to be analyzed

  • for addition  (marked with "$+$"),  and
  • for multiplication  (marked with "$\hspace{0.05cm}\cdot\hspace{0.05cm}$").


This Galois field  ${\rm GF}(q) = \{\hspace{0.1cm}z_0,\hspace{0.1cm} z_1,\hspace{0.05cm} \text{...} , \hspace{0.1cm}z_{q-1}\}$  satisfies all the requirements for a finite field listed in the chapter  "Some Basics of Algebra" . Thus, commutative, associative and distributive laws are also satisfied.

Furthermore there is

  • a neutral element with respect to 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},$$
  • a neutral element with respect to multiplication   ⇒   $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},$$
  • for all elements  $z_i$  an 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}, $$
  • for all elements  $z_i$  except the zero element a multiplicative 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}. $$





Hints:

  • This exercise belongs to the chapter  "extension field".
  • In the tables, the elements  $z_0, \hspace{0.05cm} \text{...} \hspace{0.1cm} , \ z_8$  are called coefficient vectors. For example, "$2 \hspace{0.03cm}1$" stands for "$2 \cdot \alpha + 1$".



Fragebogen

1

Specify the parameters of the Galois field considered here.

$P \ = \ $
$m \ = \ $
$q \ = \ $

2

What is the neutral element of 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

What is the neutral element of multiplication?

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

What statements are true regarding additive inverses?

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

Which of the following statements are true about multiplication?

The multiplication is modulo  $p(\alpha) = \alpha^2 + 2$.
The multiplication is modulo  $p(\alpha) = \alpha^2 + 2\alpha + 2$.

6

What statements are true regarding multiplicative inverses?

There is a multiplicative inverse for all elements  $z_i ∈ {\rm GF}(P^m)$  .
It holds  ${\rm Inv_M} ($"$1\hspace{0.03cm}2$") $\, = \, $"$1\hspace{0.03cm}0$".
It holds  ${\rm Inv_A} ($"$2\hspace{0.03cm}1$") $\, = \, $ "$1\hspace{0.03cm}2$".

7

Does ("$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$" hold?

Yes.
No.


Solution

Solution

(1)  Each element consists of two ternaries   ⇒   $\underline{P = 3}, \ \underline{m = 2}$. There are $q = P^m = 3^8 = \underline{9 \rm elements}$.


(2)  Correct is the proposed solution 1:

  • The neutral element of the addition $(N_{\rm A})$ satisfies for all $z_i ∈ {\rm GF}(P^m)$ the condition $z_i + N_{\rm A} = z_i$.
  • From the addition table it can be read that "$0\hspace{0.03cm}0$" satisfies this condition.


(3)  Correct is the proposed solution 2:

  • The neutral element of the multiplication $(N_{\rm M})$ must always satisfy the condition $z_i \cdot N_{\rm M} = z_i$.
  • From the multiplication table, $N_{\rm M} = \, "0\hspace{0.03cm}1"$.
  • In polynomial notation, this corresponds to $k_1 = 0$ and $k_0 = 1$:
$$k_1 \cdot \alpha + k_0 = 1 \hspace{0.05cm}.$$


(4)  With the polynomial representation, the following calculations result:

$${\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 Vector}\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 Vector}\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 Vector}\hspace{0.15cm}"\hspace{-0.05cm}1\hspace{0.03cm}1"\hspace{0.05cm}.$$

Consequently, only the first two proposed solutions are correct.

However, the exercise can also be solved without calculation using the addition table alone.

  • For example, you can find the inverse of "$2\hspace{0.03cm}2$" by looking for the column with the entry "$0\hspace{0.03cm}0$" in the last row.
  • You find the column labeled "$1\hspace{0.03cm}1$" and thus ${\rm Inv_A}("2\hspace{0.03cm}2") = \, "1\hspace{0.03cm}1"$.


(5)  Multiplying $\alpha$ (vector "$1\hspace{0.03cm}0$") by itself gives $\alpha^2$.

  • If the first proposed solution were valid, the condition $\alpha^2 + 2 = 0$ and thus $\alpha^2 = (-2) \, {\rm mod} \, 3 = 1$, thus yielding the vector "$0\hspace{0.03cm}1$."
  • Assuming the second proposed solution, it follows from the condition $\alpha^2 + 2\alpha + 2 = 0$ in polynomial notation.
$$\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 $$
and thus the coefficient vector "$1\hspace{0.03cm}1$".

In the multiplication table, in row 4, column 4, we find exactly the entry "$1\hspace{0.03cm}1$" → So, the correct one is proposed solution 2.


(6)  The multiplicative inverse to "$1\hspace{0.03cm}2$" can be found in row 6 of the multiplication table as the column with the entry "$0\hspace{0.03cm}1$"  
⇒  So the proposed solution 2 is correct in contrast to proposal 3. Namely, ${\rm Inv_M}("21") = \, "2\hspace{0.03cm}0"$ holds.

We check these results considering $\alpha^2 + 2\alpha + 2 = 0$ by multiplications:

$$"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 Vector}\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 Vector}\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}.$$

The solution suggestion 1 is therefore not correct, because there is no multiplicative inverse for "$00$".


(7)  The two expressions agree   ⇒   YES, as the following calculations show:

$$("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}.$$

This means:   The distributive law has been proved at least on a single example.

Retrieved from "http://en.lntwww.de/index.php?title=Aufgaben:Exercise_2.6:_GF(P_power_m)._Which_P,_which_m%3F&oldid=48680"
  • Powered by MediaWiki