diff options
Diffstat (limited to '')
| -rw-r--r-- | buch/chapters/30-endlichekoerper/Makefile.inc | 1 | ||||
| -rw-r--r-- | buch/chapters/30-endlichekoerper/chapter.tex | 6 | ||||
| -rw-r--r-- | buch/chapters/30-endlichekoerper/euklid.tex | 430 |
3 files changed, 436 insertions, 1 deletions
diff --git a/buch/chapters/30-endlichekoerper/Makefile.inc b/buch/chapters/30-endlichekoerper/Makefile.inc index 1118fb0..d1a1d76 100644 --- a/buch/chapters/30-endlichekoerper/Makefile.inc +++ b/buch/chapters/30-endlichekoerper/Makefile.inc @@ -5,6 +5,7 @@ # CHAPTERFILES = $(CHAPTERFILES) \ + chapters/30-endlichekoerper/euklid.tex \ chapters/30-endlichekoerper/galois.tex \ chapters/30-endlichekoerper/wurzeln.tex \ chapters/30-endlichekoerper/chapter.tex diff --git a/buch/chapters/30-endlichekoerper/chapter.tex b/buch/chapters/30-endlichekoerper/chapter.tex index 6dfbaef..f82532a 100644 --- a/buch/chapters/30-endlichekoerper/chapter.tex +++ b/buch/chapters/30-endlichekoerper/chapter.tex @@ -20,6 +20,10 @@ die diese Eigenschaft nicht haben. Nicht überraschend werden die ersten derartigen Körper, die wir in Abschnitt~\ref{buch:section:galoiskoerper} konstruieren werden, endlich viele Elemente haben. +Als Hilfsmittel für die Definition der Division in diesem Körper wird +als Vorbereitung in Abschnitt~\ref{buch:section:euklid} der +euklidische Algorithmus vorgestellt, wobei auch eine besonders zum +Thema dieses Buches passende Beschreibung in Matrixform angegeben wird. Zu diesen sogenannten Galois-Körpern können wir dann weitere Elemente hinzufügen, wie das in Abschnitt ~\ref{buch:section:wurzeln} gezeigt wird. @@ -27,7 +31,7 @@ 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 lösbar werden. - +\input{chapters/30-endlichekoerper/euklid.tex} \input{chapters/30-endlichekoerper/galois.tex} \input{chapters/30-endlichekoerper/wurzeln.tex} diff --git a/buch/chapters/30-endlichekoerper/euklid.tex b/buch/chapters/30-endlichekoerper/euklid.tex new file mode 100644 index 0000000..cb2f7ca --- /dev/null +++ b/buch/chapters/30-endlichekoerper/euklid.tex @@ -0,0 +1,430 @@ +% +% euklid.tex +% +% (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\section{Der euklidische Algorithmus +\label{buch:section:euklid}} +\rhead{Der euklidische Algorithmus} +Der euklidische Algorithmus bestimmt zu zwei gegebenen ganzen +Zahlen $a$ und $b$ den grössten gemeinsamen Teiler $g$. +Zusätzlich findet er ganze Zahlen $s$ und $t$ derart, dass +\[ +sa + tb = g. +\] +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. + +\subsection{Ganze Zahlen} +Gegeben sind zwei ganze Zahlen $a$ und $b$ und 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$. +Im Allgemeinen wird der grösste gemeinsame Teiler aber kleiner sein. +Wir teilen daher $a$ durch $b$, was nur mit Rest möglich ist. +Es gibt ganze Zahlen $q$, der Quotient, und $r$, der Rest, derart, dass +\begin{equation} +a = qb+ r +\qquad \Rightarrow \qquad +r = a - qb. +\label{lifting:euklid:raqb} +\end{equation} +Nach Definition des Restes ist $r < b$. +Da der grösste gemeinsame Teiler sowohl $a$ als auch $b$ teilt, muss er +wegen~\eqref{lifting:euklid:raqb} auch $r$ teilen. +Somit haben wir das Problem, den grössten gemeinsamen Teiler von $a$ und +$b$ zu finden, auf das ``kleinere'' Problem zurückgeführt, den grössten +gemeinsamen Teiler von $b$ und $r$ zu finden. + +Um den eben beschriebenen Schritt zu wiederholen, wählen wir die folgende +Notation. +Wir schreiben $a_0=a$ und $b_0=b$. +Im ersten Schritt finden wird $q_0$ und $r_0$ derart, +dass $a_0-q_0b_0 = r_0$. +Dann setzen wir $a_1=b_0$ und $b_1=r_0$. +Mit $a_1$ und $b_1$ wiederholen wir den Divisionsschritt, der einen +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} +\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 +Teiler sein: $g=r_n$. + +\begin{beispiel} +Wir bestimmen den grössten gemeinsamen Teiler von $76415$ und $23205$ +mit Hilfe des eben beschriebenen Algorithmus. +Wir schreiben die gefundenen Zahlen in eine Tabelle: +\begin{center} +\renewcommand{\arraystretch}{1.1} +\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|} +\hline +k& a_k& b_k& q_k& r_k\\ +\hline +0&76415&23205& 3&6800\\ +1&23205& 6800& 3&2805\\ +2& 6800& 2805& 2&1190\\ +3& 2805& 1190& 2& 425\\ +4& 1190& 425& 2& 340\\ +5& 425& 340& 1& 85\\ +6& 340& 85& 4& 0\\ +\hline +\end{tabular} +\end{center} +Der Algorithmus bricht also mit dem letzten Rest $r_n=85$ ab, dies +ist der grösste gemeinsame Teiler. +\end{beispiel} + +Die oben protokollierten Werte von $q_k$ werden für die Bestimmung +des grössten gemeinsamen Teilers nicht benötigt. +Wir können sie aber verwenden, um die Zahlen $s$ und $t$ zu bestimmen. + +\begin{beispiel} +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*} +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) + = -a_4 +3b_4 = -b_3 + 3r_3 +\\ +r_3&=a_3-q_3 b_3=a_3-2\cdot b_3& &= -b_3 + 3(a_3-2b_3) + = 3a_3 - 7b_3 = 3b_2 -7r_2 +\\ +r_2&=a_2-q_2 b_2=a_2-2\cdot b_2& &= 3b_2 -7(a_2-2b_2) + = -7a_2 + 17b_2 = -7b_1 + 17r_1 +\\ +r_1&=a_1-q_1 b_1=a_1-3\cdot b_1& &= -7b_1 + 17(a_1-3b_1) + = 17a_1 - 58b_1 = 17 b_0 - 58 r_0 +\\ +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*} +Tatsächlich gilt +\[ +-58\cdot 76415 + 191 \cdot 23205 = 85, +\] +die Zahlen $t=-58$ und $s=191$ sind also genau die eingangs versprochenen +Faktoren. +\end{beispiel} + +\subsection{Matrixschreibweise} +Die Durchführung des euklidischen Algorithmus lässt sich besonders elegant +in Matrixschreibweise dokumentieren. +In jedem Schritt arbeitet man mit zwei ganzen Zahlen $a_k$ und $b_k$, die wir +als zweidimensionalen Spaltenvektor betrachten können. +Der Algorithmus macht aus $a_k$ und $b_k$ die neuen Zahlen +$a_{k+1} = b_k$ und $b_{k+1} = r_k = a_k - q_kb_k$, dies +kann man als +\[ +\begin{pmatrix} a_{k+1} \\ b_{k+1} \end{pmatrix} += +\begin{pmatrix} b_k \\ r_k \end{pmatrix} += +\begin{pmatrix} 0 & 1 \\ 1 & -q_k \end{pmatrix} +\begin{pmatrix} a_{k} \\ b_{k} \end{pmatrix} +\] +schreiben. +Der Algorithmus bricht ab, wenn die zweite Komponente des Vektors $=0$ ist, +in der ersten steht dann der grösste gemeinsame Teiler. +Hier ist die Durchführung des Algorithmus in Matrix-Schreibweise: +\begin{align*} +\begin{pmatrix} 23205 \\ 6800 \end{pmatrix} +&= +\begin{pmatrix} 0&1\\1&-3 \end{pmatrix} +\begin{pmatrix} 76415 \\ 23205 \end{pmatrix} +\\ +\begin{pmatrix} 6800 \\ 2805 \end{pmatrix} +&= +\begin{pmatrix} 0&1\\1&-3 \end{pmatrix} +\begin{pmatrix} 23205 \\ 6800 \end{pmatrix} +\\ +\begin{pmatrix} 2805 \\ 1190 \end{pmatrix} +&= +\begin{pmatrix} 0&1\\1&-2 \end{pmatrix} +\begin{pmatrix} 6800 \\ 2805 \end{pmatrix} +\\ +\begin{pmatrix} 1190 \\ 425 \end{pmatrix} +&= +\begin{pmatrix} 0&1\\1&-2 \end{pmatrix} +\begin{pmatrix} 2805 \\ 1190 \end{pmatrix} +\\ +\begin{pmatrix} 425 \\ 340 \end{pmatrix} +&= +\begin{pmatrix} 0&1\\1&-2 \end{pmatrix} +\begin{pmatrix} 1190 \\ 425 \end{pmatrix} +\\ +\begin{pmatrix} 340 \\ 85 \end{pmatrix} +&= +\begin{pmatrix} 0&1\\1&-1 \end{pmatrix} +\begin{pmatrix} 425 \\ 340 \end{pmatrix} +\\ +\begin{pmatrix} 85 \\ 0 \end{pmatrix} +&= +\begin{pmatrix} 0&1\\1&-4 \end{pmatrix} +\begin{pmatrix} 340 \\ 85 \end{pmatrix} += +\begin{pmatrix}g\\0\end{pmatrix}. +\end{align*} + +\begin{definition} +Wir kürzen +\[ +Q(q_k) = \begin{pmatrix} 0 & 1 \\ 1 & -q_k \end{pmatrix} +\] +ab. +\end{definition} + +Mit dieser Definition lässt sich der euklidische Algorithmus wie folgt +beschreiben. + +\begin{algorithmus}[Euklid] +\label{lifting:euklid} +Der Algorithmus operiert auf zweidimensionalen Zustandsvektoren +$x\in\mathbb Z^2$ +wie folgt: +\begin{enumerate} +\item Initialisiere den Zustandsvektor mit den ganzen Zahlen $a$ und $b$: +$\displaystyle x = \begin{pmatrix}a\\b\end{pmatrix}$ +\item Bestimme den Quotienten $q$ als die grösste ganze Zahl, +für die $qx_2\le x_1$ gilt. +\item Berechne den neuen Zustandsvektor als $Q(q)x$. +\item Wiederhole Schritte 2 und 3 bis die zweite Komponente des Zustandsvektors +verschwindet. +Die erste Komponente ist dann der gesuchte grösste gemeinsame Teiler. +\end{enumerate} +\end{algorithmus} + +Auch die Berechnung der Zahlen $s$ und $t$ lässt sich jetzt leichter verstehen. +Nach Algorithmus~\ref{lifting:euklid} ist +\[ +\begin{pmatrix} g \\ 0 \end{pmatrix} += +Q(q_n)Q(q_{n-1})\cdots Q(q_0) +\begin{pmatrix} a \\ b \end{pmatrix}. +\] +Schreiben wir $Q=Q(q_n)Q(q_{n-1})\cdots Q(q_0)$, dann enthält die Matrix +$Q$ in der erste Zeile die ganzen Zahlen $s$ und $t$, mit denen sich der +grösste gemeinsame Teiler aus $a$ und $b$ darstellen lässt: +\[ +Q = +\begin{pmatrix} +s&t\\ +q_{21}&q_{22} +\end{pmatrix} +\qquad\Rightarrow\qquad +\bigg\{ +\quad +\begin{aligned} +g&=sa+tb\\ +0&=q_{21}a+q_{22}b. +\end{aligned} +\] + +\begin{beispiel} +Wir verifizieren die Behauptung durch Nachrechnen: +\begin{align*} +Q +&= +\begin{pmatrix} 0&1 \\ 1&-q_n\end{pmatrix} +\begin{pmatrix} 0&1 \\ 1&-q_{n-1}\end{pmatrix} +\cdots +\begin{pmatrix} 0&1 \\ 1&-q_{0}\end{pmatrix} +\\ +&= +\underbrace{ +\begin{pmatrix} 0&1 \\ 1& -4 \end{pmatrix} +\begin{pmatrix} 0&1 \\ 1& -1 \end{pmatrix} +}_{} +\underbrace{ +\begin{pmatrix} 0&1 \\ 1& -2 \end{pmatrix} +\begin{pmatrix} 0&1 \\ 1& -2 \end{pmatrix} +}_{} +\underbrace{ +\begin{pmatrix} 0&1 \\ 1& -2 \end{pmatrix} +\begin{pmatrix} 0&1 \\ 1& -3 \end{pmatrix} +}_{} +\begin{pmatrix} 0&1 \\ 1& -3 \end{pmatrix} +\\ +&= +\underbrace{ +\begin{pmatrix} 1 & -1 \\ -4 & 5 \end{pmatrix} +\begin{pmatrix} 1 & -2 \\ -2 & 5 \end{pmatrix} +}_{} +\underbrace{ +\begin{pmatrix} 1 & -2 \\ -3 & 7 \end{pmatrix} +\begin{pmatrix} 0 & 1 \\ 1 & -3 \end{pmatrix} +}_{} +\\ +&= +\begin{pmatrix} 3 & -7 \\ -14 & 33 \end{pmatrix} +\begin{pmatrix} -3 & 10 \\ 7 & -23 \end{pmatrix} += +\begin{pmatrix} -58 & 191 \\ 273 & -899 \end{pmatrix}. +%(%i9) Q6 . Q5 +% [ 1 - 1 ] +%(%o9) [ ] +% [ - 4 5 ] +%(%i10) Q4 . Q3 +% [ 1 - 2 ] +%(%o10) [ ] +% [ - 2 5 ] +%(%i11) Q2 . Q1 +% [ 1 - 3 ] +%(%o11) [ ] +% [ - 2 7 ] +%(%i12) Q6 . Q5 . Q4 . Q3 +% [ 3 - 7 ] +%(%o12) [ ] +% [ - 14 33 ] +%(%i13) Q2 . Q1 . Q0 +% [ - 3 10 ] +%(%o13) [ ] +% [ 7 - 23 ] +%(%i14) Q6 . Q5 . Q4 . Q3 . Q2 . Q1 . Q0 +% [ - 58 191 ] +%(%o14) [ ] +% [ 273 - 899 ] +\end{align*} +In der zweiten Zeile findet man Zahlen, die $a$ und $b$ zu 0 kombinieren: +\[ +273 \cdot 76415 - 899 \cdot 23205 = 0, +\] +in der ersten stehen die Zahlen $s=-58$ und $t=191$ und tatsächlich +ergibt +\[ +ta+sb = -58\cdot 76415 + 191\cdot 23205 = 85 = g +\] +den grössten gemeinsamen Teiler von 76415 und 23205. +\end{beispiel} + +Die Wirkung der Matrix +\[ +Q(q) = \begin{pmatrix} 0 & 1 \\ 1 & -q \end{pmatrix} +\] +lässt sich mit genau einer Multiplikation und einer Addition +berechnen. +Dies ist die Art von Matrix, die wir für die Implementation der +Wavelet-Transformation anstreben. + +\subsection{Polynome} +Der Ring $\mathbb{Q}[X]$ der Polynome in der Variablen $X$ mit rationalen +Koeffizienten\footnote{Es kann auch ein beliebiger anderer Körper für +die Koeffizienten verwendet werden. +Es gelten sogar ähnlich interessante Gesetzmässigkeiten, wenn man für +die Koeffizienten ganze Zahlen zulässt. +Dann wird das Problem der Faktorisierung allerdings verkompliziert +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. +Insbesondere ist der euklidische Algorithmus genauso wie die +Matrixschreibweise auch für Polynome durchführbar. + +\begin{beispiel} +Wir berechnen als Beispiel den grössten gemeinsamen Teiler +der Polynome +\[ +a = X^4 - 2X^3 -7 X^2 + 8X + 12, +\qquad +b = X^4 + X^3 -7X^2 -X + 6. +\] +Wir erstellen wieder die Tabelle der Reste +\begin{center} +\renewcommand{\arraystretch}{1.4} +\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|} +\hline +k& a_k& b_k& q_k& r_k\\ +\hline +0& X^4 - 2X^3 -7 X^2 + 8X + 12& X^4 + X^3 -7X^2 -X + 6& 1&-3X^3+9X+6\\ +1&X^4+X^3-7X^2-X+6 &-3X^3+9X+6 &-\frac13X-\frac13&-4X^2+4X+8\\ +2&-3X^3+9X+6 &-4X^2+4X+8& \frac34 X + \frac34& 0\\ +\hline +\end{tabular} +\end{center} +Daraus kann man ablesen, dass $-4x^2+4x+8$ grösster gemeinsamer Teiler ist. +Normiert auf einen führenden Koeffizienten $1$ ist dies das Polynom +$x^2-x+2=(x+2)(x-1)$. + +Wir berechnen auch noch die Polynome $s$ und $t$. +Dazu müssen wir die Matrizen $Q(q_k)$ miteinander multiplizieren: +\begin{align*} +Q +&=Q(q_2) Q(q_1) Q(q_0) +\\ +&= +\begin{pmatrix} 0 & 1 \\ 1 & -\frac34(X+1) \end{pmatrix} +\begin{pmatrix} 0 & 1 \\ 1 & \frac13(X+1) \end{pmatrix} +\begin{pmatrix} 0 & 1 \\ 1 & -1 \end{pmatrix} +\\ +&= +% [ x 1 2 x ] +% [ - + - - - - ] +% [ 3 3 3 3 ] +%(%o22) [ ] +% [ 2 2 ] +% [ x x 3 x x 3 ] +% [ (- --) - - + - -- - - - - ] +% [ 4 2 4 4 4 2 ] +\begin{pmatrix} +\frac13(X+1)&-\frac13(X-2)\\ +-\frac14(X^2+2X-3)&\frac14(X^2-X-6) +\end{pmatrix}. +\end{align*} +In der ersten Zeile finden wir die Polynome $t(X)$ und $s(X)$, mit denen +\begin{align*} +ta+sb +&= +\frac13(X+1) +(X^4-2X^3-7X^2+8X+12) +-\frac13(X-2) +(X^4+X^3-7X^2-X+6) +\\ +&= +-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 +$a$ und $b$ gleich werden: +\begin{align*} +q_{21}a+q_{22}b +&= +-\frac14(X^2+2X-3) +(X^4-2X^3-7X^2+8X+12) ++\frac14(X^2-X-6) +(X^4+X^3-7X^2-X+6) +\\ +&=0. +\qedhere +\end{align*} +Man kann natürlich den grössten gemeinsamen Teiler auch mit Hilfe einer +Faktorisierung der Polynome $a$ und $b$ finden: +\begin{align*} +&\text{Faktorisierung von $a$:}& +a &= (X-3) (X-2)\phantom{(X-1)}(X+1) (X+2) \phantom{(X+3)}\\ +&\text{Faktorisierung von $b$:}& +b &=\phantom{(X-3)}(X-2) (X-1) (X+1)\phantom{(X+2)} (X+3) \\ +&\text{gemeinsame Faktoren:}& +g &=\phantom{(X-3)}(X-2)\phantom{(X-1)}(X+1)\phantom{(X+2)}\phantom{(X+3)} + = X^2 -X + 2\\ +&& +v=a/g&= (X-3)\phantom{(X-2)(X-1)(X+1)} (X+2) \phantom{(X+3)} + = X^2-X-6 \\ +&& +u=b/g&=\phantom{(X-3)(X-2)} (X-1)\phantom{(X+1)(X+2)}(X+3) + = X^2+2X-3 +\end{align*} +Aus den letzten zwei Zeilen folgt +$ua-vb = ab/g - ab/g = 0$, wie erwartet. +\end{beispiel} + + |