% % 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 \[ \alpha = \frac{-1+i\sqrt{3}}2\in\mathbb{C} \] \label{buch:endliche-koerper:eqn:1iwurzel3} 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}\;|\; 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 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.