path: root/buch/chapters/30-endlichekoerper/wurzeln.tex

%
% wurzeln.tex -- Wurzeln einem endlichen Körper hinzufügen
%
% (c) 2021 Prof Dr Andreas Müller, Hochschule Rapperswil
%
% !TeX spellcheck = de_CH
\section{Wurzeln
\label{buch:section:wurzeln}}
Im Körper $\mathbb{Q}$ kann man zum Beispiel die Wurzel aus $2$ nicht 
ziehen.
Das Problem haben wir in Abschnitt~\ref{buch:section:reelle-zahlen}
dadurch gelöst, dass wir $\mathbb{Q}$ zu den reellen Zahlen $\mathbb{R}$
erweitert haben.
Es ist aber auch möglich, nur die Zahl $\sqrt{2}$ hinzuzufügen,
so entsteht der Körper $\mathbb{Q}(\sqrt{2})$.
Das Problem dabei ist, was denn eigentlich $\sqrt{2}$ überhaupt ist.
Solange man die reellen Zahlen nicht hat, hat man auch die
gewohnte Realisation von $\sqrt{2}$ nicht.
Das Problem wird akut bei den endlichen Körpern wie zum Beispiel
$\mathbb{F}_3$,
da man diese nicht in $\mathbb{R}$ einbetten kann, also keine
bekannte Menge von Zahlen existiert, in der wir die Wurzel $\sqrt{2}$
finden könnten.

\rhead{Wurzeln}
Im Altertum fiel dieses Problem zunächst den Pythagoreern auf.
Wenn $\sqrt{2}$ kein Bruch ist, was ist es dann?
Im 15.~Jahrhundert stellte sich dieses Problem bei den Versuchen, die
kubische Gleichung allgemein zu lösen, erneut.
Hier war es die Wurzel $\sqrt{-1}$, die den reellen Zahlen hinzuzufügen
war.
In $\mathbb{R}$ hat $\sqrt{-1}$ sicher keinen Platz, also wo existert
es denn überhaupt?
Auch der von Descartes eingeführte, eher unglückliche Begriff
``imaginäre Zahl'' illustriert dieses Dilemma.

Inzwischen hat man sich daran gewöhnt, dass man einfach ein neues Symbol
wählt, die algebraischen Regeln postuliert, nach denen damit zu rechnen
ist, und dann hofft oder besser beweist, dass keine Widersprüche auftreten.
Auf diese Weise kann man einem Körper $\Bbbk$ eine beliebige 
Nullstelle $\alpha$ eines Polynoms $f\in\Bbbk[X]$ mit Koeffizienten
in $\Bbbk$ hinzufügen und so den Körper $\Bbbk(\alpha)$ konstruieren.
Trotzdem bleibt die Frage offen: was {\em ist} denn eigentlich $\alpha$?

In diesem Abschnitt werden Wurzeln wie folgt konstruiert.
Zunächst wird in Abschnitt~\ref{buch:subsection:koerpererweiterungen}
gezeigt, dass man immer eine Matrix $M_\alpha$ finden kann, welche
genau die algebraischen Eigenschaften einer Nullstelle $\alpha$ eines
Polynoms hat.
Die Frage ``Was ist $\alpha$?'' erhält also die Antwort ``eine Matrix''.
Mit diesem Bild lassen sich alle Körperoperationen realisieren, die
Inverse kann zum Beispiel als die inverse Matrix mit dem
Gauss-Algorithmus berechnet werden.
In einem zweiten Schritt zeigen wir dann, dass man die Rechnung noch
etwas vereinfachen kann, wenn man in Polynomringen arbeitet.
%Schliesslich zeigen wir dann im
%Abschnitt~\ref{buch:subsection:zerfaellungskoerper}, wie man 
%den Prozess iterieren kann und so für beliebige Polynome immer einen
%Körper finden kann, der alle Nullstellen enthält.
Wir beginnen in Abschnitt~\ref{buch:subsection:irreduziblepolynome}
damit, die Polynome, die für die Konstruktion in Frage kommen, etwas
genauer zu charakterisieren.

\subsection{Irreduzible Polynome
\label{buch:subsection:irreduziblepolynome}}
Die Zahlen, die man dem Körper $\Bbbk$ hinzufügen möchte, müssen Nullstellen
eines Polynoms sein.
Wir gehen daher davon aus, dass $f\in \Bbbk[X]$ ein Polynom mit
Koeffizienten in $\Bbbk$ ist, dessen Nullstelle $\alpha$ hinzugefügt
werden sollen.
Das Ziel ist natürlich, dass diese Erweiterung vollständig beschrieben
werden kann durch das Polynom, ganz ohne Bezug zum Beispiel auf einen
numerischen Wert der Nullstelle, der ohnehin nur in $\mathbb{C}$ sinnvoll
wäre.

Nehmen wir jetzt an, dass sich das Polynom $f$ faktorisieren lässt.
Dann gibt es Polynome $g,h\in\Bbbk[X]$ derart, dass $f=g\cdot h$.
Die Polynome $g$ und $h$ haben geringeren Grad als $f$. 
Setzt man die Nullstelle $\alpha$ ein, erhält man
$0=f(\alpha)=g(\alpha)h(\alpha)$, daher muss einer der Faktoren
verschwinden, also $g(\alpha)=0$ oder $h(\alpha)=0$.
Ohne Beschränkung der Allgemeinheit kann angenommen werden, dass
$g(\alpha)=0$.
Die Operation des Hinzufügens der Nullstelle $\alpha$ von $f$
muss also genauso gut mit $g$ ausgeführt werden können.
Indem wir diese Überlegung auf $g$ anwenden können wir schliessen,
dass es ein Polynom $m\in\Bbbk[X]$ kleinstmöglichen Grades geben muss,
welches $\alpha$ als Nullstelle hat.
Zusätzlich kann verlangt werden, dass das Polynom normiert ist.

\begin{definition}
Ein Polynom $f\in \Bbbk[X]$ heisst {\em irreduzibel}, wenn es sich nicht
in zwei Faktoren $g,h\in \Bbbk[X]$ geringeren Grades mit $f=gh$ zerlegen
lässt.
\index{irreduzibles Polynom}%
\end{definition}

Für die Konstruktion des Körpers $\Bbbk(\alpha)$ muss daher ein irreduzibles
Polynom verwendet werden.

\begin{beispiel}
Das Polynom $f(X)=X^2-2$ ist in $\mathbb{Q}[X]$, es hat die beiden
Nullstellen $\sqrt{2}$ und $-\sqrt{2}$.
Beide Nullstellen haben die exakt gleichen algebraischen Eigenschaften,
sie sind mit algebraischen Mitteln nicht zu unterscheiden.
Nur die Ordnungsrelation ermöglicht, die negative Wurzel von der
positiven zu unterscheiden.
Das Polynom kann in $\mathbb{Q}$ nicht faktorisiert werden, denn die
einzige denkbare Faktorisierung ist $(X-\sqrt{2})(X+\sqrt{2})$, die
Faktoren sind aber keine Polynome in $\mathbb{Q}[X]$.
Also ist $f(X) = X^2 - 2$ ein irreduzibles Polynom über $\mathbb Q$.

Man kann das Polynom aber auch als Polynom in $\mathbb{F}_{23}[X]$
betrachten.
Im Körper $\mathbb{F}_{23}$ kann man durch Probieren zwei Nullstellen
finden:
\begin{align*}
5^2 &= 25\equiv 2\mod 23
\\
\text{und}\quad
18^2 &=324 \equiv 2 \mod 23.
\end{align*}
Und tatsächlich ist in $\mathbb{F}_{23}[X]$
\[
(X-5)(X-18) = X^2 -23X+90
\equiv
X^2 -2 \mod 23,
\]
über $\mathbb{F}_{23}$ ist das Polynom $X^2-2$ also reduzibel.
\end{beispiel}

\begin{beispiel}
Die Zahl 
\begin{equation}
\alpha = \frac{-1+i\sqrt{3}}2\in\mathbb{C}
\label{buch:endliche-koerper:eqn:1iwurzel3}
\end{equation}
ist eine Nullstelle des Polynoms $f(X)=X^3-1\in\mathbb{Z}[X]$.
Der Ausdruck für
$\alpha$ enthält aber nur Quadratwurzeln, man würde also eigentlich
erwarten, dass $\alpha$ Nullstelle eines quadratischen Polynoms ist.
Tatsächlich ist $f(X)$ nicht irreduzibel,  es ist nämlich
\[
X^3-1 = (X-1)(X^2+X+1).
\]
Da $\alpha$ nicht Nullstelle des ersten Faktors ist, muss es Nullstelle
des Polynoms $m(X)=X^2+X+1$ sein.
Der zweite Faktor ist irreduzibel.

Das Polynom $m(X)$ kann man aber auch als Polynom in $\mathbb{F}_7$ 
ansehen.
Dann kann man aber zwei Nullstellen finden,
\[
\begin{aligned}
X&=2&&\Rightarrow& 2^2+2+1=4+2+1&\equiv 0\mod 7
\\
X&=4&&\Rightarrow& 4^2+4+1=16+4+1=21&\equiv 0\mod 7.
\end{aligned}
\]
Dies führt auf die Faktorisierung
\[
(X-2)(X-4)
\equiv
(X+5)(X+3)
=
X^2+8X+15
\equiv
X^2+X+1\mod 7.
\]
Das Polynom $X^2+X+1$ ist daher über $\mathbb{F}_7$ reduzibel und
das Polynom $X^3-1\in\mathbb{F}_7$ zerfällt in Linearfaktoren
$X^3-1=(X+6)(X+3)(X+5)$.
\end{beispiel}


\subsection{Körpererweiterungen
\label{buch:subsection:koerpererweiterungen}}
Nach den Vorbereitungen von
Abschnitt~\ref{buch:subsection:irreduziblepolynome}
können wir jetzt definieren, wie die Körpererweiterung
konstruiert werden soll.

\subsubsection{Erweiterung mit einem irreduziblen Polynom}
Sei $m\in\Bbbk[X]$ ein irreduzibles Polynome über $\Bbbk$ mit dem Grad
$\deg m=n>1$,
wir dürfen es als normiert annehmen und schreiben es in der Form
\[
m(X)
=
m_0+m_1X+m_2X^2 + \dots m_{n-1}X^{n-1}+X^n.
\]
Wir möchten den Körper $\Bbbk$ um eine Nullstelle $\alpha$ von $m$
erweitern.
Da es in $\Bbbk$ keine Nullstelle von $m$ gibt, konstruieren wir
$\Bbbk(\alpha)$ auf abstrakte Weise, ganz so wie das mit der imaginären
Einheit $i$ gemacht wurde.
Die Zahl $\alpha$ ist damit einfach ein neues Symbol, mit dem man
wie in der Algebra üblich rechnen kann.
Die einzige zusätzliche Eigenschaft, die von $\alpha$ verlangt wird,
ist dass $m(\alpha)=0$.
Unter diesen Bedingungen können beliebige Ausdrücke der Form
\begin{equation}
a_0 + a_1\alpha + a_2\alpha^2 + \dots a_k\alpha^k
\label{buch:endlichekoerper:eqn:ausdruecke}
\end{equation}
gebildet werden.
Aus der Bedingung $m(\alpha)=0$ folgt aber, dass
\begin{equation}
\alpha^n = -m_{n-1}\alpha^{n-1} -\dots - m_2\alpha^2  - m_1\alpha - m_0.
\label{buch:endlichekoerper:eqn:reduktion}
\end{equation}
Alle Potenzen mit Exponenten $\ge n$ in
\eqref{buch:endlichekoerper:eqn:ausdruecke}
können daher durch die rechte Seite von
\eqref{buch:endlichekoerper:eqn:reduktion}
ersetzt werden.
Als Menge ist daher
\[
\Bbbk(\alpha)
=
\{
a_0+a_1\alpha+a_2\alpha^2+\dots+a_{n-1}\alpha^{n-1} \mid a_i\in\Bbbk\}
\]
ausreichend.
Die Addition von solchen Ausdrücken und die Multiplikation mit Skalaren
aus $\Bbbk$ machen $\Bbbk(\alpha)\cong \Bbbk^n$ zu einem Vektorraum,
die Operationen können auf den Koeffizienten komponentenweise ausgeführt
werden.

\subsubsection{Matrixrealisierung der Multiplikation mit $\alpha$}
Die schwierige Operation ist die Multiplikation mit $\alpha$.
Dazu stellen wir zusammen, wie die Multiplikation mit $\alpha$ auf den
Basisvektoren von $\Bbbk(\alpha)$ wirkt:
\[
\alpha\colon
\Bbbk^n\to\Bbbk^n
:
\left\{
\begin{aligned}
     1  &\mapsto \alpha   \\
\alpha  &\mapsto \alpha^2 \\
\alpha^2&\mapsto \alpha^3 \\
        &\phantom{m}\vdots\\
\alpha^{n-2}&\mapsto \alpha^{n-1}\\
\alpha^{n-1}&\mapsto \alpha^n = -m_0-m_1\alpha-m_2\alpha^2-\dots-m_{n-1}\alpha^{n-1}.
\end{aligned}
\right.
\]
Diese lineare Abbildung hat die Matrix
\[
M_{\alpha}
=
\begin{pmatrix}
0   &    &    &      &   &-m_0    \\
1   & 0  &    &      &   &-m_1    \\
    & 1  & 0  &      &   &-m_2    \\
    &    & 1  &\ddots&   &\vdots  \\
    &    &    &\ddots& 0 &-m_{n-2}\\
    &    &    &      & 1 &-m_{n-1}
\end{pmatrix}.
\]
Aufgrund der Konstruktion wird die lineare Abbildung $m(M_\alpha)$,
die man erhält, wenn
man die Matrix $M_\alpha$ in das Polynom $m$ einsetzt, jeden Vektor
in $\Bbbk(\alpha)$ zu Null machen.
Als Matrix muss daher $m(M_\alpha)=0$ sein.
Dies kann man auch mit einem Computeralgebra-System nachprüfen.

\begin{beispiel}
In dem früheren Beispiel auf
Seite~\pageref{buch:endliche-koerper:eqn:1iwurzel3}
haben wir gesehen, dass
$\alpha=\frac12(-1+\sqrt{3})$ 
eine Nullstelle des irreduziblen Polynomes $m(X)=X^2+X+1$ ist.
Die zugehörige Matrix $M_\alpha$ ist
\[
M_{\alpha}
=
\begin{pmatrix}
0&-1\\
1&-1
\end{pmatrix}
\qquad\Rightarrow\qquad
M_{\alpha}^2
=
\begin{pmatrix}
-1& 1\\
-1& 0
\end{pmatrix},\quad
M_{\alpha}^3
=
\begin{pmatrix}
 1& 0\\
 0& 1
\end{pmatrix}.
\]
Wir können auch verifizieren, dass
\[
m(M_\alpha)
=
M_\alpha^2+M_\alpha+I
=
\begin{pmatrix}
-1& 1\\
-1& 0
\end{pmatrix}
+
\begin{pmatrix}
0&-1\\
1&-1
\end{pmatrix}
+
\begin{pmatrix}
1&0\\
0&1
\end{pmatrix}
=
\begin{pmatrix}
0&0\\
0&0
\end{pmatrix}.
\]
Die Matrix ist also eine mögliche Realisierung für das ``mysteriöse''
Element $\alpha$.
Sie hat alle algebraischen Eigenschaften von $\alpha$.
\end{beispiel}

Die Menge $\Bbbk(\alpha)$ kann durch die Abbildung $\alpha\mapsto M_\alpha$
mit der Menge aller Matrizen
\[
\Bbbk(M_\alpha)
=
\left\{
\left.
a_0I+a_1M_\alpha+a_2M_\alpha^2+\dots+a_{n-1}M_\alpha^{n-1}\;\right|\; a_i\in\Bbbk
\right\}
\]
in eine Eins-zu-eins-Beziehung gebracht werden.
Diese Abbildung ist ein Algebrahomomorphismus.
Die Menge $\Bbbk(M_\alpha)$ ist also das Bild des
Körpers $\Bbbk(\alpha)$ in der Matrizenalgebra $M_n(\Bbbk)$.

\subsubsection{Inverse in $\Bbbk(\alpha)$ mit der inversen Matrix}
Im Moment wissen wir noch nicht, wie wir Elemente in $\Bbbk(\alpha)$ 
invertieren sollen.
%$\alpha^{-1}$ berechnen sollten.
Wir können dafür aber die Matrizendarstellung verwenden.
Für Matrizen wissen wir selbstverständlich, wie sie invertiert
werden können.
Tatsächlich kann man die Matrix $M_\alpha$ z.~B.~direkt invertieren:
\[
M_\alpha^{-1}
=
\frac{1}{m_0}
\begin{pmatrix}
   -m_1 &m_0&   &      &      &   \\
   -m_2 & 0 &m_0&      &      &   \\
   -m_3 &   & 0 &   m_0&      &   \\
 \vdots &   &   &\ddots&\ddots&   \\
-m_{n-1}& 0 & 0 &      &  0   &m_0\\
    -1  & 0 & 0 &      &  0   & 0
\end{pmatrix},
\]
wie man durch Ausmultiplizieren überprüfen kann:
\[
\frac{1}{m_0}
\begin{pmatrix}
   -m_1 &m_0&   &      &      &   \\
   -m_2 & 0 &m_0&      &      &   \\
   -m_3 &   & 0 &   m_0&      &   \\
 \vdots &   &   &\ddots&\ddots&   \\
-m_{n-1}& 0 & 0 &      &  0   &m_0\\
    -1  & 0 & 0 &      &  0   & 0
\end{pmatrix}
\begin{pmatrix}
  0   &    &    &      &   &-m_0    \\
  1   & 0  &    &      &   &-m_1    \\
      & 1  & 0  &      &   &-m_2    \\
      &    & 1  &\ddots&   &\vdots  \\
      &    &    &\ddots& 0 &-m_{n-2}\\
      &    &    &      & 1 &-m_{n-1}
\end{pmatrix}
=
\begin{pmatrix}
1&0&0&\dots&0&0\\
0&1&0&\dots&0&0\\
0&0&1&\dots&0&0\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
0&0&0&\dots&1&0\\
0&0&0&\dots&0&1
\end{pmatrix}.
\]
Die Invertierung in $\Bbbk(M_\alpha)$ ist damit zwar geklärt, aber
es wäre viel einfacher, wenn man die Inverse auch in $\Bbbk(\alpha)$
bestimmen könnte.

Die Potenzen von $M_\alpha^k$ haben in der ersten Spalte genau in
Zeile $k+1$ eine $1$, alle anderen Einträge in der ersten Spalte
sind $0$.
Die erste Spalte eines Elementes
$a(\alpha)=a_0+a_1\alpha+a_2\alpha^2 +a_{n-1}\alpha^{n-1}$
besteht daher genau aus den Elementen $a_i$.
Die Inverse des Elements $a$ kann daher wie folgt gefunden werden.
Zunächst wird die Matrix $a(M_\alpha)$ gebildet und invertiert.
Wir schreiben $B=a(M_\alpha)^{-1}$.
Aus den Einträgen der ersten Spalte kann man jetzt die Koeffizienten
\[
b_0=(B)_{11},
b_1=(B)_{21},
b_2=(B)_{31},\dots,
b_{n-1}=(B)_{n,1}
\]
ablesen und daraus das Element
\[
b(\alpha) = b_0+b_1\alpha+b_2\alpha^2 + \dots + b_{n-1}\alpha^{n-1}
\]
bilden.
Da $b(M_\alpha)=B$ die inverse Matrix von $a(M_\alpha)$ ist, muss $b(\alpha)$
das Inverse von $a(\alpha)$ sein.

\begin{beispiel}
Wir betrachten das Polynom 
\[
m(X) = X^3 + 2X^2 + 2X + 3 \in \mathbb{F}_{7}[X],
\]
es ist irreduzibel.
Sei $\alpha$ eine Nullstelle von $m$, wir suchen das inverse Element zu
\[
a(\alpha)=1+2\alpha+2\alpha^2\in\mathbb{F}_{7}(\alpha).
\]
Die Matrix $a(M_\alpha)$ bekommt die Form
\[
A=\begin{pmatrix}
 1& 1& 6\\
 2& 4& 5\\
 2& 5& 1
\end{pmatrix}.
\]
Die Inverse kann man bestimmen, indem man den
Gauss-Algorithmus in $\mathbb{F}_{7}$ durchführt.
Die Arithmetik in $\mathbb{F}_{7}$ ist etwas ungewohnt, insbesondere
die Pivot-Division ist etwas mühsam, daher sind in
Abbildung~\ref{buch:endlichekoerper:fig:additionmultiplikation}
die Additions- und Multiplikationstabellen zusammengestellt.
\begin{figure}
\begin{center}
\begin{tabular}{|>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
\hline
+&0&1&2&3&4&5&6\\
\hline
0&0&1&2&3&4&5&6\\
1&1&2&3&4&5&6&0\\
2&2&3&4&5&6&0&1\\
3&3&4&5&6&0&1&2\\
4&4&5&6&0&1&2&3\\
5&5&6&0&1&2&3&4\\
6&6&0&1&2&3&4&5\\
\hline
\end{tabular}
\qquad
\begin{tabular}{|>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
\hline
\cdot
 &0&1&2&3&4&5&6\\
\hline
0&0&0&0&0&0&0&0\\
1&0&1&2&3&4&5&6\\
2&0&2&4&6&1&3&5\\
3&0&3&6&2&5&1&4\\
4&0&4&1&5&2&6&3\\
5&0&5&3&1&6&4&2\\
6&0&6&5&4&3&2&1\\
\hline
\end{tabular}
\end{center}
\caption{Additions- und Multiplikationstabelle für das Rechnen im
Galois-Körper $\mathbb{F}_7$.
Die multiplikative Inverse eines Elements in $a\in\mathbb{F}_7^*$
findet man, indem man in der Multiplikationstabelle in der Zeile
$a$ die Spalte mit der $1$ sucht, diese Spalte ist mit der multiplikativen
Inversen von $a$ angeschrieben.
\label{buch:endlichekoerper:fig:additionmultiplikation}}
\end{figure}
Mit dieser Rechenhilfe kann jetzt der Gaussalgorithmus leicht durchgeführt
werden:
\begin{align*}
\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
\hline
 1& 1& 6& 1& 0& 0\\
 2& 4& 5& 0& 1& 0\\
 2& 5& 1& 0& 0& 1\\
\hline
\end{tabular}
&\rightarrow
\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
\hline
 1& 1& 6& 1& 0& 0\\
 0& 2& 0& 5& 1& 0\\
 0& 3& 3& 5& 0& 1\\
\hline
\end{tabular}
\rightarrow
\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
\hline
 1& 1& 6& 1& 0& 0\\
 0& 1& 0& 6& 4& 0\\
 0& 0& 3& 1& 2& 1\\
\hline
\end{tabular}
\\
&\rightarrow
\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
\hline
 1& 1& 6& 1& 0& 0\\
 0& 1& 0& 6& 4& 0\\
 0& 0& 1& 5& 3& 5\\
\hline
\end{tabular}
\\
&\rightarrow
\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
\hline
 1& 1& 0& 6& 3& 5\\
 0& 1& 0& 6& 4& 0\\
 0& 0& 1& 5& 3& 5\\
\hline
\end{tabular}
\rightarrow
\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}>{$}c<{$}>{$}c<{$}|}
\hline
 1& 0& 0& 0& 6& 5\\
 0& 1& 0& 6& 4& 0\\
 0& 0& 1& 5& 3& 5\\
\hline
\end{tabular}
\end{align*}
Für die Durchführung braucht man die Inversen
der Pivot-Elemente in $\mathbb{F}_7$, sie sind $2^{-1}=4$ und $3^{-1}=5$.
Im rechten Teil des Tableau steht jetzt die inverse Matrix
\[
A^{-1}
=
B=\begin{pmatrix}
 0& 6& 5\\
 6& 4& 0\\
 5& 3& 5
\end{pmatrix}.
\]
Daraus können wir jetzt das inverse Element
\[
b(\alpha) = 6\alpha+5\alpha^2
\]
ablesen.
Zur Kontrolle berechnen wir das Produkt $b(X)\cdot a(X)$, es ist
\begin{align*}
(1+2X+2X^2)(6X+5X^2)
&=
10X^4 + 22X^3 + 17X^2 + 6X
\\
&=
3X^4+X^3+3X^2+6X.
\intertext{
Dieses Polynom muss jetzt mit dem Polynom $m(X)$ reduziert
werden, wir subtrahieren dazu $3Xm(X)$ und erhalten}
&=
-5X^3-3X^2-3X
\\
&=
2X^3+4X^2+4X.
\intertext{Die vollständige Reduktion wird erreicht, indem wir nochmals
$2m(X)$ subtrahieren:}
&=
-6 \equiv 1\mod 7,
\end{align*}
das Element $b(\alpha)=6\alpha+5\alpha^2$ ist also tatsächlich
das inverse Element von
$a(\alpha)=1+2\alpha+2\alpha^2$ in $\mathbb{F}_7(\alpha)$.
\label{buch:endlichekoerper:beispiel:inversemitmatrix}
\end{beispiel}

Die Matrixrealisation von $\Bbbk(\alpha)$ führt also auf eine effiziente
Berechnungsmöglichkeit für das Inverse eines Elements von $\Bbbk(\alpha)$.

\subsubsection{Algebraische Konstruktion}
Die Matrixdarstellung von $\alpha$ ermöglicht eine rein algebraische
und für die Rechnung besser geeignete Konstruktion.
Für jedes Polynom $f\in\Bbbk[X]$ ist $f(M_\alpha)\in M_n(\Bbbk)$.
Dies definiert einen Homomorphismus
\[
\varphi\colon \Bbbk[X] \to M_n(\Bbbk) : f \mapsto f(M_\alpha).
\]
Wir haben früher schon gesehen, dass das Bild dieses Homomorphismus
genau die Menge $\Bbbk(M_\alpha)$ ist.
Allerdings ist $\varphi$ nicht injektiv, das Polynom $m$ wird zum
Beispiel auf $\varphi(m) = m(M_\alpha) = 0$ abgebildet.

Der Kern von $\varphi$ besteht aus allen Polynomen $p\in\Bbbk[X]$,
für die $p(M_\alpha)=0$ gilt.
Da aber alle Matrizen $I,M_\alpha,\dots,M_\alpha^{n-1}$ linear
unabhängig sind, muss ein solches Polynom den gleichen Grad haben
wie $m$, und damit ein Vielfaches von $m$ sein.
Der Kern besteht daher genau aus den Vielfachen von $m(X)$,
$\ker\varphi = m(X)\Bbbk[X]$.

Es ist nicht a priori klar, dass der Quotient $R/I$ für ein
Ideal $I\subset R$ ein Körper ist.
Hier spielt es eine Rolle, dass das von $m$ erzeugte Ideal
maximal ist im folgenden Sinne.

\begin{definition}
Ein Ideal $I\subset R$ heisst {\em maximal}, wenn für jedes andere Ideal
$J$ mit $I\subset J\subset R$ entweder $I=J$ oder $J=R$ gilt.
\end{definition}

\begin{beispiel}
Die Ideale $p\mathbb{Z}\subset \mathbb{Z}$ sind maximal genau dann, wenn
$p$ eine Primzahl ist.

Ist nämlich $p=n_1n_2$ eine Faktorisierung, dann ist
$\mathbb{Z}\supset n_1\mathbb{Z} \supset p\mathbb{Z}$ 
und $n_1\mathbb{Z}$ ist ein grössers Ideal als $p\mathbb{Z}$,
d.~h.~$p\mathbb{Z}$ ist nicht maximal.

In $\mathbb{Z}$ sind alle Ideale von der Form $n\mathbb{Z}$.
Wenn es also ein Ideal $I\supset p\mathbb{Z}$ gibt, welches
$p\mathbb{Z}$ echt enthält, dann gibt es $n\in\mathbb{Z}$ derart,
dass $n\mathbb{Z} \subset p\mathbb{Z}$.
Dies ist gleichbedeutend damit, dass $n$ ein echter Teiler von $p$
ist, also ist $p$ keine Primzahl.
\end{beispiel}

\begin{satz}
Der Ring $R/I$ ist genau dann ein Körper, wenn $I$ ein maximales Ideal ist.
\end{satz}

\begin{proof}[Beweis]
Nehmen wir zunächst an, dass $I$ ein maximales Ideal ist.
Damit $R/I$ ein Körper ist, muss jedes von $0$ verschiedene Element 
eine multiplikatives Inverses haben.
Sei als $a\in R\setminus I$, dann ist $a+I$ ein von $0$ verschiedenes
Körperelement.
Die Menge $Ra+I$ ist dann ein Ideal von $R$, welches $I$ echt enthält.
Weil $I$ maximal ist, ist $Ra+I=R$, also gibt es ein Element $b\in I$
derart, dass $ab+I=1+I$, d.~h.~$b+I$ ist das gesuchte multiplikative 
Inverse.

Sei nun umgekehrt $R/I$ ein Körper und $J\supset I$ sei ein Ideal,
welches $I$ echt enhält.
Sei $a\in J\setminus I$.
Da $R/I$ ein Körper ist, ist $a+I$ invertierbar, es gibt also ein
$b\in R$ mit $ab+I=1+I$.
Da $a\in J$ ist, folgt $Ra\subset J$.
Andererseits ist $1\in Ra$, also ist $J=R$ und das Ideal $J$ ist maximal.
\end{proof}

Ein irreduzibles Polynom $m\in\Bbbk[X]$ erzeugt ein maximales Ideal,
somit ist $\Bbbk[X]/m\Bbbk[X]\cong \Bbbk(M_\alpha) \cong \Bbbk(\alpha)$.

\subsubsection{Reduktion modulo $m$}
Die algebraische Konstruktion hat gezeigt, dass die arithmetischen
Operationen im Körper $\Bbbk(\alpha)$ genau die Operationen 
in $\Bbbk[X]/m\Bbbk[X]$ sind.
Eine ``Zahl'' in $\Bbbk(\alpha)$ wird also durch ein Polynom vom 
$n-1$ dargestellt.
Addieren und Subtrahieren erfolgen koeffizientenweise in $\Bbbk$.
Bei der Multiplikation entsteht möglicherweise ein Polynom grösseren
Grades, mit dem Polynomdivisionsalgorithmus kann der Rest bei Division
durch $m$ ermittelt werden.

\begin{beispiel}
Das Polyonom $f=X^5+X^4+X^3+X^2+X^1+1\in\mathbb{F}_7[X]$ soll modulo
$m(X)=X^3+2X^2+2X^2+3$ reduziert werden.
Wir führen die Polynomdivision in $\mathbb{F}_7[X]$ durch, die
Multiplikationstabelle von $\mathbb{F}_7$ in
Abbildung~\ref{buch:endlichekoerper:fig:additionmultiplikation}
ist dabei wieder hilfreich.
\[
\arraycolsep=1.4pt
\begin{array}{rcrcrcrcrcrcrcrcrcrcrcrcr}
X^5&+& X^4&+& X^3&+& X^2&+& X&+&1&:&X^3&+&2X^2&+&2X&+&3&=&X^2&+&6X&+&1\rlap{$\mathstrut=q$}\\
\llap{$-($}X^5&+&2X^4&+&2X^3&+&3X^2\rlap{$)$}& &  & & & &   & &    & &  & & & &   & &  & & \\
\cline{1-7}
   & &6X^4&+&6X^3&+&5X^2&+& X& & & &   & &    & &  & & & &   & &  & & \\
   & &\llap{$-($}6X^4&+&5X^3&+&5X^2&+&4X\rlap{$)$}& & & &   & &    & &  & & & &   & &  & & \\
\cline{3-9}
   & &    & & X^3& &    &+&4X&+&1& &   & &    & &  & & & &   & &  & & \\
   & &    & &\llap{$-($}X^3&+&2X^2&+&2X&+&3\rlap{$)$}& &   & &    & &  & & & &   & &  & & \\
\cline{5-11}
   & &    & &    & &5X^2&+&2X&+&5\rlap{$\mathstrut=r$}& &   & &    & &  & & & &   & &  & & \\
\end{array}
\]
Die Kontrolle
\[
\arraycolsep=1.4pt
\begin{array}{rcrcrcrcrcrcr}
\llap{$($}X^2&+&  6X&+&   1\rlap{$)$}&\cdot&\llap{$($} X^3&+&2X^2&+&2X&+&3\rlap{$)$}\\
\cline{1-13}
   & &    & &    &     & X^3&+&2X^2&+&2X&+&3\\
   & &    & &6X^4&  +  &5X^3&+&5X^2&+&4X& & \\
   & & X^5&+&2X^4&  +  &2X^3&+&3X^2& &  & & \\
\cline{3-13}
   & & X^5&+& X^4&  +  & X^3&+&3X^2&+&6X&+&3\rlap{$\phantom{)}=q\cdot m$}\\
   & &    & &    &     &    & &\llap{$+($}5X^2&+&2X&+&5\rlap{$)=r$}\\
\cline{3-13}
   & & X^5&+& X^4&  +  & X^3&+& X^2&+& X&+&1\\
\cline{3-13}
\end{array}
\]
zeigt $f=qm+r$ und damit die Korrektheit der Rechnung.
\end{beispiel}

Die Identität $m(\alpha)=0$ kann aber auch wie folgt interpretiert werden.
Sei der Grad von $f$ mindestens so gross wie der von $m$, also
$l=\deg f\ge \deg m=n$.
Indem man mit $\alpha^{l-n}$ multipliziert, erhält man die Relation
\[
\alpha^l + m_{n-1}\alpha^{l-1} + m_{n-2}\alpha^{l-2}+\dots +a_1\alpha^{l-n+1} + a_0\alpha^{l-n} = 0.
\]

Ist $f_l$ der führende Koeffizient des Polynoms $f$, dann ist
$f-f_0mX^{n-l}$ ein Polynom vom Grad $l-1$, welches modulo $m$
mit $f$ übereinstimmt.
Indem man dies wiederholt, kann man also die Reduktion finden, ohne
den Polynomdivisionsalgorithmus durchzuführen.
Man erhält auf diese Weise zwar den Quotienten $q$ nicht, aber den
Rest $r$ kann man trotzdem bekommen.

\begin{beispiel}
Wir wenden den eben beschriebenen Algorithmus wieder auf das
Polynom $f=X^5+X^4+X^3+X^2+X+1$ an und erhalten:
\[
\arraycolsep=1.4pt
\begin{array}{rcrcrcrcrcr}
X^5&+& X^4&+& X^3&+& X^2&+& X&+&1\\
\llap{$-($}X^5&+&2X^4&+&2X^3&+&3X^2\rlap{$\mathstrut =X^2m)$}& &  & & \\
\cline{1-11}
   & &6X^4&+&6X^3&+&5X^2&+& X&+&1\\
   & &\llap{$-($}6X^4&+&5X^3&+&5X^2&+&4X\rlap{$\mathstrut =6Xm)$}& & \\
\cline{3-11}
   & &    & & X^3& &    &+&4X&+&1\\
   & &    & & \llap{$-($}X^3&+&2X^2&+&2X&+&3\rlap{$\mathstrut =m)$}\\
\cline{5-11}
   & &    & &    & &5X^2&+&2X&+&5\rlap{$\mathstrut =r$}\\
\end{array}
\]
Dies ist derselbe Rest wie wir mit dem Divisionsalgorithmus
gefunden haben.
\end{beispiel}

Diese Form des Reduktionsalgorithmus ist in einem Körper $\mathbb{F}_2$
besonders leicht durchzuführen, da dort die Addition und die Subtraktion
der Koeffizienten übereinstimmen.
Die Multiplikation mit $X$ ist nichts anders als ein Shift der
Koeffizienten.

\subsubsection{Multiplikative Inverse}
Die schwierigste Operation in $\Bbbk(\alpha)$ ist die Division.
Wie bei der Berechnung der Inversion in einem Galois-Körper $\mathbb{F}_p$
kann dafür der euklidische Algorithmus verwendet werden.
Sei also $f\in\Bbbk[X]$ ein Polynom vom Grad $\deg f <\deg m$, es soll
das multiplikative Inverse gefunden werden.
Da $m$ ein irreduzibles Polynom ist, müssen $f$ und $m$ teilerfremd sein.
Der euklidische Algorithmus liefert zwei Polynome $s,t\in\Bbbk[X]$ derart,
dass
\[
sf+tm=1.
\]
Reduzieren wir modulo $m$, wird daraus $af=1$ in $\Bbbk[X]/m\Bbbk[X]$.
Das Polynom $a$, reduziert modulo $m$, ist also die multiplikative
Inverse von $f$.

Bei der praktischen Durchführung des euklidischen Algorithmus ist der 
letzte Rest $r_{n-1}$ oft nicht $1$ sondern ein anderes Element von
$\mathbb{F}_p^*$.
Die Linearkombination von $f$ und $m$ mit den berechneten Faktoren
$s$ und $t$ ist daher auch nicht $1$, sondern 
\[
sf+tm=r_{n-1}.
\]
Da aber alle Elemente in $\mathbb{F}_p^*$ invertierbar sind, kann man
durch $r_{n-1}$ dividieren, was
\[
r_{n-1}^{-1}sf+r_{n-1}^{-1}tm=1
\]
ergibt.
Also ist $r_{n-1}^{-1}s$ die gesuchte Inverse in $\mathbb{F}_p(\alpha)$,
dies passiert auch im folgenden Beispiel.

\begin{beispiel}
Auf 
Seite~\pageref{buch:endlichekoerper:beispiel:inversemitmatrix}
haben wir die multiplikative Inverse von
$f=2X^2+2X+1\in\mathbb{F}_7[X]/m\mathbb{F}_7[X]$ 
mit $m = X^3 + 2X^2 + 2X + 3$
mit Hilfe von Matrizen berechnet, hier soll sie jetzt nochmals
mit dem euklidischen Algorithmus berechnet werden.

Zunächst müssen wir den euklidischen Algorithmus für die beiden Polynome
$f$ und $m$ durchführen.
Der Quotient $m:f$ ist:
\[
\arraycolsep=1.4pt
\begin{array}{rcrcrcrcrcrcrcrcr}
  X^3&+&2X^2&+&2X&+&3&:&2X^2&+&2X&+&1&=&4X&+&4\rlap{$\mathstrut=q_0$}\\
\llap{$-($}X^3&+& X^2&+&4X\rlap{$)$}& & & &    & &  & & & &  & & \\ \cline{1-5}
     & & X^2&+&5X&+&3& &    & &  & & & &  & & \\
     &&\llap{$-(\phantom{2}$}X^2&+& X&+&4\rlap{$)$}& &    & &  & & & &  & & \\ \cline{3-7}
     & &    & &4X&+&6\rlap{$\mathstrut=r_0$}& &    & &  & & & &  & &
\end{array}
\]
Jetzt muss der Quotient $f:r_0$ berechnet werden:
\[
\arraycolsep=1.4pt
\begin{array}{rcrcrcrcrcrcrcrcr}
  2X^2&+&2X&+&1&:&4X&+&6&=&4X&+&5\rlap{$\mathstrut=q_1$}\\
\llap{$-($}2X^2&+&3X\rlap{$)$}& & & &  & & & &  \\ \cline{1-3}
      & &6X&+&1& &  & & & &  \\
      & &\llap{$-($}6X&+&2\rlap{$)$}& &  & & & &  \\ \cline{3-5}
      & &  & &6\rlap{$\mathstrut=r_1$}& & & &  & & & &
\end{array}
\]
Da der Rest $r_1\in\mathbb{F}_7^*$ liegt, gibt die nächste Division
natürlich den Rest $0$ und der letzte nicht verschwindende Rest ist
$r_{1}=6$:
\[
\arraycolsep=1.4pt
\begin{array}{rcrcrcrcr}
4X&+&6&:&6&=&3X&+&1\rlap{$\mathstrut=q_2$} \\
\llap{$-($}4X\rlap{$)$}& & & & & &  & &  \\ \cline{1-1}
 0&+&6& & & &  & & \\
  & &\llap{$-($}6\rlap{$)$}& & & &  & &\\ \cline{3-3}
  & &0\rlap{$\mathstrut=r_2$}& & & &  & &
\end{array}
\]
Damit ist der euklidische Algorithmus abgeschlossen.

Durch Ausmultiplizieren der Matrizen $Q(-q_i)$ können wir jetzt auch die 
Faktoren $s$ und $t$ finden.
\begin{align*}
Q=\begin{pmatrix}
s&t\\
*&*
\end{pmatrix}
&= Q(q_2)Q(q_1)Q(q_0)
=
\begin{pmatrix}0&1\\1&-q_2\end{pmatrix}
\begin{pmatrix}0&1\\1&-q_1\end{pmatrix}
\begin{pmatrix}0&1\\1&-q_0\end{pmatrix}
\\
&=
\begin{pmatrix}
0&1\\
1&4X+6
\end{pmatrix}
\begin{pmatrix}
0&1\\
1&3X+2
\end{pmatrix}
\begin{pmatrix}
0&1\\
1&3X+3
\end{pmatrix}
\\
&=
\begin{pmatrix}
0&1\\
1&4X+6
\end{pmatrix}
\begin{pmatrix}
   1&3X+3\\
3X+2&2X^2 + X
\end{pmatrix}
\\
&=
\begin{pmatrix}
3X+2           &2X^2+X\\
1+(4X+6)(3X+2) &3X+3 + (4X+6)(2X^2+X)
\end{pmatrix}
\\
&=
\begin{pmatrix}
     3X+2 & 2X^2     +X\\
5X^2+5X+6 &  X^3+2X^2+2X+6
\end{pmatrix}.
\end{align*}
Daraus liest man
\[
s
=
2X^2+X
\qquad\text{und}\qquad
t
=
3X+2
\]
ab.
Wir überprüfen, ob die Koeffizienten der ersten Zeile tatsächlich $m$ und $f$
zu $r_1=6$ kombinieren.
Es ist
\begin{align*}
(3X+2)\cdot m + (2X^2+X)\cdot f
&= 
(3X+2)
(X^3+3X^2+X+2)
+
(2X^2+X)
(2X^2+2X+1)
=
6=r_1.
\end{align*}
Die multiplikative Inverse ist daher
$
r_1^{-1}(2X^2 + X)
=
6^{-1}
(2X^2 + X)
=
6
(2X^2 + X)
=
5X^2+6X$,
was mit dem Beispiel von
Seite~\pageref{buch:endlichekoerper:beispiel:inversemitmatrix}
übereinstimmt.
\end{beispiel}

Besonders einfach ist die Rechung für $\Bbbk=\mathbb{F}_2$.
Dieser Spezialfall ist für die praktische Anwendung in der Kryptographie
von besonderer Bedeutung, daher wird er im 
Kapitel~\ref{buch:chapter:kryptographie} genauer untersucht.