diff options
Diffstat (limited to 'buch/chapters/30-endlichekoerper/wurzeln.tex')
| -rw-r--r-- | buch/chapters/30-endlichekoerper/wurzeln.tex | 894 |
1 files changed, 894 insertions, 0 deletions
diff --git a/buch/chapters/30-endlichekoerper/wurzeln.tex b/buch/chapters/30-endlichekoerper/wurzeln.tex index 9ad0800..02429dc 100644 --- a/buch/chapters/30-endlichekoerper/wurzeln.tex +++ b/buch/chapters/30-endlichekoerper/wurzeln.tex @@ -3,7 +3,901 @@ % % (c) 2021 Prof Dr Andreas Müller, Hochschule Rapperswil % +% !TeX spellcheck = de_CH \section{Wurzeln \label{buch:section:wurzeln}} \rhead{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 $\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önnte. + +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 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]$ 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 Vergleichsrelation ermöglicht, die negative Wurzel von der +positiven zu unterscheiden. +Das Polynom kann in $\mathbb{Q}$ nicht faktorisiert werden, denn die +einzig 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 +\[ +\alpha = \frac{1+i\sqrt{3}}2 +\] +ist eine Nullstelle des Polynoms $f(X)=X^3-1\in\mathbb{Z}[X]$. +$\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 daher 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$, +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}\;|\; 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}. +\] +%TODO: Was ist hier die Aussage? +Aufgrund der Konstruktion 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 einem früheren Beispiel 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$. +Es 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} +Im Moment wissen wir noch nicht, wie wir $\alpha^{-1}$ berechnen sollten. +Wir können aber auch die Matrizendarstellung verwenden. +Für Matrizen wissen wir selbstverständlich, wie Matrizen invertiert +werden können. +Tatsächlich kann man die Matrix $M_\alpha$ 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 in $\mathbb{F}_7$ +der Pivot-Elemente, 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. +Das Produkt $b(X)\cdot a(X)$ 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{ +Diese Polynom muss jetzt mit dem Minimalpolynom $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 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 $E,M_\alpha,\dots,M_\alpha^{n-1}$ linear +unabhängig sind, muss ein solches Polynom den gleichen Grad haben +we $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. + +TODO: XXX Begründung +\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] +\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öglicherwise 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 besonders leicht durchzuführen +in einem Körper $\mathbb{F}_2$, 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 module $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 +In Kapitel~\ref{buch:chapter:kryptographie} genauer untersucht. + +\subsection{Zerfällungskörper +\label{buch:subsection:zerfaellungskoerper}} +XXX TODO + + + |