[[File:P_ID2508__KC_A_2_5.png|right|frame|Potenzen zweier Erweiterungskörper über $\rm GF(2^4)$ – nicht ganz vollständig]]
[[File:EN_KC_A_2_5.png|right|frame|Powers of two different extension fields over $\rm GF(2^4)$ - a not quite complete list]]
Irreduzible und primitive Polynome haben große Bedeutung für die Beschreibung von Verfahren zur Fehlerkorrektur. In [[LN97]] findet man zum Beispiel die folgenden irreduziblen Polynome vom Grad $m = 4$:
Irreducible and primitive polynomials have great importance in the description of error correction methods. For example, in '''[LN97]''' one finds the following irreducible polynomials of degree $m = 4$:
* $p(x) = x^4 + x +1$,
* $p_1(x) = x^4 + x +1$,
* $p(x) = x^4 + x^3 + 1$,
* $p(x) = x^4 + x^3 + x^2 + x + 1$.
* $p_2(x) = x^4 + x^3 + 1$,
Die beiden ersten Polynome sind auch primitiv. Dies erkennt man aus den Potenztabellen, die rechts angegeben sind – die untere Tabelle (B) allerdings nicht ganz vollständig. Aus beiden Tabellen erkennt man, dass alle Potenzen $\alpha^i$ für $1 ≤ i ≤ 14$ in der Polynomdarstellung ungleich $1$ sind. Erst für $i = 15$ ergibt sich
Nicht angegeben wird, ob sich die rot hinterlegte Tabelle (A) aus dem Polynom $x^4 + x + 1$ oder aus $x^4 + x^3 + 1$ ergibt. Diese Zuordnungen sollen Sie in den Teilaufgaben (1) und (2) treffen. In der Teilaufgabe (3) sollen Sie zudem die fehlenden Potenzen $\alpha^5, \ \alpha^6, \ \alpha^7$ und $\alpha^8$ in der Tabelle (B) ergänzen.
Die Teilaufgabe (4) bezieht sich auf das ebenfalls irreduzible Polynom $p(x) = x^4 + x^3 + x^2 + x +1$. Entsprechend den oben genannten Kriterien sollen Sie entscheiden, ob dieses Polynom primitiv ist oder nicht.
The first two polynomials are also primitive. This can be seen from the power tables given on the right – the lower table $\rm (B)$ however not quite complete.
*From both tables we see that all powers $\alpha^i$ for $1 ≤ i ≤ 14$ are unequal $1$ in the polynomial representation. Only for $i = 15$ it follows that
*It is not specified whether the tables $\rm (A)$ and $\rm (B)$ result from the polynomial $p_1(x) = x^4 + x + 1$ or from $p_2(x) =x^4 + x^3 + 1$. You are to make these assignments in subtasks '''(1)''' and '''(2)'''.
*In the subtask '''(3)''' you are also to complete the missing powers $\alpha^5, \ \alpha^6, \ \alpha^7$ and $\alpha^8$ in the table $\rm (B)$.
''Hinweis:''
*The subtask '''(4)''' refers to the also irreducible polynomial $p_3(x) = x^4 + x^3 + x^2 + x +1$. According to the above criteria, you are to decide whether this polynomial is primitive.
* Die Aufgabe gehört ebenfalls zum Themengebiet des Kapitels [[Kanalcodierung/Erweiterungsk%C3%B6rper|Erweiterungskörper]].
Hints:
*The exercise belongs to the chapter [[Channel_Coding/Extension_Field|"Extension Field"]].
*The literature citation '''[LN97]''' refers to the book "Lidl, R.; Niederreiter, H.: Finite Fields. Encyclopedia of Mathematics and its Application. 2nd ed. Cambridge: University Press, 1997."
===Fragebogen===
===Questions===
<quiz display=simple>
<quiz display=simple>
{Welches Polynom liegt der Tabelle (A) zugrunde?
{Which polynomial underlies the table $\rm (A)$ ?
|type="()"}
|type="()"}
+ $p(x) = x^4 + x + 1$,
+ $p_1(x) = x^4 + x + 1$,
- $p(x) = x^4 + x^3 + 1$.
- $p_2(x) = x^4 + x^3 + 1$.
{Welches Polynom liegt der Tabelle (B) zugrunde?
{Which polynomial underlies the table $\rm (B)$ ?
|type="()"}
|type="()"}
- $p(x) = x^4 + x + 1$,
- $p_1(x) = x^4 + x + 1$,
+ $p(x) = x^4 + x^3 + 1$.
+ $p_2(x) = x^4 + x^3 + 1$.
{Berechnen Sie die in der Tabelle (B) fehlenden Einträge. Welche der folgenden Angaben sind richtig?
{Complete the entries missing in the table $\rm (B)$. Which of the following entries are correct?
{Ist $p(x) = x^4 + x^3 + x^2 + x + 1$ ein primitives Polynom? Klären Sie diese Frage anhand der Potenzen $\alpha^i$ ($i$ soweit erforderlich).
{Is the polynomial $p_3(x) = x^4 + x^3 + x^2 + x + 1$ primitive? Clarify this question using the powers $\alpha^i$ $(i$ where necessary$)$.
|type="()"}
|type="()"}
- Ja.
- Yes.
+ Nein.
+ No.
</quiz>
</quiz>
===Musterlösung===
===Solution===
{{ML-Kopf}}
{{ML-Kopf}}
'''(1)'''
'''(1)''' From the upper power table $\rm (A)$ on the data page one recognizes among other things the property
Thus, the <u>proposed solution 1</u> is correct.
'''(5)'''
'''(2)''' Following the same procedure, it can be shown that the power table $\rm (B)$ is based on the polynomial $p_2(x) = x^4 + x^3 + 1$ ⇒ <u>Proposed solution 2</u>.
'''(3)''' Starting from polynomial $p_2(x) = x^4 + x^3 + 1$ one obtains from the determining equation $p(\alpha) = 0$ the result $\alpha^4 = \alpha^3 + 1$. This further yields:
*Thus, only the <u>proposed solutions 1 and 4</u> are correct. The other two statements are interchanged.
*The following are the complete power tables for $p_1(x) = x^4 + x + 1$ (left, red background) and for $p_2(x) = x^4 + x^3 + 1$ (right, blue background).
[[File:P_ID2512__KC_A_2_5d_neu.png|right|frame|Complete power tables over $\rm GF(2^4)$ for two different polynomials <br>$($Sorry, we used here the German terms$)$]]
'''(4)''' The polynomials $p_1(x) = x^4 + x + 1$ and $p_2(x) = x^4 + x^3 + 1$ are primitive.
*This can be seen from the fact that $\alpha^i \ne 1$ for $0 < i < 14$ in each case.
*In contrast, $\alpha^{15} = \alpha^0 = 1$ holds. In both cases, the Galois field can be expressed as follows:
*So here is already $\alpha^5 = \alpha^0 = 1 $ <br>$\Rightarrow \ p_3(x)$ is not a primitive polynomial ⇒ <u>Proposed solution 2</u>.
Powers of two different extension fields over $\rm GF(2^4)$ - a not quite complete list
Irreducible and primitive polynomials have great importance in the description of error correction methods. For example, in [LN97] one finds the following irreducible polynomials of degree $m = 4$:
$p_1(x) = x^4 + x +1$,
$p_2(x) = x^4 + x^3 + 1$,
$p_3(x) = x^4 + x^3 + x^2 + x + 1$.
The first two polynomials are also primitive. This can be seen from the power tables given on the right – the lower table $\rm (B)$ however not quite complete.
From both tables we see that all powers $\alpha^i$ for $1 ≤ i ≤ 14$ are unequal $1$ in the polynomial representation. Only for $i = 15$ it follows that
It is not specified whether the tables $\rm (A)$ and $\rm (B)$ result from the polynomial $p_1(x) = x^4 + x + 1$ or from $p_2(x) =x^4 + x^3 + 1$. You are to make these assignments in subtasks (1) and (2).
In the subtask (3) you are also to complete the missing powers $\alpha^5, \ \alpha^6, \ \alpha^7$ and $\alpha^8$ in the table $\rm (B)$.
The subtask (4) refers to the also irreducible polynomial $p_3(x) = x^4 + x^3 + x^2 + x +1$. According to the above criteria, you are to decide whether this polynomial is primitive.
The literature citation [LN97] refers to the book "Lidl, R.; Niederreiter, H.: Finite Fields. Encyclopedia of Mathematics and its Application. 2nd ed. Cambridge: University Press, 1997."
(2) Following the same procedure, it can be shown that the power table $\rm (B)$ is based on the polynomial $p_2(x) = x^4 + x^3 + 1$ ⇒ Proposed solution 2.
(3) Starting from polynomial $p_2(x) = x^4 + x^3 + 1$ one obtains from the determining equation $p(\alpha) = 0$ the result $\alpha^4 = \alpha^3 + 1$. This further yields:
Thus, only the proposed solutions 1 and 4 are correct. The other two statements are interchanged.
The following are the complete power tables for $p_1(x) = x^4 + x + 1$ (left, red background) and for $p_2(x) = x^4 + x^3 + 1$ (right, blue background).
Complete power tables over $\rm GF(2^4)$ for two different polynomials $($Sorry, we used here the German terms$)$
(4) The polynomials $p_1(x) = x^4 + x + 1$ and $p_2(x) = x^4 + x^3 + 1$ are primitive.
This can be seen from the fact that $\alpha^i \ne 1$ for $0 < i < 14$ in each case.
In contrast, $\alpha^{15} = \alpha^0 = 1$ holds. In both cases, the Galois field can be expressed as follows:
