Aufgaben:Aufgabe 2.5: Drei Varianten von GF(2 hoch 4)

• Zurück zum Buch

Potenzen zweier verschiedener Erweiterungskörper über  $\rm GF(2^4)$  – eine nicht ganz vollständige Liste

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

• $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$.

Die beiden ersten Polynome sind auch primitiv.  Dies erkennt man aus den Potenztabellen,  die rechts angegeben sind – die untere Tabelle  $\rm (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

$$\alpha^{15} = \alpha^{0} = 1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}{\rm Koeffizientenvektor\hspace{0.15cm} 0001}\hspace{0.05cm} .$$

• Nicht angegeben wird,  ob sich die Tabellen  $\rm (A)$  und  $\rm (B)$  aus dem Polynom   $p_1(x) = x^4 + x + 1$   oder aus   $p_2(x) =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  $\rm (B)$  ergänzen.

• Die Teilaufgabe  (4)  bezieht sich auf das ebenfalls irreduzible Polynom   $p_3(x) = x^4 + x^3 + x^2 + x +1$.   Entsprechend den oben genannten Kriterien sollen Sie entscheiden,  ob dieses Polynom primitiv ist.

Hinweise:

• Die Aufgabe gehört zum Kapitel  "Erweiterungskörper".

• Das Literaturzitat  [LN97]  verweist auf das Buch  "Lidl, R.; Niederreiter, H.:  Finite Fields.  Encyclopedia of Mathematics and its Application. 2. Auflage. Cambridge: University Press, 1997".

Fragebogen

1 Welches Polynom liegt der Tabelle  $\rm (A)$  zugrunde?

	$p_1(x) = x^4 + x + 1$,
	$p_2(x) = x^4 + x^3 + 1$.

2 Welches Polynom liegt der Tabelle  $\rm (B)$  zugrunde?

	$p_1(x) = x^4 + x + 1$,
	$p_2(x) = x^4 + x^3 + 1$.

3 Ergänzen Sie die in der Tabelle  $\rm (B)$  fehlenden Einträge.  Welche der folgenden Angaben sind richtig?

	$\alpha^5 = \alpha^3 + \alpha + 1$   ⇒   Koeffizientenvektor  „$1011$”,
	$\alpha^6 = \alpha^2 + 1$   ⇒   Koeffizientenvektor  „$0111$”,
	$\alpha^7 = \alpha^3 + \alpha^2 + \alpha + 1$   ⇒   Koeffizientenvektor  „$1111$”,
	$\alpha^8 = \alpha^3 + \alpha^2 + \alpha$   ⇒   Koeffizientenvektor  „$1110$”.

4 Ist   $p_3(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$)$.

	Ja.
	Nein.

Musterlösung

Musterlösung

(1)  Aus der oberen Potenztabelle  $\rm (A)$  auf der Angabenseite erkennt man unter anderem die Eigenschaft

$$\alpha^{4} = \alpha + 1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}\alpha^{4} + \alpha + 1 = 0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}p(x) = x^4 + x +1 =p_1(x)\hspace{0.05cm}.$$

• Richtig ist somit der  Lösungsvorschlag 1.

(2)  Nach gleicher Vorgehensweise kann gezeigt werden,  dass die Potenztabelle  $\rm (B)$  auf dem Polynom   $p_2(x) = x^4 + x^3 + 1$   basiert   ⇒   Lösungsvorschlag 2.

(3)  Ausgehend vom Polynom   $p_2(x) = x^4 + x^3 + 1$   erhält man aus der Bestimmungsgleichung  $p(\alpha) = 0$  das Ergebnis  $\alpha^4 = \alpha^3 + 1$.  Damit ergibt sich weiter:

$$\alpha^5 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^4 = \alpha \cdot (\alpha^3 + 1) = \alpha^4 + \alpha = \alpha^3 + \alpha +1\hspace{0.05cm} \Rightarrow\hspace{0.05cm}{\rm Vektor\hspace{0.15cm} 1011},$$

$$\alpha^6 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^5 = \alpha \cdot (\alpha^3 +\alpha + 1) = \alpha^4 + \alpha^2 + \alpha= \alpha^3 +\alpha^2 + \alpha + 1\hspace{0.05cm} \Rightarrow\hspace{0.05cm}{\rm Vektor\hspace{0.15cm} 1111},$$

$$\alpha^7 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^6 = \alpha^4 +\alpha^3 +\alpha^2 +\alpha = \alpha^2 + \alpha + 1\hspace{0.05cm} \Rightarrow\hspace{0.05cm}{\rm Vektor\hspace{0.15cm} 0111},$$

$$\alpha^8 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^7 = \alpha \cdot (\alpha^2 + \alpha + 1) = \alpha^3 +\alpha^2 +\alpha \hspace{0.05cm} \Rightarrow\hspace{0.05cm}{\rm Vektor\hspace{0.15cm} 1110}.$$

• Richtig sind somit die  Lösungsvorschläge 1 und 4.  Die beiden anderen Angaben sind vertauscht.
• Nachfolgend finden Sie die vollständigen Potenztabellen für   $p_1(x) = x^4 + x + 1$   (links,  rot hinterlegt) und für   $p_2(x) = x^4 + x^3 + 1$   (rechts,  blau hinterlegt).

Vollständige Potenztabellen über  $\rm GF(2^4)$  für zwei unterschiedliche Polynome

(4)  Die beiden Polynome   $p_1(x) = x^4 + x + 1$   und   $p_2(x) = x^4 + x^3 + 1$   sind primitiv.

• Dies erkennt man daran,  dass für  $0 < i < 14$  jeweils  $\alpha^i \ne 1$  ist.

• Dagegen gilt  $\alpha^{15} = \alpha^0 = 1$.  In beiden Fällen kann das Galoisfeld wie folgt ausgedrückt werden:

$${\rm GF}(2^4) = \{\hspace{0.1cm}0\hspace{0.05cm},\hspace{0.1cm} \alpha^{0} = 1,\hspace{0.05cm}\hspace{0.1cm}\alpha\hspace{0.05cm},\hspace{0.1cm} \alpha^{2},\hspace{0.1cm} ... \hspace{0.1cm} , \hspace{0.1cm}\alpha^{14}\hspace{0.1cm}\}\hspace{0.05cm}. $$

⇒   Für das Polynom  $p_3(x) = x^4 + x^3 + x^2 + x +1$  erhält man :

$$\alpha^4 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha^3 + \alpha^2 + \alpha +1\hspace{0.25cm} \Rightarrow\hspace{0.25cm}{\rm Vektor\hspace{0.15cm} 1111}\hspace{0.05cm},$$

$$\alpha^5 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha \cdot \alpha^4 = \alpha^4 + \alpha^3 + \alpha^2 + \alpha $$

$$= (\alpha^3 + \alpha^2 + \alpha +1) + \alpha^3 + \alpha^2 + \alpha = 1 \hspace{0.25cm} \Rightarrow\hspace{0.25cm}{\rm Vektor\hspace{0.15cm} 0001}\hspace{0.05cm}.$$

• Hier ist also bereits $\alpha^5 = \alpha^0 = 1$
  $\Rightarrow \ p_3(x)$  ist kein primitives Polynom   ⇒   Lösungsvorschlag 2.

• Für die weiteren Potenzen gilt für dieses Polynom:

$$\alpha^6 = \alpha^{11} = \alpha\hspace{0.05cm},\hspace{0.2cm} \alpha^7 = \alpha^{12} = \alpha^2\hspace{0.05cm},\hspace{0.2cm}\alpha^8 = \alpha^{13} = \alpha^3\hspace{0.05cm},$$

$$\alpha^9 = \alpha^{14} = \alpha^4\hspace{0.05cm},\hspace{0.2cm}\alpha^{10} = \alpha^{15} = \alpha^0 = 1\hspace{0.05cm}.$$