Exercise 2.4Z: Finite and Infinite Fields
In der Mathematik unterscheidet man verschiedene Zahlenmengen:
- die Menge der natürlichen Zahlen: $\mathcal{N} = \{0, \, 1, \, 2, \hspace{0.05cm}\text{ ...} \}$,
- die Menge der ganzen Zahlen: $\mathcal{Z} = \{\text{ ...}, \, -1, \, 0, \, +1, \hspace{0.05cm}\text{ ...} \}$,
- die Menge der rationalen Zahlen: $\mathcal{Q} = \{m/n\}$ mit $m ∈ \mathcal{Z}, \ n ∈ \mathcal{Z} \, \backslash \, \{0\}$,
- die Menge $\mathcal{R}$ der reellen Zahlen,
- die Menge der komplexen Zahlen: $\mathcal{C}= \{a + {\rm j} \cdot b\}$ mit $a ∈ \mathcal{R}, \ b ∈ \mathcal{R}$ und der imaginären Einheit $\rm j$.
Eine solche Menge (englisch: Set ) bezeichnet man dann (und nur dann) als einen Körper (englisch: Field ) im algebraischen Sinne, wenn in ihr die vier Rechenoperationen Addition, Subtraktion, Multiplikation und Division erlaubt und die Ergebnisse im gleichen Körper darstellbar sind. Einige diesbezügliche Definitionen finden Sie im Theorieteil. Soviel vorneweg: Nicht alle der oben aufgelisteten Mengen sind Körper.
Daneben gibt es auch noch endliche Körper (englisch: Finite Fields), die in unserem Lerntutorial auch als Galoisfeld ${\rm GF}(P^m)$ bezeichnet werden, wobei
- $P ∈ \mathcal{P}$ eine Primzahl angibt, und
- $m ∈ \mathcal{N}$ eine natürliche Zahl bezeichnet.
Ist der Exponent $m ≥ 2$, so spricht man von einem Erweiterungskörper (englisch: Extension Field ). In dieser Aufgabe beschränken wir uns auf Erweiterungskörper zur Basis $P = 2$.
Die beiden ersten Teilaufgaben beziehen sich auf die Klassifizierung von Polynomen. Ein Grad–$m$–Polynom nennt man reduzibel im Körper $\mathcal{F}$, wenn es in der Form
- $$p(x)= \prod_{i = 1}^m (x-x_i) = (x - x_1) \cdot (x - x_2) \cdot \hspace{0.05cm}\text{ ...}\hspace{0.05cm} \cdot (x - x_m) $$
darstellbar ist und für alle Nullstellen $x_i ∈ \mathcal{F}$ gilt. Ist dies nicht möglich, so spricht man von einem irreduziblen Polynom.
Hinweise:
- Die Aufgabe gehört zum Kapitel Erweiterungskörper.
- Oben sehen Sie Abbildungen der italienischen Mathematiker Gerolamo Cardano sowie Rafael Bombelli, die erstmals imaginäre Zahlen zur Lösung algebraischer Gleichungen einführten, sowie von Évariste Galois, der schon in sehr jungen Jahren die Grundlagen der endlichen Körper geschaffen hat.
Fragebogen
Musterlösung
Ein Polynom vom Grad $m$ nennt man reduzibel im Körper $\mathcal{F}$, wenn es in der Form
- $$p(x)= \prod_{i = 1}^m (x-x_i) = (x - x_1) \cdot (x - x_2) \cdot \hspace{0.05cm}\text{ ...}\hspace{0.05cm} \cdot (x - x_m) $$
dargestellt werden kann und für alle Nullstellen $x_i ∈ \mathcal{F}$ gilt. Ist dies nicht möglich, so spricht man von einem irreduziblen Polynom.
Im reellen Zahlenraum gilt für die jeweils $m = 2$ Nullstellen $x_1$ und $x_2$:
- $$p_1(x) \text{:}\hspace{0.3cm}x_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} +{\rm j}\hspace{0.05cm},\hspace{0.2cm}x_2 = -{\rm j}\hspace{0.05cm},$$
- $$p_2(x) \text{:}\hspace{0.3cm}x_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} +1\hspace{0.05cm},\hspace{0.2cm}x_2 = -1\hspace{0.05cm},$$
- $$p_3(x) \text{:}\hspace{0.3cm}x_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} -0.5 + {\rm j} \cdot \sqrt{3}/2 \hspace{0.05cm},\hspace{0.2cm}x_2 = -0.5 - {\rm j} \cdot \sqrt{3}/2\hspace{0.05cm},$$
- $$p_4(x) \text{:}\hspace{0.3cm}x_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} +1\hspace{0.05cm},\hspace{0.2cm}x_2 = -2\hspace{0.05cm}.$$
Richtig sind somit die Lösungsvorschläge 1 und 3:
- Die beiden Nullstellen von $p_2(x)$ und $p_4(x)$ sind jeweils reell. Somit handelt es sich hierbei mit Sicherheit um reduzible Polynome.
- Die beiden anderen Polynome weisen dagegen keine reellen Nullstellen auf (vielmehr imaginäre bzw. komplexe) und sind nach obiger Definition irreduzibel im reellen Körper.
(2) Richtig ist der Lösungsvorschlag 3:
$p_3 = x^2 + x + 1$ ist das einzige irreduzible Polynom im Galoisfeld $\rm GF(2^2)$. Im Theorieteil wurden hierfür die Additions– und die Multiplikationstabelle angegeben.
Für die anderen Polynome gilt:
- Das Polynom $p_1(x)$ ist in ${\rm GF}(2) = \{0, \, 1\}$ reduzibel, da dieses Polynom faktorisiert werden kann:
- $$p_1(x) = x^2 + 1 = (x+1)^2\hspace{0.05cm}.$$
- Da in $\rm GF(2)$ kein Unterschied zwischen Summe und Differenz besteht, ist auch das Polynom $p_2(x) = x^2 - 1$ reduzibel.
- Das Polynom $p_4(x) = x^2 + x - 2$ ist schon allein deshalb für $\rm GF(2)$ ungeeignet, da nicht alle Polynomkoeffizienten $0$ oder $1$ sind.
- Die „$2$” wäre nur im Galoisfeld $\rm GF(3)$ möglich.
(3) Richtig sind die letzten drei Lösungsvorschläge:
- Die Menge $\mathcal{N}$ ist kein Körper, da schon die Subtraktion nicht für alle Elemente zulässig ist, zum Beispiel ist $2 - 3 = -1 ∉ \mathcal{N}$.
- Auch die Menge $\mathcal{Z}$ der ganzen Zahlen ist kein Körper, da beispielsweise die Gleichung $2 \cdot z = 1$ für kein $z ∈ \mathcal{N}$ zu erfüllen ist.
(4) Richtig sind die Antworten 1 und 3:
- Es gilt $\mathcal{Q} ⊂ \mathcal{R}$ (rationale Zahlen sind eine Untermenge der reellen Zahlen) und $\mathcal{R} ⊂ \mathcal{C}$ (reelle Zahlen sind eine Untermenge der komplexen Zahlen).
- Damit gilt auch $\mathcal{Q} ⊂ \mathcal{C}$.
- Bei den endlichen Körpern bedeutet ${\rm GF}(2^m) ⊂ {\rm GF}(2^M)$, dass $m < M$ gelten muss.
(5) Richtig ist der Lösungsvorschlag 2:
- Die Menge $\mathcal{C}$ der komplexen Zahlen ist eine Erweiterung der reellen Zahlen $(\mathcal{R})$ in eine zweite Dimension. Hierfür kann geschrieben werden:
- $$\mathcal{C} = \{k_0 + {\rm j} \cdot k_1\hspace{0.05cm}| \hspace{0.05cm}k_0 \in {\mathcal{R}}, k_1 \in \mathcal{R}\}\hspace{0.05cm}.$$
- $\rm GF(2^2)$ ist eine Erweiterung des endlichen Körpers $\rm GF(2) = \{0, \, 1\}$ in eine zweite Dimension:
- $${\rm GF}(2^2) = \{k_0 + \alpha \cdot k_1\hspace{0.05cm}| \hspace{0.05cm}k_0 \in {\rm GF}(2), k_1 \in {\rm GF}(2)\}\hspace{0.05cm}.$$
- Die imaginäre Einheit ${\rm j} ∉ \mathcal{C}$ ergibt sich als Lösung der Gleichung ${\rm j}^2 + 1 = 0$, während das neue Element von $\rm GF(2^2)$ mit $\alpha ∉ \rm GF(2)$ bezeichnet wird und aus der Gleichung $\alpha^2 + \alpha + 1 = 0$ folgt.
