Aufgabe 2.3: Reduzible und irreduzible Polynome

• Zurück zum Buch

Einige Polynome von Grad  $m = 2$,  $m = 3$,  $m = 4$

Wichtige Voraussetzungen für das Verständnis der Kanalcodierung sind Kenntnisse der Polynomeigenschaften. 

Wir betrachten in dieser Aufgabe Polynome der Form

$$a(x) = a_0 + a_1 \cdot x + a_2 \cdot x^2 + \hspace{0.1cm}... \hspace{0.1cm} + a_m \cdot x^{m} \hspace{0.05cm},$$

• wobei für die Koeffizienten  $a_i ∈ {\rm GF}(2) = \{0, \, 1\}$  gilt  $(0 ≤ i ≤ m)$

• und der höchste Koeffizient stets zu  $a_m = 1$  vorausgesetzt wird.

Man bezeichnet  $m$  als den  "Grad"  des Polynoms.  Nebenstehend sind zehn Polynome angegeben,  mit den Polynomgraden

• $m = 2$  (rote Schrift), 
• $m = 3$  (blaue Schrift) oder 
• $m = 4$  (grüne Schrift).

Ein Polynom  $a(x)$  bezeichnet man als  reduzibel,  wenn es als Produkt zweier Polynome  $p(x)$  und  $q(x)$  mit jeweils niedrigerem Grad dargestellt werden kann:

$$a(x) = p(x) \cdot q(x)$$

Ist dies nicht möglich,  das heißt,  wenn für das Polynom

$$a(x) = p(x) \cdot q(x) + r(x)$$

mit einem Restpolynom  $r(x) ≠ 0$  gilt,  so nennt an das Polynom  irreduzibel.  Solche irreduziblen Polynome sind für die Beschreibung von Fehlerkorrekturverfahren von besonderer Bedeutung.

⇒   Der Nachweis,  dass ein Polynom  $a(x)$  vom Grad  $m$  irreduzibel ist,  erfordert mehrere Polynomdivisionen  $a(x)/q(x)$,  wobei der Grad des Divisorpolynoms  $q(x)$  stets kleiner ist als  $m$. Nur wenn alle diese Modulo–2–Divisionen stets einen Rest  $r(x) ≠ 0$  liefern,  ist nachgewiesen,  dass  $a(x)$  tatsächlich ein irreduzibles Polynom ist.

⇒   Dieser exakte Nachweis ist sehr aufwändig.  Notwendige Voraussetzungen dafür,  dass  $a(x)$  überhaupt ein irreduzibles Polynom sein könnte,  sind die beiden Bedingungen  $($bei nichtbinärer Betrachtungsweise wäre „$x=1$” durch „$x≠0$” zu ersetzen$)$:

• $a(x = 0) = 1$,

• $a(x = 1) = 1$.

Ansonsten könnte man für das zu untersuchende Polynom schreiben:

$$a(x) = q(x) \cdot x \hspace{0.5cm}{\rm bzw.}\hspace{0.5cm}a(x) = q(x) \cdot (x+1)\hspace{0.05cm}.$$

Die oben genannten Voraussetzungen sind zwar notwendig,  jedoch nicht hinreichend,  wie das folgende Beispiel zeigt:

$$a(x) = x^5 + x^4 +1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}a(x = 0) = 1\hspace{0.05cm},\hspace{0.2cm}a(x = 1) = 1 \hspace{0.05cm}.$$

Trotzdem ist dieses Polynom nämlich reduzibel:

$$a(x) = (x^3 + x +1)(x^2 + x +1) \hspace{0.05cm}.$$

Hinweis:  Die Aufgabe gehört zum Kapitel  "Erweiterungskörper".

Fragebogen

1

Wieviele Polynomdivisionen  $(N_{\rm D})$  sind erforderlich,  um exakt nachzuweisen,  dass ein  ${\rm GF}(2)$–Polynom  $a(x)$  vom Grad  $m$  irreduzibel ist?

$m = 2 \text{:} \hspace{0.35cm} N_{\rm D} \ = \ $

$m = 3 \text{:} \hspace{0.35cm} N_{\rm D} \ = \ $

$m = 4 \text{:} \hspace{0.35cm} N_{\rm D} \ = \ $

2

Welche der Grad–2–Polynome sind irreduzibel?

	$a_1(x) = x^2 + x$,
	$a_2(x) = x^2 + x + 1$.

3

Welche der Grad–3–Polynome sind irreduzibel?

	$a_3(x) = x^3$,
	$a_4(x) = x^3 + 1$,
	$a_5(x) = x^3 + x$,
	$a_6(x) = x^3 + x + 1$,
	$a_7(x) = x^3 + x^2 + 1$.

4

Welche der Grad–4–Polynome sind irreduzibel?

	$a_8(x) = x^4 + 1$,
	$a_9(x) = x^4 + x^3 + 1$,
	$a_{10}(x) = x^4 + x^2 + 1$.

Musterlösung

Musterlösung

(1)  Das Polynom  $a(x) = a_0 + a_1 \cdot x + a_2 \cdot x^2 + \hspace{0.1cm}... \hspace{0.1cm} + a_m \cdot x^{m}$

• mit  $a_m = 1$

• und gegebenen Koeffizienten  $a_0, \ a_1, \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ a_{m-1}$  $($jeweils  $0$  oder  $1)$

ist dann irreduzibel,  wenn es kein einziges Polynom  $q(x)$  gibt,  so dass die Modulo–2–Division   $a(x)/q(x)$   keinen Rest ergibt.  Der Grad aller zu betrachtenden Teilerpolynome  $q(x)$  ist dabei mindestens  $1$  und höchstens  $m-1$.

• Für  $m = 2$  sind zwei Polynomdivisionen  $a(x)/q_i(x)$  erforderlich,  nämlich mit

$$q_1(x) = x \hspace{0.5cm}{\rm und}\hspace{0.5cm}q_2(x) = x+1 \hspace{0.3cm} \Rightarrow\hspace{0.3cm}N_{\rm D}\hspace{0.15cm}\underline{= 2} \hspace{0.05cm}.$$

• Für  $m = 3$  gibt es schon  $N_{\rm D} \ \underline{= 6}$  Teilerpolynome,  nämlich neben  $q_1(x) = x$  und  $q_2(x) = x + 1$  noch

$$q_3(x) = x^2\hspace{0.05cm},\hspace{0.2cm}q_4(x) = x^2+1\hspace{0.05cm},\hspace{0.2cm} q_5(x) = x^2 + x\hspace{0.05cm},\hspace{0.2cm}q_6(x) = x^2+x+1\hspace{0.05cm}.$$

• Für  $m = 4$  müssen außer  $q_1(x), \hspace{0.05cm}\text{ ...} \hspace{0.1cm} , \ q_6(x)$  auch noch alle möglichen Teilerpolynome mit Grad  $m = 3$  berücksichtigt werden,  also:

$$q_i(x) = a_0 + a_1 \cdot x + a_2 \cdot x^2 + x^3\hspace{0.05cm},\hspace{0.5cm}a_0,\ a_1,\ a_2 \in \{0,1\} \hspace{0.05cm}.$$

Für den Index gilt dabei  $7 ≤ i ≤ 14 \ \Rightarrow \ N_{\rm D} \ \underline{= 14}$.

(2)  Für das erste Polynom gilt:  $a_1(x = 0) = 0$.  Deshalb ist dieses Polynom reduzibel:  

$$a_1(x) = x \cdot (x + 1).$$

Dagegen gilt für das zweite Polynom:

$$a_2(x = 0) = 1\hspace{0.05cm},\hspace{0.2cm}a_2(x = 1) = 1 \hspace{0.05cm}.$$

Diese notwendige,  aber nicht hinreichende Eigenschaft zeigt,  dass  $a_2(x)$  irreduzibel sein könnte. 

Der endgültige Beweis ergibt sich erst durch zwei Modulo–2–Divisionen:

• $a_2(x)$  geteilt durch  $x$  liefert  $x + 1$,  Rest $r(x) = 1$,

• $a_2(x)$  geteilt durch  $x + 1$  liefert  $x$,  Rest $r(x) = 1$.

Richtig ist demnach der  Lösungsvorschlag 2.

(3)  Die drei ersten Polynome sind reduzibel,  wie die folgenden Rechenergebnisse zeigen:

$$a_3(x = 0) = 0\hspace{0.05cm},\hspace{0.2cm}a_4(x = 1) = 0\hspace{0.05cm},\hspace{0.2cm}a_5(x = 0) = 0\hspace{0.05cm},\hspace{0.2cm}a_5(x = 1) = 0 \hspace{0.05cm}.$$

Das hätte man auch durch Nachdenken herausfinden können:

$$a_3(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} x \cdot x \cdot x \hspace{0.05cm},$$

$$a_4(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (x^2 + x + 1)\cdot(x + 1) \hspace{0.05cm},$$

$$a_5(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} x \cdot (x + 1)\cdot(x + 1) \hspace{0.05cm}.$$

Das Polynom  $a_6(x)$  ist sowohl für  $x = 0$  als auch für  $x = 1$  ungleich  $0$.  Das heißt,  dass

• „nichts dagegen spricht”,  dass $a_6(x)$  irreduzibel ist,

• die Division durch die irreduziblen Grad–1–Polynome  $x$  bzw.  $x + 1$  nicht ohne Rest möglich ist.

Da aber auch die Division durch das einzige irreduzible Grad–2–Polynom einen Rest liefert,  ist bewiesen,  dass  $a_6(x)$  ein irreduzibles Polynom ist:

$$(x^3 + x+1)/(x^2 + x+1) = x + 1 \hspace{0.05cm},\hspace{0.4cm}{\rm Rest}\hspace{0.15cm} r(x) = x\hspace{0.05cm},$$

Mit gleichem Rechengang kann auch gezeigt werden, dass  $a_7(x)$  ebenfalls irreduzibel ist   ⇒   Lösungsvorschläge 4 und 5.

(4)  Aus  $a_8(x + 1) = 0$  folgt die Reduzibilität von  $a_8(x)$.  Für die beiden anderen Polynome gilt dagegen:

$$a_9(x = 0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1\hspace{0.05cm},\hspace{0.35cm}a_9(x = 1) = 1 \hspace{0.05cm},$$

$$a_{10}(x = 0) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}1\hspace{0.05cm},\hspace{0.2cm}a_{10}(x = 1) = 1 \hspace{0.05cm}.$$

Beide könnten also irreduzibel sein.  Der exakte Nachweis der Irreduzibilität ist aufwändiger:

• Man muss zur Überprüfung zwar nicht alle vier Divisorpolynome mit Grad  $m = 2$ heranziehen,  nämlich $x^2, \ x^2 + 1, \ x^2 + x + 1$,  sondern es genügt die Division durch das einzige irreduzible Grad–2–Polynom.  Man erhält hinsichtlich des Polynoms  $a_9(x)$:

$$(x^4 + x^3+1)/(x^2 + x+1) = x^2 + 1 \hspace{0.05cm},\hspace{0.4cm}{\rm Rest}\hspace{0.15cm} r(x) = x\hspace{0.05cm}.$$

Auch die Division durch die beiden irreduziblen Grad–3–Polynome liefert jeweils einen Rest:

$$(x^4 + x^3+1)/(x^3 + x+1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} x + 1 \hspace{0.05cm},\hspace{0.4cm}{\rm Rest}\hspace{0.15cm} r(x) = x^2\hspace{0.05cm},$$

$$(x^4 + x^3+1)/(x^3 + x^2+1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} x \hspace{0.05cm},\hspace{0.95cm}{\rm Rest}\hspace{0.15cm} r(x) = x +1\hspace{0.05cm}.$$

Betrachten wir schließlich noch das Polynom  $a_{10}(x) = x^4 + x^2 + 1$.  Hier gilt

$$(x^4 + x^2+1)/(x^2 + x+1) = x^2 + x+1 \hspace{0.05cm},\hspace{0.4cm}{\rm Rest}\hspace{0.15cm} r(x) = 0\hspace{0.05cm}.$$

Daraus folgt:  Nur das Polynom  $a_9(x)$  ist irreduzibel   ⇒   Lösungsvorschlag 2.