From 24179efc3fcb681a65fe7609419b9db7e5903d59 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Thu, 7 Jan 2021 20:26:23 +0100 Subject: =?UTF-8?q?Abschnitt=20=C3=BCber=20den=20euklidischen=20Algorithmu?= =?UTF-8?q?s=20hinzugef=C3=BCgt?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/chapters/30-endlichekoerper/euklid.tex | 430 ++++++++++++++++++++++++++++ 1 file changed, 430 insertions(+) create mode 100644 buch/chapters/30-endlichekoerper/euklid.tex (limited to 'buch/chapters/30-endlichekoerper/euklid.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} + + -- cgit v1.2.1 From e65f01b8c2a8c70662c7fd712d0678ded1be0540 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Tue, 2 Mar 2021 11:30:24 +0100 Subject: =?UTF-8?q?vereinfachte=20Durchf=C3=BChrung?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/chapters/30-endlichekoerper/euklid.tex | 193 +++++++++++++++++++++++++++- 1 file changed, 190 insertions(+), 3 deletions(-) (limited to 'buch/chapters/30-endlichekoerper/euklid.tex') 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