Aufgabe 2.3Z: Polynomdivision

• Zurück zum Buch

Multiplikation und Division von Polynomen in  $\rm GF(2)$

In dieser Aufgabe beschäftigen wir uns mit der Multiplikation und insbesondere der Division von Polynomen im Galoisfeld  $\rm GF(2)$.  In der Abbildung ist jeweils die Vorgehensweise an einem einfachen und  (hoffentlich)  selbsterklärenden Beispiel angedeutet:

• Die Multiplikation der beiden Polynome   $x^2 + 1$   und   $x +1$   liefert das Ergebnis   $a(x) = x^3 + x^2 + x + 1$.

• Die Division des Polynoms   $b(x) = x^3$   durch   $p(x) = x + 1$   liefert den Quotienten   $q(x) = x^2 + x$   und den Rest  $r(x) = x$.

• Man kann das letztere Ergebnis wie folgt überprüfen:

$$b(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} p(x) \cdot q(x) + r(x)\hspace{0.05cm}= \big[(x+1) \cdot (x^2+x)\big] +x =\big[x^3+ x^2+x^2+ x\big] +x = x^3\hspace{0.05cm}.$$

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

Fragebogen

1

Welches Ergebnis liefert  $a(x) = (x^3 + x + 1) \cdot (x^2 + 1)$?

	$a(x) = x^5 + x^3 + x^2 + 1$,
	$a(x) = x^5 + x^2 + x + 1$.
	$a(x) = x^6 + x^3 + x^2 + 1$-

2

Welche der Polynomdivisionen ergeben keinen Rest  $r(x) \ne 0$?

	$(x^5 + x^2 + x + 1)/(x^3 + x + 1)$.
	$(x^5 + x^2 + x + 1)/(x^2 + 1)$,
	$(x^5 + x^2 + x + 1)/(x^2)$,
	$(x^5 + x^2 + x)/(x^2 + 1)$.

3

Es sei   $a(x) = x^6 + x^5 + 1$   und   $p(x) = x^3 + x^2 + 1$.
Bestimmen Sie  $q(x)$  und  $r(x)$  entsprechend der Beschreibungsgleichung   $a(x) = p(x) \cdot q(x) + r(x)$.

	$q(x) = x^3 + x^2 + 1, \hspace{0.2cm} r(x) = 0$,
	$q(x) = x^3 + 1, \hspace{0.2cm} r(x) = 0$,
	$q(x) = x^3 + 1, \hspace{0.2cm} r(x) = x^2$.

Musterlösung

Musterlösung

(1)  Die Modulo–2–Multiplikation der beiden Polynome führt zum Ergebnis

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

• Richtig ist somit der  Lösungsvorschlag 2.

• Der letzte Lösungsvorschlag kann schon alleine deshalb nicht simmen,  da der Grad des Produktpolynoms ungleich  $5$  wäre.

Beispiel 1  zur Polynomdivision

(2)  Mit den Abkürzungen

$$a(x) = x^5+ x^2+x+1\hspace{0.05cm},\hspace{0.4cm}p(x) = x^3+ x+1\hspace{0.05cm},\hspace{0.4cm}q(x) = x^2+ 1$$

und dem Ergebnis aus der Teilaufgabe  (1)  erhält man  $a(x) = p(x) \cdot q(x)$.

Das heißt:   Die Divisionen   $a(x)/p(x)$   und   $a(x)/q(x)$   sind restfrei möglich  
⇒   Richtig sind die  Lösungsvorschläge 1 und 2.

Auch ohne Rechnung erkennt man,  dass  $a(x)/x^2$  einen Rest ergeben muss.  Nach Rechnung ergibt sich explizit:

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

Zum letzten Lösungsvorschlag.  Wir verwenden zur Abkürzung   $b(x) = x^5 + x^2 + x = a(x) + 1$.  Damit ist der vorgegebene Quotient:

$$b(x)/q(x) = a(x)/q(x) + 1/q(x) \hspace{0.05cm}.$$

Beispiel 2  zur Polynomdivision

• Der erste Quotient  $a(x)/q(x)$  ergibt entsprechend der Teilaufgabe  (2)  genau  $p(x)$  ohne Rest,  der zweite Quotient hat das Ergebnis  $0$  mit Rest  $1$.

• Somit ist hier der Rest des Quotienten  $b(x)/q(x)$ gleich $r(x) = 1$,  wie die Rechnung im  Beispiel 1  zeigt.

(3)  Die Polynomdivision ist im  Beispiel 2  ausführlich erläutert.  Richtig ist der Lösungsvorschlag 3.