diff options
Diffstat (limited to 'buch')
| -rw-r--r-- | buch/chapters/30-endlichekoerper/euklid.tex | 193 |
1 files changed, 190 insertions, 3 deletions
diff --git a/buch/chapters/30-endlichekoerper/euklid.tex b/buch/chapters/30-endlichekoerper/euklid.tex index cb2f7ca..db326f8 100644 --- a/buch/chapters/30-endlichekoerper/euklid.tex +++ b/buch/chapters/30-endlichekoerper/euklid.tex @@ -16,6 +16,9 @@ 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. +% +% Der euklidische Algorithmus für ganze Zahlen +% \subsection{Ganze Zahlen} Gegeben sind zwei ganze Zahlen $a$ und $b$ und wir dürfen annehmen, dass $a\ge b$. @@ -59,6 +62,7 @@ Der letzte nicht verschwindende Rest $r_n$ muss daher der grösste gemeinsame Teiler sein: $g=r_n$. \begin{beispiel} +\label{buch:endlichekoerper:beispiel1} 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: @@ -116,7 +120,11 @@ die Zahlen $t=-58$ und $s=191$ sind also genau die eingangs versprochenen Faktoren. \end{beispiel} -\subsection{Matrixschreibweise} +% +% Matrixschreibeweise für den euklidischen Algorithmus +% +\subsection{Matrixschreibweise +\label{buch:endlichekoerper: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 @@ -263,8 +271,7 @@ Q \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} = @@ -315,6 +322,186 @@ berechnen. Dies ist die Art von Matrix, die wir für die Implementation der Wavelet-Transformation anstreben. +% +% Vereinfachte Durchführung des euklidischen Algorithmus +% +\subsection{Vereinfachte Durchführung +\label{buch:endlichekoerper:subsection:matrixschreibweise}} +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 +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 müssen. +Dazu beachten wir zunächst, dass die Multiplikation mit der Matrix +$Q(q_k)$ die zweite Zeile in die erste Zeile verschiebt: +\[ +Q(q_k) +\begin{pmatrix} +u&v\\ +c&d\\ +\end{pmatrix} += +\begin{pmatrix}0&1\\1&-q_k\end{pmatrix} +\begin{pmatrix} +u&v\\ +c&d +\end{pmatrix} += +\begin{pmatrix} +c&d\\ +u-q_kc&v-q_kd +\end{pmatrix}. +\] +Die Matrizen +\[ +Q_k = Q(q_k)Q(q_{k-1})\dots Q(q_0) +\] +haben daher jeweils für aufeinanderfolgende Werte vo $k$ eine Zeile +gemeinsam. +Wir bezeichnen die Einträge der ersten Zeile der Matrix $Q_k$ mit +$c_k$ und $d_k$. +Es gilt dann +\[ +Q_k += +\begin{pmatrix} +c_{k} &d_{k} \\ +c_{k+1}&d_{k+1} +\end{pmatrix} += +Q(q_k) +\begin{pmatrix} +c_{k-1}&d_{k-1}\\ +c_{k} &d_{k} +\end{pmatrix} +\] +Daraus ergeben sich die Rekursionsformeln +\begin{equation} +\begin{aligned} +c_{k+1}&=c_{k-1}-q_kc_k\\ +d_{k+1}&=d_{k-1}-q_kd_k. +\end{aligned} +\label{buch:endlichekoerper:eqn:cdrekursion} +\end{equation} +Die Auswertung des Matrizenproduktes von links nach rechts beginnt mit +der Einheitsmatrix, es ist +\[ +Q_0 += +Q(q_0) I += +\begin{pmatrix} +0&1\\ +1&-q_0 +\end{pmatrix} +\begin{pmatrix} +1&0\\0&1\end{pmatrix}, +\] +woraus man ablesen kann, dass +\begin{equation} +Q_{-1} += +\begin{pmatrix} +c_{-1}&d_{-1}\\ +c_0&d_0 +\end{pmatrix} += +\begin{pmatrix} +1&0\\ +0&1 +\end{pmatrix} +\label{buch:endlichekoerper:eqn:cdinitial} +\end{equation} +gesetzt werden muss. + +Mit diesen Notationen kann man den Algorithmus jetzt in der früher +verwendeten Tabelle durchführen, die man um die zwei +Spalten $c_k$ und $d_k$ hinzufügt und die Werte in dieser +Spalte mit Hilfe der +Rekursionsformeln~\eqref{buch:endlichekoerper:eqn:cdrekursion} +aus den initialen Werten~\eqref{buch:endlichekoerper:eqn:cdinitial} +berechnet. + +\begin{beispiel} +Wir erweitern das Beispiel von Seite~\pageref{buch:endlichekoerper:beispiel1} +zur Bestimmung des grössten gemeinsamen Teilers von $76415$ und $23205$ +zur Berechnung der Koeffizienten $c_k$ und $d_k$ +Wir schreiben die gefundenen Zahlen in eine Tabelle: +\begin{center} +\renewcommand{\arraystretch}{1.1} +\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|} +\hline +k& a_k& b_k& q_k& r_k& c_k& d_k\\ +\hline + & & & & & 1& 0\\ +0& 76415& 23205& 3& 6800& 0& 1\\ +1& 23205& 6800& 3& 2805& 1& -3\\ +2& 6800& 2805& 2& 1190& -3& 10\\ +3& 2805& 1190& 2& 425& 7& -23\\ +4& 1190& 425& 2& 340& -17& 56\\ +5& 425& 340& 1& 85& 41& -135\\ +6& 340& 85& 4& 0& -58& 191\\ +7& 85& 0& & & 273& -899\\ +\hline +\end{tabular} +\end{center} +Aus den letzten zwei Spalten der Tabelle kann man ablesen, dass +\begin{align*} +-58\cdot 76415 + 191\cdot 23205 &= 85\\ +273\cdot 76415 - 899\cdot 23205 &= 0, +\end{align*} +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 +aus den vier Elementen in den Zeilen $k$ und $k+1$ in den +Spalten $c_k$ und $d_k$. +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}$. + +Bis jetzt gingen wir immer davon aus, dass $a>b$ ist. +Dies ist jedoch nicht nötig, wie die Durchführung des Algorithmus +für das obige Beispiel mit vertauschten Werten von $a$ und $b$ zeigt. +Wir bezeichnen die Elemente zur Unterscheidung von der ursprünglichen +Durchführung mit einem Strich: +\begin{center} +\renewcommand{\arraystretch}{1.1} +\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|} +\hline +k& a_k'& b_k'& q_k'& r_k'& c_k'& d_k'\\ +\hline + & & & & & 1& 0\\ +0& 23205& 76415& 0& 23205& 0& 1\\ +1& 76415& 23205& 3& 6800& 1& 0\\ +2& 23205& 6800& 3& 2805& -3& 1\\ +3& 6800& 2805& 2& 1190& 10& -3\\ +4& 2805& 1190& 2& 425& -23& 7\\ +5& 1190& 425& 2& 340& 56& -17\\ +6& 425& 340& 1& 85& -135& 41\\ +7& 340& 85& 4& 0& 191& -58\\ +8& 85& 0& & & -899& 273\\ +\hline +\end{tabular} +\end{center} +Da für $a<b$ der erste Quotient $q_0'=0$ ist, werden die ersten neuen +Elemente $c_1'=1=d_0$ und $d_1'=0=c_0$ sein. +Die nachfolgenden Quotienten sind genau die gleichen, also $q_k = q_{k+1}'$ +und damit werden auch +\[ +c_{k}=d_{k+1}' \qquad\text{und}\qquad d_{k} = c_{k+1}' +\] +sein. +Man findet also die gleichen Einträge in einer Tabelle, die eine Zeile +mehr hat und in der die letzten zwei Spalten gegenüber der ursprünglichen +Tabelle vertauscht wurden. + +% +% Der euklidische Algorithmus für Polynome +% \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 |