diff options
Diffstat (limited to 'buch/chapters/30-endlichekoerper/wurzeln.tex')
| -rw-r--r-- | buch/chapters/30-endlichekoerper/wurzeln.tex | 78 |
1 files changed, 43 insertions, 35 deletions
diff --git a/buch/chapters/30-endlichekoerper/wurzeln.tex b/buch/chapters/30-endlichekoerper/wurzeln.tex index e3731d5..1118387 100644 --- a/buch/chapters/30-endlichekoerper/wurzeln.tex +++ b/buch/chapters/30-endlichekoerper/wurzeln.tex @@ -15,12 +15,13 @@ 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. +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önnte. +finden könnten. Im Altertum fiel dieses Problem zunächst den Pythagoreern auf. Wenn $\sqrt{2}$ kein Bruch ist, was ist es dann? @@ -46,7 +47,7 @@ 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''. +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. @@ -62,7 +63,7 @@ genauer zu charakterisieren. \subsection{Irreduzible Polynome \label{buch:subsection:irreduziblepolynome}} -Die Zahlen, die man dem Körper hinzufügen möchte, müssen Nullstellen +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 @@ -89,7 +90,8 @@ 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. +in zwei Faktoren $g,h\in \Bbbk[X]$ geringeren Grades mit $f=gh$ zerlegen +lässt. \index{irreduzibles Polynom}% \end{definition} @@ -101,10 +103,10 @@ 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 +Nur die Ordnungsrelation 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 +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$. @@ -130,9 +132,11 @@ X^2 -2 \mod 23, \begin{beispiel} Die Zahl \[ -\alpha = \frac{1+i\sqrt{3}}2 +\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 @@ -178,7 +182,7 @@ 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$, +$\deg m=n>1$, wir dürfen es als normiert annehmen und schreiben es in der Form \[ m(X) @@ -238,7 +242,7 @@ Basisvektoren von $\Bbbk(\alpha)$ wirkt: \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} +\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. \] @@ -255,8 +259,7 @@ M_{\alpha} & & & & 1 &-m_{n-1} \end{pmatrix}. \] -%TODO: Was ist hier die Aussage? -Aufgrund der Konstruktion die Lineare Abbildung $m(M_\alpha)$, +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. @@ -264,7 +267,9 @@ 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 +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 @@ -317,7 +322,7 @@ M_\alpha^2+M_\alpha+I \] Die Matrix ist also eine mögliche Realisierung für das ``mysteriöse'' Element $\alpha$. -Es hat alle algebraischen Eigenschaften von $\alpha$. +Sie hat alle algebraischen Eigenschaften von $\alpha$. \end{beispiel} Die Menge $\Bbbk(\alpha)$ kann durch die Abbildung $\alpha\mapsto M_\alpha$ @@ -335,12 +340,14 @@ 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 +\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$ direkt invertieren: +Tatsächlich kann man die Matrix $M_\alpha$ z.~B.~direkt invertieren: \[ M_\alpha^{-1} = @@ -527,8 +534,8 @@ werden: \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$. +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} @@ -544,28 +551,29 @@ Daraus können wir jetzt das inverse Element b(\alpha) = 6\alpha+5\alpha^2 \] ablesen. -Das Produkt $b(X)\cdot a(X)$ ist +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 +3X^4+X^3+3X^2+6X. \intertext{ -Diese Polynom muss jetzt mit dem Minimalpolynom $m(X)$ reduziert +Dieses 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 +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 +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} @@ -588,9 +596,9 @@ 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 +Da aber alle Matrizen $I,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. +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]$. @@ -641,7 +649,7 @@ 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$ folgt $Ra\subset J$. +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} @@ -652,10 +660,10 @@ somit ist $\Bbbk[X]/m\Bbbk[X]\cong \Bbbk(M_\alpha) \cong \Bbbk(\alpha)$. 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 +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 +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. @@ -739,8 +747,8 @@ 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 +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. @@ -919,5 +927,5 @@ Seite~\pageref{buch:endlichekoerper:beispiel:inversemitmatrix} 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. +Kapitel~\ref{buch:chapter:kryptographie} genauer untersucht. |