Exercise 2.3Z: Polynomial Division

• Return to book

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

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 selbsterklärenden Beispiel verdeutlicht:

• 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 $a(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:

$$a(x) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} p(x) \cdot q(x) + r(x)\hspace{0.05cm}= $$

$$\hspace{-0.15cm} \ = \ \hspace{-0.15cm}[(x+1) \cdot (x^2+x)] +x =$$

$$\hspace{-0.15cm} \ = \ \hspace{-0.15cm}[x^3+ x^2+x^2+ x] +x = x^3\hspace{0.05cm}.$$

Hinweis:

• Die Aufgabe gehört zum Themengebiet des Kapitels 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)$?

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

Solution

(1)  (2)  (3)  (4)  (5)