Aufgaben:Aufgabe 2.3: Reduzible und irreduzible Polynome: Unterschied zwischen den Versionen
(Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt) | |||
Zeile 1: | Zeile 1: | ||
{{quiz-Header|Buchseite=Kanalcodierung/Erweiterungskörper}} | {{quiz-Header|Buchseite=Kanalcodierung/Erweiterungskörper}} | ||
− | [[Datei:P_ID2503__KC_A_2_3.png|right|frame|Polynome von Grad $m = 2$, $m = 3$ | + | [[Datei:P_ID2503__KC_A_2_3.png|right|frame|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 | + | 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} | :$$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},$$ | \hspace{0.05cm},$$ | ||
− | wobei für die Koeffizienten $a_i ∈ {\rm GF}(2) = \{0, \, 1\}$ gilt $(0 ≤ i ≤ m)$ | + | *wobei für die Koeffizienten $a_i ∈ {\rm GF}(2) = \{0, \, 1\}$ gilt $(0 ≤ i ≤ m)$ |
− | Ein Polynom $a(x)$ bezeichnet man als <b>reduzibel</b>, wenn es als Produkt zweier Polynome $p(x)$ und $q(x)$ mit jeweils niedrigerem Grad dargestellt werden kann: | + | *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 <b>reduzibel</b>, 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)$$ | :$$a(x) = p(x) \cdot q(x)$$ | ||
− | Ist dies nicht möglich, das heißt, wenn für das Polynom | + | Ist dies nicht möglich, das heißt, wenn für das Polynom |
:$$a(x) = p(x) \cdot q(x) + r(x)$$ | :$$a(x) = p(x) \cdot q(x) + r(x)$$ | ||
− | mit einem Restpolynom $r(x) ≠ 0$ gilt, so nennt an das Polynom <b>irreduzibel</b>. Solche irreduziblen Polynome sind für die Beschreibung von Fehlerkorrekturverfahren von besonderer Bedeutung. | + | mit einem Restpolynom $r(x) ≠ 0$ gilt, so nennt an das Polynom <b>irreduzibel</b>. 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 | + | ⇒ 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): | + | ⇒ 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 = 0) = 1$, | ||
+ | |||
* $a(x = 1) = 1$. | * $a(x = 1) = 1$. | ||
Zeile 26: | Zeile 38: | ||
:$$a(x) = q(x) \cdot x \hspace{0.5cm}{\rm bzw.}\hspace{0.5cm}a(x) = q(x) \cdot (x+1)\hspace{0.05cm}.$$ | :$$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: | + | 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 | :$$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}.$$ | \hspace{0.05cm}.$$ | ||
− | Trotzdem ist dieses Polynom reduzibel: | + | Trotzdem ist dieses Polynom nämlich reduzibel: |
:$$a(x) = (x^3 + x +1)(x^2 + x +1) \hspace{0.05cm}.$$ | :$$a(x) = (x^3 + x +1)(x^2 + x +1) \hspace{0.05cm}.$$ | ||
Zeile 37: | Zeile 49: | ||
− | + | Hinweis: Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Erweiterungsk%C3%B6rper| "Erweiterungskörper"]]. | |
− | |||
Zeile 44: | Zeile 55: | ||
===Fragebogen=== | ===Fragebogen=== | ||
<quiz display=simple> | <quiz display=simple> | ||
− | {Wieviele Polynomdivisionen $(N_{\rm D})$ sind erforderlich, um exakt nachzuweisen, dass ein ${\rm GF}(2)$–Polynom $a(x)$ vom Grad $m$ irreduzibel ist? | + | {Wieviele Polynomdivisionen $(N_{\rm D})$ sind erforderlich, um exakt nachzuweisen, dass ein ${\rm GF}(2)$–Polynom $a(x)$ vom Grad $m$ irreduzibel ist? |
|type="{}"} | |type="{}"} | ||
$m = 2 \text{:} \hspace{0.35cm} N_{\rm D} \ = \ ${ 2 3% } | $m = 2 \text{:} \hspace{0.35cm} N_{\rm D} \ = \ ${ 2 3% } | ||
Zeile 72: | Zeile 83: | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | '''(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}$ | + | '''(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$ | + | *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$ | + | |
+ | *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– | + | 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 | + | * 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 | :$$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.3cm} \Rightarrow\hspace{0.3cm}N_{\rm D}\hspace{0.15cm}\underline{= 2} | ||
\hspace{0.05cm}.$$ | \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 | + | * 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_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}.$$ | 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: | + | * 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\} | + | :$$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}.$$ | \hspace{0.05cm}.$$ | ||
− | :Für den Index gilt dabei $7 ≤ i ≤ 14 \ \Rightarrow \ N_{\rm D} \ \underline{= 14}$. | + | :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)$ | + | '''(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: | Dagegen gilt für das zweite Polynom: | ||
Zeile 99: | Zeile 112: | ||
\hspace{0.05cm}.$$ | \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: | + | Diese notwendige, aber nicht hinreichende Eigenschaft zeigt, dass $a_2(x)$ irreduzibel sein könnte. |
− | * $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$. | + | 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 <u>Lösungsvorschlag 2</u>. | + | Richtig ist demnach der <u>Lösungsvorschlag 2</u>. |
− | '''(3)''' Die drei ersten Polynome sind reduzibel, wie die folgenden Rechenergebnisse zeigen: | + | '''(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 | :$$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}.$$ | \hspace{0.05cm}.$$ | ||
Zeile 116: | Zeile 132: | ||
:$$a_5(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} x \cdot (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 | + | 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, | + | * „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. | + | |
+ | * 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: | + | 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},$$ | :$$(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 ⇒ <u>Lösungsvorschläge 4 und 5</u>. | + | Mit gleichem Rechengang kann auch gezeigt werden, dass $a_7(x)$ ebenfalls irreduzibel ist ⇒ <u>Lösungsvorschläge 4 und 5</u>. |
− | '''(4)''' Aus $a_8(x + 1) = 0$ folgt die Reduzibilität von $a_8(x)$. Für die beiden anderen Polynome gilt dagegen: | + | '''(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_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}.$$ | :$$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: | + | 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)$: | + | *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}.$$ | :$$(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}.$$ | ||
Zeile 139: | Zeile 156: | ||
:$$(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}.$$ | :$$(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 | + | 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}.$$ | :$$(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 ⇒ <u>Lösungsvorschlag 2</u>. | + | Daraus folgt: Nur das Polynom $a_9(x)$ ist irreduzibel ⇒ <u>Lösungsvorschlag 2</u>. |
{{ML-Fuß}} | {{ML-Fuß}} | ||
Aktuelle Version vom 29. September 2022, 16:48 Uhr
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
Musterlösung
- 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.