View source for Aufgaben:Exercise 2.6: GF(P power m). Which P, which m?

{{quiz-Header|Buchseite=Channel_Coding/Extension_Field}}

[[File:P_ID2510__KC_A_2_6_neu.png|right|frame|Underlying tables for <br>addition and multiplication]]
A Galois field&nbsp; ${\rm GF}(q)$&nbsp; with&nbsp; $q = P^m$&nbsp; elements defined by the adjacent tables is to be analyzed
*for addition&nbsp; $($marked with "$+$"$)$,&nbsp; and
 
*for multiplication&nbsp; $($marked with "$\hspace{0.05cm}\cdot\hspace{0.05cm}$)". 


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

Furthermore there is
* a neutral element with respect to addition &nbsp; &#8658; &nbsp; $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 (zero\hspace{0.15cm}element)}
\hspace{0.05cm},$$
* a neutral element with respect to multiplication &nbsp; &#8658; &nbsp; $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 (identity\hspace{0.15cm}element)}
\hspace{0.05cm},$$
* for all elements&nbsp; $z_i$&nbsp; an additive inverse &nbsp; &#8658; &nbsp; ${\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 "\hspace{-0.15cm}0\hspace{-0.1cm}"}\hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm short}\text{:}\hspace{0.15cm}
{\rm Inv_A}(z_i) = - z_i \hspace{0.05cm}, $$
* for all elements&nbsp; $z_i$&nbsp; except the zero element a multiplicative inverse &nbsp;&#8658;&nbsp; ${\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 "\hspace{-0.15cm}1\hspace{-0.1cm}"}
\hspace{0.25cm} \Rightarrow \hspace{0.25cm}{\rm short}\text{:}\hspace{0.15cm}
{\rm Inv_M}(z_i) = z_i^{-1}
\hspace{0.05cm}. $$



Hints:
* This exercise belongs to the chapter&nbsp; [[Channel_Coding/Extension_Field| "Extension Field"]].
 
* In the tables,&nbsp; the elements &nbsp; $z_0, \hspace{0.05cm}  \text{...}  \hspace{0.1cm} , \ z_8$ &nbsp; are called&nbsp; "coefficient vectors".

* For example,&nbsp; "$2 \hspace{0.03cm}1$"&nbsp; stands for&nbsp; "$2 \cdot \alpha + 1$".
 




===Questions===
<quiz display=simple>
{Specify the parameters of the Galois field considered here.
|type="{}"}
$P \ = \ ${ 3 }
$m \ = \ ${ 2 }
$q \ = \ ${ 9 }

{What is the neutral element of addition?
|type="()"}
+ The neutral element of addition is&nbsp; $N_{\rm A} = \,$ "$0\hspace{0.03cm}0$",
- The neutral element of addition is&nbsp; $N_{\rm A} = \,$ "$0\hspace{0.03cm}1$".

{What is the neutral element of multiplication?
|type="()"}
- The neutral element of multiplication is&nbsp; $N_{\rm M} = \,$ "$0\hspace{0.03cm}0$",
+ The neutral element of multiplication is&nbsp; $N_{\rm M} = \,$ "$0\hspace{0.03cm}1$".

{What statements are true regarding additive inverses?
|type="[]"}
+ It holds&nbsp; ${\rm Inv_A} ($"$0\hspace{0.03cm}2$") $\, = \, $ "$0\hspace{0.03cm}1$",
+ It holds&nbsp; ${\rm Inv_A} ($"$1\hspace{0.03cm}1$") $\, = \, $ "$2\hspace{0.03cm}2$",
- It holds&nbsp; ${\rm Inv_A} ($"$2\hspace{0.03cm}2$") $\, = \, $ "$0\hspace{0.03cm}0$".

{Which of the following statements are true about the  multiplication?
|type="()"}
- The multiplication is defined here modulo&nbsp; $p(\alpha) = \alpha^2 + 2$.
+ The multiplication is defined here  modulo&nbsp; $p(\alpha) = \alpha^2 + 2\alpha + 2$.

{What statements are true regarding multiplicative inverses?
|type="[]"}
- There is a multiplicative inverse for all elements&nbsp; $z_i &#8712; {\rm GF}(P^m)$&nbsp; .
+ It holds&nbsp; ${\rm Inv_M} ($"$1\hspace{0.03cm}2$") $\, = \, $"$1\hspace{0.03cm}0$".
- It holds&nbsp; ${\rm Inv_M} ($"$2\hspace{0.03cm}1$") $\, = \, $ "$1\hspace{0.03cm}2$".

{Does&nbsp;  $($"$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="()"}
+ Yes.
- No.
</quiz>

===Solution===
{{ML-Kopf}}
'''(1)'''&nbsp; Each element consists of two ternaries &nbsp; &#8658; &nbsp; $\underline{P = 3}, \ \underline{m = 2}$.&nbsp; There are&nbsp; $q = P^m = 3^8 = \underline{9 \rm \hspace{0.2cm}elements}$.


'''(2)'''&nbsp; Correct is the&nbsp; <u>proposed solution 1</u>:
*The neutral element of the addition &nbsp;  $(N_{\rm A})$&nbsp; satisfies for all&nbsp; $z_i &#8712; {\rm GF}(P^m)$&nbsp; the condition&nbsp; $z_i + N_{\rm A} = z_i$. 
*From the addition table it can be read that&nbsp; "$0\hspace{0.03cm}0$"&nbsp; satisfies this condition.


'''(3)'''&nbsp; Correct is the&nbsp; <u>proposed solution 2</u>:
*The neutral element of the multiplication &nbsp;  $(N_{\rm M})$&nbsp; must always satisfy the condition&nbsp; $z_i \cdot N_{\rm M} = z_i$.
 
*From the multiplication table,&nbsp; $N_{\rm M} = \, "\hspace{-0.15cm}0\hspace{0.03cm}1\hspace{-0.1cm}"$.

*In polynomial notation,&nbsp; this corresponds to&nbsp; $k_1 = 0$&nbsp; and&nbsp; $k_0 = 1$:
:$$k_1 \cdot \alpha + k_0 = 1 \hspace{0.05cm}.$$


'''(4)'''&nbsp; With the polynomial representation,&nbsp; 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.1cm}0\hspace{0.03cm}1\hspace{-0.1cm}"\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.15cm}\hspace{-0.05cm}2\hspace{0.03cm}2\hspace{-0.1cm}"\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.15cm}\hspace{-0.05cm}1\hspace{0.03cm}1\hspace{-0.1cm}"\hspace{0.05cm}.$$

Consequently,&nbsp; only the&nbsp; <u>first two proposed solutions</u>&nbsp; are correct. 

However,&nbsp; the exercise can also be solved without calculation using the addition table alone: 
*For example,&nbsp; you can find the inverse of&nbsp; "$2\hspace{0.03cm}2$"&nbsp; by looking for the column with the entry&nbsp; "$0\hspace{0.03cm}0$"&nbsp; in the last row.
 
*You find the column labeled&nbsp; "$1\hspace{0.03cm}1$"&nbsp; and thus&nbsp; ${\rm Inv_A}("\hspace{-0.15cm}2\hspace{0.03cm}2\hspace{-0.15cm}") = \, "\hspace{-0.15cm}1\hspace{0.03cm}1\hspace{-0.15cm}"$.


'''(5)'''&nbsp; Multiplying&nbsp; $\alpha$&nbsp; $($vector "$1\hspace{0.03cm}0$"$)$&nbsp; by itself gives&nbsp; $\alpha^2$.
* If the first proposed solution were valid,&nbsp; the condition&nbsp; $\alpha^2 + 2 = 0$&nbsp; and thus&nbsp; $\alpha^2 = (-2) \, {\rm mod} \, 3 = 1$,&nbsp; thus yielding the vector&nbsp; "$0\hspace{0.03cm}1$".

* Assuming the second proposed solution,&nbsp; it follows from the condition&nbsp; $\alpha^2 + 2\alpha + 2 = 0$ &nbsp; in polynomial notation:
:$$\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 $$
:and thus the coefficient vector&nbsp; "$1\hspace{0.03cm}1$".

*In the multiplication table,&nbsp; in row 4, column 4,&nbsp; we find exactly the entry&nbsp; "$1\hspace{0.03cm}1$" &nbsp; &rArr; &nbsp; So,&nbsp; the correct answert is the&nbsp; <u>proposed solution 2</u>.


'''(6)'''&nbsp; The multiplicative inverse to&nbsp; "$1\hspace{0.03cm}2$"&nbsp; can be found in row 6 of the multiplication table as the column with the entry&nbsp; "$0\hspace{0.03cm}1$" &nbsp;
*So the&nbsp; <u>proposed solution 2</u>&nbsp; is correct in contrast to proposal 3.&nbsp; Namely,&nbsp; ${\rm Inv_M}("\hspace{-0.15cm}21\hspace{-0.15cm}") = \, "\hspace{-0.15cm}2\hspace{0.03cm}0\hspace{-0.1cm}"$ holds.

*We check these results considering&nbsp; $\alpha^2 + 2\alpha + 2 = 0$&nbsp; by multiplications:
:$$"\hspace{-0.15cm}1\hspace{0.03cm}2\hspace{-0.1cm}" \hspace{0.05cm}\cdot \hspace{0.05cm}"\hspace{-0.15cm}1\hspace{0.03cm}0\hspace{-0.1cm}" \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}"\hspace{-0.15cm}0\hspace{0.03cm}1\hspace{-0.15cm}" \hspace{0.15cm} \Rightarrow  \hspace{0.15cm}{\rm multiplicative \hspace{0.15cm}inverse}\hspace{0.05cm}.$$
:$$"\hspace{-0.15cm}2\hspace{0.03cm}1\hspace{-0.1cm}" \hspace{0.05cm}\cdot \hspace{0.05cm}"\hspace{-0.15cm}1\hspace{0.03cm}2\hspace{-0.1cm}" \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}"\hspace{-0.15cm}1\hspace{0.03cm}1\hspace{-0.15cm}" \hspace{0.15cm} \Rightarrow  \hspace{0.15cm}{\rm no\hspace{0.15cm}multiplicative \hspace{0.15cm}inverse}\hspace{0.05cm}.$$

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


'''(7)'''&nbsp; The two expressions agree &nbsp; &#8658; &nbsp; <u>YES</u>, as the following calculations show:
:$$("\hspace{-0.15cm}20\hspace{-0.1cm}" + "\hspace{-0.15cm}12\hspace{-0.1cm}") \ \cdot "\hspace{-0.15cm}12\hspace{-0.1cm}" \hspace{-0.15cm} \ = \ \hspace{-0.15cm} "\hspace{-0.15cm}02\hspace{-0.1cm}"\cdot "\hspace{-0.15cm}12\hspace{-0.1cm}" \hspace{-0.15cm} \ = \ \hspace{-0.15cm} "\hspace{-0.15cm}21\hspace{-0.1cm}"\hspace{0.05cm},$$
:$$"\hspace{-0.15cm}20\hspace{-0.1cm}" \cdot  "\hspace{-0.15cm}12\hspace{-0.1cm}" + "\hspace{-0.15cm}12\hspace{-0.1cm}" \cdot "\hspace{-0.15cm}12\hspace{-0.1cm}" \hspace{-0.15cm} \ = \ \hspace{-0.15cm} "\hspace{-0.15cm}02\hspace{-0.1cm}" + "\hspace{-0.15cm}22\hspace{-0.1cm}" \hspace{-0.15cm} \ = \ \hspace{-0.15cm} "\hspace{-0.15cm}21\hspace{-0.1cm}"\hspace{0.05cm}.$$

This means: &nbsp; The distributive law has been proved at least on a single example.
{{ML-Fuß}}



[[Category:Channel Coding: Exercises|^2.2 Extension Field^]]