From 7ba2b33ce9ed11753a1bb80d833354393f7e7603 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Wed, 22 Sep 2021 21:06:58 +0200 Subject: zweite Leseung Kapitel 3 und 4 --- buch/chapters/20-polynome/chapter.tex | 14 ++--- buch/chapters/20-polynome/definitionen.tex | 35 ++++++------ buch/chapters/20-polynome/vektoren.tex | 17 +++--- buch/chapters/30-endlichekoerper/chapter.tex | 2 +- buch/chapters/30-endlichekoerper/euklid.tex | 80 +++++++++++++++++++--------- buch/chapters/30-endlichekoerper/galois.tex | 68 +++++++++++------------ buch/chapters/30-endlichekoerper/wurzeln.tex | 78 +++++++++++++++------------ 7 files changed, 169 insertions(+), 125 deletions(-) diff --git a/buch/chapters/20-polynome/chapter.tex b/buch/chapters/20-polynome/chapter.tex index fd72a59..19f0221 100644 --- a/buch/chapters/20-polynome/chapter.tex +++ b/buch/chapters/20-polynome/chapter.tex @@ -33,7 +33,7 @@ In dieser eher arithmetischen Sichtweise ist es aber eigentlich egal, dass in \eqref{buch:eqn:polynome:polynom} nur einfache Multiplikationen und Additionen vorkommen. In einem Programm könnten ja auch beliebig komplizierte Operationen -verwendet werden, warum also diese Beschränkung. +verwendet werden, warum also diese Beschränkung? Für die nachfolgenden Betrachtungen stellen wir uns $X$ daher nicht mehr einfach als einen Platzhalter für eine Zahl vor, sondern als ein neues @@ -88,7 +88,8 @@ Die ganzen Zahlen $\mathbb{Z}$ kommen dafür in Frage, aber auch die rationalen oder reellen Zahlen $\mathbb{Q}$ und $\mathbb{R}$. Man kann sogar noch weiter gehen: man kann als Koeffizienten auch Vektoren oder sogar Matrizen zulassen. -Polynome können addiert werden, indem die Koeffizienten addiert werden. +Polynome können addiert werden, indem die Koeffizienten addiert werden, +und sie können mit Skalaren aus dem Koeffizentenkörper multipliziert werden. Polynome können aber auch multipliziert werden, was auf die Faltung der Koeffizienten hinausläuft: \begin{align} @@ -103,15 +104,14 @@ a_{n}b_{m}X^{n+m} + (a_{n}b_{m-1}+a_{n-1}b_{m})X^{n+m-1} + -\dots -+ -\sum_{i + j = k}a_ib_j X^k -+ -\dots +\ldots + (a_1b_0+a_0b_1)X + a_0b_0 +\\ +&= +\sum_{i + j = k}a_ib_j X^k. \label{buch:eqn:polynome:faltung} \end{align} Dies ist aber nur möglich, wenn die Koeffizienten selbst miteinander diff --git a/buch/chapters/20-polynome/definitionen.tex b/buch/chapters/20-polynome/definitionen.tex index 3c541d8..659a972 100644 --- a/buch/chapters/20-polynome/definitionen.tex +++ b/buch/chapters/20-polynome/definitionen.tex @@ -74,7 +74,7 @@ Ein Polynom heisst {\em normiert} oder auch {\em monisch}, wenn der \index{normiertes Polynom}% \index{Polynom!monisch}% \index{normiertes Polynom} -höchste Koeffizient oder auch {\em Leitkoeffizient} des Polynomus $1$ ist, +höchste Koeffizient oder auch {\em Leitkoeffizient} des Polynoms $1$ ist, also $a_n=1$. \index{Leitkoeffizient}% Wenn man in $R$ durch $a_n$ dividieren kann, dann kann man aus dem Polynom @@ -84,7 +84,7 @@ $p(X)=a_nX^n+\dots$ mit Leitkoeffizient $a_n$ das normierte Polynom X^n + \frac{a_{n-1}}{a_n}X^{n-1} + \dots + \frac{a_0}{a_n} \] machen. -Man sagt auch, das Polynom $p(X)$ wurde normiert. +Man sagt auch, das Polynom $p(X)$ wurde {\em normiert}. Wenn $R$ ein Körper ist, ist die Normierung immer möglich. Die Tatsache, dass zwei Polynome nicht gleich viele von $0$ verschiedene Koeffizienten haben müssen, @@ -136,7 +136,7 @@ p(X)q(X)r(X) = p(X)(q(X)r(X)) \end{align*} -für die Multiplikation besagt, das es keine Rolle spielt, in welcher +für die Multiplikation besagen, dass es keine Rolle spielt, in welcher Reihenfolge man die Additionen oder Multiplikationen ausführt. % @@ -155,7 +155,7 @@ p(X) = a_nX^n + a_{n-1}X^{n-1}+\dots a_1X + a_0 \] hat den Grad $n$, wenn $a_n\ne 0$ ist. Der Grad von $p$ wird mit $\deg p$ bezeichnet. -Konstante Polynome $p(X)=a_0$ mit $a_0\ne 0$ hat den Grad $0$. +Das konstante Polynom $p(X)=a_0$ mit $a_0\ne 0$ hat den Grad $0$. Der Grad des Nullpolynoms $p(X)=0$ ist definiert als $-\infty$. \end{definition} @@ -196,24 +196,23 @@ p(X) &= a_nX^n + a_{n-1}X^{n-1} + \dots + a_1X + a_0&&\Rightarrow&\deg p&=n\\ q(X) &= b_mX^m + b_{m-1}X^{m-1} + \dots + b_1X + b_0&&\Rightarrow&\deg q&=m. \end{aligned} \] -Dann kann der höchste Koeffizient in der Summe $p+q$ nicht weiter oben +Dann kann der höchste Koeffizient in der Summe $p+q$ nicht ``weiter oben'' sein als die grössere von den beiden Zahlen $n$ und $m$ angibt, dies beweist \eqref{buch:eqn:polynome:gradsumme}. Ebenso kann der höchste Koeffizient im Produkt nach der -Formel~\eqref{buch:eqn:polynome:faltung} nicht weiter oben als bei +Formel~\eqref{buch:eqn:polynome:faltung} nicht ``weiter oben'' als bei $n+m$ liegen, dies beweist beweist \eqref{buch:eqn:polynome:gradprodukt}. In einem Ring mit Nullteilern (Siehe Definition~\ref{buch:grundlagen:def:nullteiler}) könnte es passieren, dass $a_nb_m=0$ ist, d.~h.~es ist durchaus möglich, dass der Grad kleiner ist. -Schliesslich kann der höchsten Koeffizient von $\lambda p(X)$ nicht grösser +Schliesslich kann der höchste Koeffizient von $\lambda p(X)$ nicht grösser als der höchste Koeffizient von $p(X)$ sein, was \eqref{buch:eqn:polynome:gradskalar} beweist. \end{proof} -In einem nullteilerfreien Ring gelten die Rechenregeln für den Grad -jetzt exakt: +In einem nullteilerfreien Ring gelten die Rechenregeln für den Grad exakt: \begin{lemma} Sei $R$ ein nullteilerfreier Ring und $p$ und $q$ Polynome über $R$ @@ -338,7 +337,7 @@ a &= a_nX^{n} + a_{n-1}X^{n-1} + \dots + a_1X^{1} + a_0 \\ b &= b_mX^{n} + b_{m-1}X^{n-1} + \dots + b_1X^{1} + b_0, \end{align*} -mit dem einzigen Unterschied, dass statt $X$ mit der festen Zahl $X=10$ +mit dem einzigen Unterschied, dass statt mit $X$ mit der festen Zahl $X=10$ gearbeitet wird. Der Divisionsalgorithmus für Polynome lässt sich aber leicht rekonstruieren. @@ -399,15 +398,16 @@ Fall, weil der führende Koeffizient $1$ war. Für beliebige Polynome $b\in R[X]$ ist dies aber nur dann immer der Fall, wenn die Koeffizienten in Tat und Wahrheit einem Körper entstammen. +\begin{beispiel} Im Folgenden betrachten wir daher nur noch Polynomringe mit Koeffizienten in einem Körper $\Bbbk$. In $\mathbb{Q}[X]$ ist die Division $a:b$ für die Polynome \begin{equation} \begin{aligned} a(X) &= X^4 - X^3 -7X^2 + X + 6\\ -b(X) &= X^2+X+1, +b(X) &= 2X^2+X+1, \end{aligned} -\label{buch:polynome:eqn:divisionsaufgabe} +\label{buch:polynome:eqn:divisionsaufgabe2} \end{equation} problemlos durchführbar: \[ @@ -424,8 +424,9 @@ X^4&-& X^3&-& 7X^2&+& X&+& 6&:&2X^2&+&X&+&1&=&\ \end{array} \] Der Algorithmus funktioniert selbstverständlich genauso in $\mathbb{R}[X]$ -oder $\mathbb{C}[X]$, und ebenso in den in +oder $\mathbb{C}[X]$ und ebenso in den in Kapitel~\ref{buch:chapter:endliche-koerper} studierten endlichen Körpern. +\end{beispiel} \subsubsection{Euklidische Ringe und Faktorzerlegung} Der Polynomring $\Bbbk[X]$ hat noch eine weitere Eigenschaft, die ihn @@ -462,7 +463,8 @@ kann auf eindeutige Art und Weise in ein Produkt von Primfaktoren zerlegt werden. \subsubsection{Irreduzible Polynome} -Das Konzept der Primzahl lässt sich wie folgt in den Polynomring übertragen. +Das Konzept der Primzahl lässt sich wie folgt in die Welt der Polynomringe +übertragen. \index{Primzahl}% \begin{definition} @@ -479,16 +481,17 @@ Sei jetzt $f=X^2+bX+c$ ein quadratisches Polynom in $\mathbb{Q}[X]$. Wenn es faktorisierbar sein soll, dann müssen die Faktoren Polynome ersten Grades sein, also $f=(X-x_1)(X-x_2)$ mit $x_i\in\mathbb{Q}$. Die Zahlen $x_i$ die einzigen möglichen Lösungen für $x_i$ können mit -der Lösungsformel für die quadratische Gleichung +der Lösungsformel \[ x_i = -\frac{b}2\pm\sqrt{\frac{b^2}{4}-c} \] +für die quadratische Gleichung gefunden werden. Die Faktorisierung ist also genau dann möglich, wenn $b^2/4-c$ ein Quadrat in $\mathbb{Q}$ ist. In $\mathbb{R}$ ist das Polynom faktorisierbar, wenn $b^2-4c\ge 0$ ist. In $\mathbb{C}$ gibt es keine Einschränkung, die Wurzel zu ziehen, -in $\mathbb{C}$ gibt es also keine irreduziblen Polynome im Grad $2$. +in $\mathbb{C}$ gibt es also keine irreduziblen Polynome vom Grad $2$. \end{beispiel} \subsubsection{Faktorisierung in einem Polynomring} diff --git a/buch/chapters/20-polynome/vektoren.tex b/buch/chapters/20-polynome/vektoren.tex index 0743592..e494477 100644 --- a/buch/chapters/20-polynome/vektoren.tex +++ b/buch/chapters/20-polynome/vektoren.tex @@ -108,7 +108,7 @@ b_0\\b_1\\\vdots\\b_m\\0\\\vdots \end{pmatrix} . \] -Die Moduln $R^{k+1}$ sind also alle ineinandergeschachtelt, können aber +Die Vektormengen $R^{k+1}$ sind also alle ineinandergeschachtelt, können aber alle auf konsistente Weise mit der Abbildung $\varphi$ in den Polynomring $R[X]$ abgebildet werden. \begin{center} @@ -165,10 +165,10 @@ der die Multiplikation mit $X$ beschreibt. Ist $p(X)$ ein Polynom, dann lässt sich die Multiplikation in von Polynome mit $R[X]$ ebenfalls als Operator schreiben. -Die Potenz $X^k$ wird durch $k$-fache Iteration des Operators +Die Potenz $X^k$ wirkt durch $k$-fache Iteration des Operators $X\cdot$. -Das Polynom $p(X)$ wird durch Linearkombination, entspricht -also dem Operator, den man durch Einsetzen von $X\cdot$ +Das Polynom $p(X)$ wirkt als Linearkombination der Operatoren $(X\cdot)^k$, +entspricht also dem Operator, den man durch Einsetzen von $X\cdot$ in das Polynom erhalten kann: \[ p(X\cdot) @@ -192,7 +192,7 @@ $(X\cdot)^k$ auch in Matrixform darstellen: 0&1&0&0&\dots\\ 0&0&1&0&\dots\\ \vdots&\vdots&\vdots&\ddots&\ddots -\end{pmatrix} +\end{pmatrix}, & (X\cdot)^k &= @@ -225,11 +225,14 @@ a_4 &a_3 & a_2 & a_1 & a_0 & \dots \\ Da die Matrix-Operation als Produkt $\text{Zeile}\times\text{Spalte}$ ausgeführt wird, kann man erkennen, dass das Polynomprodukt auch auf -eine Faltung hinausläuft. +eine Faltung hinausläuft: +Die Multiplikation einer Zeile der Matrix $p(X\cdot)$ mit +einem Spaltenvektor $b$ multipliziert den gespiegelten und verschobenen +Vektor der Koeffizienten $a$ mit den Koeffizienten $b$. Die wichtigste Lehre aus obigen Ausführungen aber ist die Beobachtung, dass sich eine ganz allgemeine Algebra -wie die der Polynome auf sehr direkte Art und Weise auf +wie die der Polynome auf sehr direkte Art und Weise abbilden lässt in eine Algebra von Matrizen auf einem geeigneten Vektorraum. Im vorliegenden Fall sind das zwar ``undendliche'' diff --git a/buch/chapters/30-endlichekoerper/chapter.tex b/buch/chapters/30-endlichekoerper/chapter.tex index b4c602e..b94ae48 100644 --- a/buch/chapters/30-endlichekoerper/chapter.tex +++ b/buch/chapters/30-endlichekoerper/chapter.tex @@ -29,7 +29,7 @@ Zu diesen sogenannten Galois-Körpern können wir dann weitere Elemente hinzufügen, wie das in Abschnitt ~\ref{buch:section:wurzeln} gezeigt wird. Diese Technik, die auch für den Körper $\mathbb{Q}$ funktioniert, erlaubt -dafür zu sorgen, dass in einem Körper gewisse algebraische Gleichungen +dafür zu sorgen, dass in einem Körper vorgebebene algebraische Gleichungen lösbar werden. \input{chapters/30-endlichekoerper/euklid.tex} diff --git a/buch/chapters/30-endlichekoerper/euklid.tex b/buch/chapters/30-endlichekoerper/euklid.tex index a75046f..7586273 100644 --- a/buch/chapters/30-endlichekoerper/euklid.tex +++ b/buch/chapters/30-endlichekoerper/euklid.tex @@ -8,6 +8,8 @@ \rhead{Der euklidische Algorithmus} Der euklidische Algorithmus bestimmt zu zwei gegebenen ganzen Zahlen $a$ und $b$ den grössten gemeinsamen Teiler $g$. +Wir schreiben $g|a$ für ``$g$ ist Teiler von $a$'' oder ``$g$ teilt $a$'', +gesucht ist also die grösste ganze Zahl $g$ derart, dass $g|a$ und $g|b$. \begin{definition} \label{buch:endliche-koerper:def:ggt} @@ -28,18 +30,16 @@ In diesem Abschnitt soll der Algorithmus zunächst für ganze Zahlen vorgestellt werden, bevor er auf Polynome verallgemeinert und dann in Matrixform niedergeschrieben wird. Die Matrixform ermöglicht, einfach zu implementierende iterative -Algorithmen für die Zahlen $s$ und $t$ un später auch für die +Algorithmen für die Zahlen $s$ und $t$ und später auch für die Berechnung des kleinsten gemeinsamen Vielfachen zu finden. % % Der euklidische Algorithmus für ganze Zahlen % \subsection{Grösster gemeinsamer Teiler ganzer Zahlen} -Gegeben sind zwei ganze Zahlen $a$ und $b$ und wir dürfen annehmen, -dass $a\ge b$. +Gegeben sind zwei ganze Zahlen $a$ und $b$. +Wir dürfen annehmen, dass $a\ge b$. Gesucht ist der grösste gemeinsame Teiler $g$ von $a$ und $b$. -Wir schreiben $g|a$ für ``$g$ ist Teiler von $a$'' oder ``$g$ teilt $a$'', -gesucht ist also die grösste ganze Zahl $g$ derart, dass $g|a$ und $g|b$. Ist $b|a$, dann ist offenbar $b$ der grösste gemeinsame Teiler von $a$ und $b$. @@ -70,7 +70,15 @@ neuen Quotienten $q_1$ und einen neuen Rest $r_1$ liefert mit $a_1-q_1b_1=r_1$. So entstehen vier Folgen von Zahlen $a_k$, $b_k$, $q_k$ und $r_k$ derart, dass in jedem Schritt gilt \begin{align*} -a_k - q_kb_k &= r_k & g&|a_k & g&|b_k & a_k &= b_{k-1} & b_k = r_{k-1}. +a_k - q_kb_k &= r_k +&&\wedge & +g&|a_k +&&\wedge & +g&|b_k +&&\wedge & +a_k &= b_{k-1} +&&\wedge & +b_k = r_{k-1}. \end{align*} Der Algorithmus bricht im Schritt $n$ ab, wenn $r_{n+1}=0$. Der letzte nicht verschwindende Rest $r_n$ muss daher der grösste gemeinsame @@ -109,7 +117,8 @@ Wir können sie aber verwenden, um die Zahlen $s$ und $t$ zu bestimmen. Wir drücken die Reste im obigen Beispiel durch die Zahlen $a_k$, $b_k$ und $q_k$ aus und setzen sie in den Ausdruck $g=a_5-q_5b_5$ ein, bis wir einen Ausdruck in $a_0$ und $b_0$ für $g$ finden: -\begin{align*} +\[ +\begin{aligned} r_5&=a_5-q_5 b_5=a_5-1\cdot b_5& g &= a_5 - 1 \cdot b_5 = b_4 - 1 \cdot r_4 \\ r_4&=a_4-q_4 b_4=a_4-2\cdot b_4& &= b_4 - (a_4 -2b_4) @@ -126,7 +135,8 @@ r_1&=a_1-q_1 b_1=a_1-3\cdot b_1& &= -7b_1 + 17(a_1-3b_1) \\ r_0&=a_0-q_0 b_0=a_0-3\cdot b_0& &= 17b_0 - 58(a_0t-3b_0) = -58a_0+191b_0 -\end{align*} +\end{aligned} +\] Tatsächlich gilt \[ -58\cdot 76415 + 191 \cdot 23205 = 85, @@ -339,7 +349,7 @@ berechnen. % Vereinfachte Durchführung des euklidischen Algorithmus % \subsection{Iterative Durchführung des erweiterten euklidischen Algorithmus -\label{buch:endlichekoerper:subsection:matrixschreibweise}} +\label{buch:endlichekoerper:subsection:erweitertereuklidischeralgo}} Die Durchführung des euklidischen Algorithmus mit Hilfe der Matrizen $Q(q_k)$ ist etwas unhandlich. In diesem Abschnitt sollen die Matrizenprodukte daher in einer Form @@ -348,6 +358,8 @@ dargestellt werden, die leichter als Programm zu implementieren ist. In Abschnitt~\ref{buch:endlichekoerper:subsection:matrixschreibweise} wurde gezeigt, dass das Produkt der aus den Quotienten $q_k$ gebildeten Matrizen $Q(q_k)$ berechnet werden muss. +Im Folgenden soll ein rekursiver Algorithmus zu seiner Berechnung +hergeleitet werden. Dazu beachten wir zunächst, dass die Multiplikation mit der Matrix $Q(q_k)$ die zweite Zeile in die erste Zeile verschiebt: \[ @@ -372,7 +384,7 @@ Die Matrizen \[ Q_k = Q(q_k)Q(q_{k-1})\cdots Q(q_0) \] -haben daher jeweils für aufeinanderfolgende Werte vo $k$ eine Zeile +haben daher jeweils für aufeinanderfolgende Werte von $k$ eine Zeile gemeinsam. Wir bezeichnen die Einträge der ersten Zeile der Matrix $Q_k$ mit $c_k$ und $d_k$. @@ -389,7 +401,7 @@ Q(q_k) \begin{pmatrix} c_{k-1}&d_{k-1}\\ c_{k} &d_{k} -\end{pmatrix} +\end{pmatrix}. \] Daraus ergeben sich die Rekursionsformeln \begin{equation} @@ -445,6 +457,15 @@ um die Spalten zur Berechnung der Koeffizienten $c_k$ und $d_k$ Wir schreiben die gefundenen Zahlen in eine Tabelle: \begin{center} \label{buch:endlichekoerper:beispiel1erweitert} +\begin{tikzpicture}[>=latex,thick] +\fill[color=darkgreen!30] (1.8,-0.4) rectangle (3.5,0.4); +\node at (3.10,0) {$\displaystyle +\color{darkgreen} +\begin{pmatrix} +\phantom{-33}\,\,&\phantom{-233}\\ +\phantom{-33}\,\,&\phantom{-233} +\end{pmatrix}\;=Q_2$}; +\node at (0,0) {$\displaystyle \renewcommand{\arraystretch}{1.1} \begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|} \hline @@ -460,7 +481,8 @@ k& a_k& b_k& q_k& r_k& c_k& d_k\\ 6& 340& 85& 4& 0& -58& 191\\ 7& 85& 0& & & 273& -899\\ \hline -\end{tabular} +\end{tabular}$}; +\end{tikzpicture} \end{center} Aus den letzten zwei Spalten der Tabelle kann man ablesen, dass \begin{align*} @@ -471,9 +493,10 @@ wie erwartet. Die gesuchten Zahlen $s$ und $t$ sind also $s=-58$ und $t=191$. \end{beispiel} -Die Matrizen $Q_k$ kann man auch as der Tabelle ablesen, sie bestehen +Die Matrizen $Q_k$ kann man auch aus der Tabelle ablesen, sie bestehen aus den vier Elementen in den Zeilen $k$ und $k+1$ in den Spalten $c_k$ und $d_k$. +Die Matrix $Q_2$ ist beispielhaft grün hervorgehoben. Auf jeder Zeile gilt $b_k = c_ka_0 + d_kb_0$, für $k>0$ ist dies $c_ka_0+d_kb_0=r_{k-1}$. @@ -527,7 +550,7 @@ durch das Problem der Teilbarkeit der Koeffizienten. Dieses Problem entfällt, wenn man die Koeffizienten aus einem Bereich wählt, in dem Teilbarkeit kein Problem ist, also in einem Körper.} verhält -sich bezüglich Teilbarkeit ganz genau gleich wie die ganzen Zahlen. +sich bezüglich Teilbarkeit ganz ähnlich wie die ganzen Zahlen. Insbesondere ist der euklidische Algorithmus genauso wie die Matrixschreibweise auch für Polynome durchführbar. @@ -595,7 +618,7 @@ ta+sb -4X^2+4X+8, \end{align*} und dies ist tatsächlich der gefundene grösste gemeinsame Teiler. -Die zweite Zeile von $Q$ gibt uns die Polynomfaktoren, mit denen +Die zweite Zeile von $Q$ gibt uns die Faktoren, mit denen $a$ und $b$ gleich werden: \begin{align*} q_{21}a+q_{22}b @@ -609,20 +632,23 @@ q_{21}a+q_{22}b \qedhere \end{align*} Man kann natürlich den grössten gemeinsamen Teiler auch mit Hilfe einer -Faktorisierung der Polynome $a$ und $b$ finden: +Faktorisierung der Polynome $a$ und $b$ finden. +Um die Übersicht zu erleichtern, werden gleiche Faktoren jeweils untereinander +geschrieben und fehlende Faktoren als Platzhalter in grau dargestellt. +\def\grau#1{\bgroup\color{gray!50}#1\egroup} \begin{align*} &\text{Faktorisierung von $a$:}& -a &= (X-3) (X-2)\phantom{(X-1)}(X+1) (X+2) \phantom{(X+3)}\\ +a &= (X-3) (X-2)\grau{(X-1)} (X+1) (X+2) \grau{(X+3)}\\ &\text{Faktorisierung von $b$:}& -b &=\phantom{(X-3)}(X-2) (X-1) (X+1)\phantom{(X+2)} (X+3) \\ +b &=\grau{(X-3)} (X-2) (X-1) (X+1) \grau{(X+2)} (X+3) \\ &\text{gemeinsame Faktoren:}& -g &=\phantom{(X-3)}(X-2)\phantom{(X-1)}(X+1)\phantom{(X+2)}\phantom{(X+3)} +g &=\grau{(X-3)} (X-2)\grau{(X-1)} (X+1) \grau{(X+2)}\grau{(X+3)} = X^2 -X + 2\\ && -v=a/g&= (X-3)\phantom{(X-2)(X-1)(X+1)} (X+2) \phantom{(X+3)} +v=a/g &= (X-3)\grau{(X-2) (X-1) (X+1)} (X+2) \grau{(X+3)} = X^2-X-6 \\ && -u=b/g&=\phantom{(X-3)(X-2)} (X-1)\phantom{(X+1)(X+2)}(X+3) +u=b/g&=\grau{(X-3) (X-2)} (X-1)\grau{(X+1) (X+2)} (X+3) = X^2+2X-3 \end{align*} Aus den letzten zwei Zeilen folgt @@ -702,7 +728,7 @@ Q(q_n)^{-1} \] Eine mögliche Lösung für die Matrix $K$ in \eqref{buch:eindlichekoerper:eqn:uvmatrix} -ist der die Matrix +ist daher die Matrix \[ K = @@ -715,7 +741,9 @@ Q(q_n). Insbesondere ist die Matrix $K$ die Inverse der früher gefundenen Matrix $Q$. -Die Berechnung der Matrix $K$ als Inverse von $Q$ ist nicht schwierig. +Die Berechnung der Matrix $K$ als Inverse von $Q$ ist nicht schwierig, +aber eingebaut in den bereits etablierten iterativen Prozess fällt +sie noch leichter. Genauso wie es möglich war, das Produkt $Q$ der Matrizen $Q(q_k)$ iterativ zu bestimmen, muss es auch eine Rekursionsformel für das Produkt der inversen Matrizen $Q(q_k)^{-1}$ geben. @@ -938,7 +966,9 @@ Man weiss zusätzlich noch, dass der euklidische Algorithmus genau drei Schritte braucht, es gibt also genau drei Quotienten, die in die Berechnung der Zahlen $e_k$ und $f_k$ einfliessen. -Im ersten Schritt des euklidischen Algorithmus ist der Quotient +In den folgenden Zeilen wird der euklische Algorithmus für die Polynome +$n(X)$ und $r(X)$ durchgeführt. +Im ersten Schritt ist der Quotient $n(X) / r(X)$ zu bestimmen, der Grad $1$ haben muss. \begin{align*} a_0=n(X) &= X^{12}+12 @@ -961,7 +991,7 @@ a_2 &= 10X^{10} + 5X^9 + 6X^8 + 8X^7 + \dots \\ b_2 &= 5X^9 + 10 X^8 + \dots \\ -q_2 &= 2X+10 +q_2 &= 2X+10. \end{align*} Aus den Polynomen $q_k$ können jetzt die Faktoren $u$ und $v$ bestimmt werden: diff --git a/buch/chapters/30-endlichekoerper/galois.tex b/buch/chapters/30-endlichekoerper/galois.tex index 7ffef0b..1d4a9c9 100644 --- a/buch/chapters/30-endlichekoerper/galois.tex +++ b/buch/chapters/30-endlichekoerper/galois.tex @@ -80,14 +80,14 @@ Beim Rechnen mit Resten modulo $n$ können Vielfache von $n$ ignoriert werden. Zum Beispiel gilt \[ \begin{aligned} -48&\equiv -1\mod 7& 48&=-1&&\text{in $\mathbb{Z}/7\mathbb{Z}$} +48&\equiv -1\mod 7&&\Leftrightarrow& 48&=-1&&\text{in $\mathbb{Z}/7\mathbb{Z}$} \\ -3\cdot 5=15&\equiv 1\mod 7 & 3\cdot 5&=1&&\text{in $\mathbb{Z}/7\mathbb{Z}$.} +3\cdot 5=15&\equiv\phantom{-}1\mod 7&&\Leftrightarrow & 3\cdot 5&=\phantom{-}1&&\text{in $\mathbb{Z}/7\mathbb{Z}$.} \end{aligned} \] Das Beispiel zeigt, dass man mindestens in $\mathbb{Z}/7\mathbb{Z}$ mit Resten ganz ähnlich rechnen kann wie in $\mathbb{Q}$. -In $\mathbb{Z}/7\mathbb{Z}$ scheinen $3$ und $5$ multiplikative inverse +In $\mathbb{Z}/7\mathbb{Z}$ scheinen $3$ und $5$ multiplikative Inverse zu sein. Tatsächlich kann man auf den Restklassen eine Ringstruktur definieren. @@ -97,7 +97,6 @@ Der Rest $a$ kann jede Zahl der Form $a+kn$ darstellen. Ebenso kann der Rest $b$ jede Zahl der Form $b+ln$ darstellen. Deren Summe ist $a+b+(k+l)n\equiv a+b\mod n$. Der Repräsentant des Restes hat also keinen Einfluss auf die Summe. - Ebenso ist das Produkt der beiden Repräsentaten $(a+kn)\cdot(b+ln) = ab + (al+bk)n + kln^2=ab + (al+bk+kln)n\equiv ab\mod n$ für jede Wahl von $k$ und $l$. @@ -105,7 +104,7 @@ Auch die Multiplikation ist also unabhängig vom gewählten Repräsentanten. \begin{definition} Die Menge $\mathbb{Z}/n\mathbb{Z}$ ist ein Ring, -heisst der {\em Restklassenring modulo $n$}. +er heisst der {\em Restklassenring modulo $n$}. \end{definition} \subsubsection{Division in $\mathbb{Z}/n\mathbb{Z}$} @@ -288,7 +287,7 @@ Primzahl ist. Wir betrachten dazu die Menge der nicht einfarbigen, geschlossenen Perlenketten der Länge $p$ mit $a$ Farben. Einge dieser Perlenketten unterscheiden sich nur durch eine -Drehung um einzelne Perlen. +Drehung um eine gewisse Anzahl Perlen. Sei $G$ die Menge der nicht einfarbigen, geschlossenen Perlenketten, die sich nicht nur um eine Drehung unterscheiden. @@ -362,14 +361,11 @@ $(p-1)!\equiv -1\mod p$. \begin{proof}[Beweis] Wenn $p$ keine Primzahl ist, dann lässt sich $p$ in Faktoren -$p=n_1\cdot n_2=p$ zerlegen. -Beide Faktoren kommen in der Liste $1,2,\dots,p-1$ vor. -Insbesondere haben $p=n_1n_2$ und $(p-1)!$ mindestens einen -der Faktoren $n_1$ oder $n_2$ gemeinsam, wir können annehmen, -dass $n_1$ dieser Faktor ist. -Es folgt, dass der grösste gemeinsame Teiler von $p$ und $(p-1)!$ -grösser als $n_1$ ist, auch $(p-1)!$ ein Vielfaches von $n_1$ in -$\mathbb{F}_p$. +$p=n_1\cdot n_2$ zerlegen. +Dies bedeutet auch, dass $n_1$ und $n_2$ Nullteiler sind in +$\mathbb{F}_p$, es ist also $n_1n_2=0\in\mathbb{F}_p$. +Beide Faktoren kommen in der Liste der Zahlen $1,2,\dots,p-1$ vor. +Daher muss auch $1\cdot2\cdot\dots\cdot(p-1)=(p-1)!=0\in\mathbb{F}_p$ sein. Insbesondere kann $(p-1)!$ nicht $-1\in\mathbb{F}_p$ sein. Ist andererseits $p$ eine Primzahl, dann sind die Zahlen $1, 2,\dots,p-1$ @@ -382,7 +378,7 @@ Daher ist auch $(a+1)(a-1)=0$, in $\mathbb{F}_p$ muss daher einer der Faktoren $0$ sein, also $a=-1$ oder $a=1$ in $\mathbb{F}_p$. Zu jeder Zahl $a\in\{2,\dots,p-2\}$ liegt die Inverse $a^{-1}$ -ebenfalls in diesen Bereich und ist verschieden von $a$: $a^{-1}\ne a$. +ebenfalls in diesem Bereich und ist verschieden von $a$: $a^{-1}\ne a$. Das Produkt der Zahlen $2\cdot 3 \cdot\ldots\cdot (p-2)$ besteht also aus zueinander inversen Paaren. @@ -467,7 +463,7 @@ Ein Körper mit Charakteristik $0$ enthält immer unendliche viele Elemente. \subsubsection{Teilbarkeit von Binomialkoeffizienten} -Als Beispiel für die Auswrikung der Charakteristik auf die Arithmetik +Als Beispiel für die Auswirkung der Charakteristik auf die Arithmetik in einem endlichen Körper betrachten wir die Teilbarkeitseigenschaften der Binomialkoeffizienten. @@ -500,9 +496,10 @@ Rest bei Teilung durch $2$ der Binomialkoeffizienten. \index{Binomialkoeffizient}% Man kann daraus ablesen, dass $\binom{n}{m}\equiv 0\mod 2$ für $n=2^k$ und $00$ und $00$ und $01$, 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. -- cgit v1.2.1