Aufgabe 2.4Z: Endliche und unendliche Körper

Aus LNTwww
Wechseln zu:Navigation, Suche

Einige Pioniere der Mathematik

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:

  • 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

1

Welche Polynome sind irreduzibel im reellen Körper  $\mathcal{R}$?

$p_1(x) = x^2 + 1$.
$p_2(x) = x^2 - 1$,
$p_3(x) = x^2 + x + 1$,
$p_4(x) = x^2 + x - 2$.

2

Welche Polynome sind irreduzibel in  $\rm GF(2)$?

$p_1(x) = x^2 + 1$,
$p_2(x) = x^2 - 1$,
$p_3(x) = x^2 + x + 1$,
$p_4(x) = x^2 + x - 2$.

3

Bei welchen Mengen handelt es sich im algebraischen Sinne um Körper?

die Menge  $\mathcal{N}$  der natürlichen Zahlen,
die Menge  $\mathcal{Z}$  der ganzen Zahlen,
die Menge  $\mathcal{Q}$  der rationalen Zahlen,
die Menge  $\mathcal{R}$  der reellen Zahlen,
die Menge  $\mathcal{C}$  der komplexen Zahlen.

4

Welche Körper sind Teilmenge  $($Unterraum$)$  eines anderen Körpers?

$\mathcal{Q} ⊂ \mathcal{C}$,
$\mathcal{C} ⊂ \mathcal{R}$,
${\rm GF}(2) ⊂ {\rm GF}(2^2)$,
${\rm GF}(2^3) ⊂ {\rm GF}(2^2)$.

5

Zwischen welchen Körpern bestehen gewisse Analogien?

Menge  $\mathcal{Q}$  der rationalen Zahlen und  ${\rm GF}(2^2)$,
Menge  $\mathcal{C}$  der komplexen Zahlen und  ${\rm GF}(2^2)$,
Menge  $\mathcal{C}$  der komplexen Zahlen und  ${\rm GF}(2^3)$.


Musterlösung

(1)  Im Angabenteil steht sinngemäß:

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:
  1. Die beiden Nullstellen von  $p_2(x)$  und  $p_4(x)$  sind jeweils reell.  Somit handelt es sich hierbei mit Sicherheit um reduzible Polynome.
  2. 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.