From 036e7aae98bcf2cb7d63546e153c25649baa93d1 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Tue, 31 Aug 2021 20:58:56 +0200 Subject: Kapitel 3 --- buch/chapters/30-endlichekoerper/euklid.tex | 80 ++++++++++++++++++----------- 1 file changed, 49 insertions(+), 31 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 0bf3016..a75046f 100644 --- a/buch/chapters/30-endlichekoerper/euklid.tex +++ b/buch/chapters/30-endlichekoerper/euklid.tex @@ -8,18 +8,33 @@ \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 + +\begin{definition} +\label{buch:endliche-koerper:def:ggt} +Der grösste gemeinsame Teiler von $a$ und $b$ ist die grösste +ganze Zahl $g$, die sowohl $a$ als auch $b$ teilt: $g|a$ und +$g|b$. +\index{grösster gemeinsamer Teiler}% +\index{ggT}% +\end{definition} + +Zusätzlich findet der euklidische Algorithmus ganze Zahlen $s$ +\index{euklidischer Algorithmus}% +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. +Die Matrixform ermöglicht, einfach zu implementierende iterative +Algorithmen für die Zahlen $s$ und $t$ un später auch für die +Berechnung des kleinsten gemeinsamen Vielfachen zu finden. % % Der euklidische Algorithmus für ganze Zahlen % -\subsection{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$. Gesucht ist der grösste gemeinsame Teiler $g$ von $a$ und $b$. @@ -55,11 +70,11 @@ 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 & 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$. +Teiler $g$ von $a$ und $b$ sein: $g=r_n$. \begin{beispiel} \label{buch:endlichekoerper:beispiel1} @@ -131,7 +146,7 @@ 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 +kann man als die Matrixoperation \[ \begin{pmatrix} a_{k+1} \\ b_{k+1} \end{pmatrix} = @@ -143,7 +158,7 @@ kann man als 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: +Hier die Durchführung des Algorithmus in Matrix-Schreibweise: \begin{align*} \begin{pmatrix} 23205 \\ 6800 \end{pmatrix} &= @@ -196,16 +211,16 @@ beschreiben. \begin{algorithmus}[Euklid] \label{lifting:euklid} -Der Algorithmus operiert auf zweidimensionalen Zustandsvektoren +Der Algorithmus operiert auf zweidimensionalen Vektoren $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 Initialisiere den Vektor mit den ganzen Zahlen $a$ und $b$: +$\displaystyle x = \begin{pmatrix}x_1\\x_2\end{pmatrix}=\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 +\item Berechne den neuen Vektor als $Q(q)x$. +\item Wiederhole Schritte 2 und 3 bis die zweite Komponente des Vektors verschwindet. Die erste Komponente ist dann der gesuchte grösste gemeinsame Teiler. \end{enumerate} @@ -319,13 +334,11 @@ 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. % % Vereinfachte Durchführung des euklidischen Algorithmus % -\subsection{Vereinfachte Durchführung +\subsection{Iterative Durchführung des erweiterten euklidischen Algorithmus \label{buch:endlichekoerper:subsection:matrixschreibweise}} Die Durchführung des euklidischen Algorithmus mit Hilfe der Matrizen $Q(q_k)$ ist etwas unhandlich. @@ -334,7 +347,7 @@ 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. +Matrizen $Q(q_k)$ berechnet werden muss. Dazu beachten wir zunächst, dass die Multiplikation mit der Matrix $Q(q_k)$ die zweite Zeile in die erste Zeile verschiebt: \[ @@ -357,7 +370,7 @@ u-q_kc&v-q_kd \] Die Matrizen \[ -Q_k = Q(q_k)Q(q_{k-1})\dots Q(q_0) +Q_k = Q(q_k)Q(q_{k-1})\cdots Q(q_0) \] haben daher jeweils für aufeinanderfolgende Werte vo $k$ eine Zeile gemeinsam. @@ -419,7 +432,7 @@ 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 +Spalten $c_k$ und $d_k$ erweitert und die Werte in dieser Spalte mit Hilfe der Rekursionsformeln~\eqref{buch:endlichekoerper:eqn:cdrekursion} aus den initialen Werten~\eqref{buch:endlichekoerper:eqn:cdinitial} @@ -428,7 +441,7 @@ 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$ +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} @@ -503,7 +516,7 @@ Tabelle vertauscht wurden. % % Der euklidische Algorithmus für Polynome % -\subsection{Polynome} +\subsection{Grösster gemeinsare Teiler von Polynomen} 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. @@ -579,7 +592,7 @@ ta+sb (X^4+X^3-7X^2-X+6) \\ &= --4X^2+4X+8 +-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 @@ -621,6 +634,8 @@ $ua-vb = ab/g - ab/g = 0$, wie erwartet. % \subsection{Das kleinste gemeinsame Vielfache \label{buch:subsection:daskgv}} +\index{kleinstes gemeinsames Vielfaches}% +\index{kgV}% Das kleinste gemeinsame Vielfache zweier Zahlen $a$ und $b$ ist \[ \operatorname{kgV}(a,b) @@ -631,8 +646,8 @@ Wir suchen nach einen Algorithmus, mit dem man das kleinste gemeinsame Vielfache effizient berechnen kann. Die Zahlen $a$ und $b$ sind beide Vielfache des grössten gemeinsamen -Teilers $g=\operatorname{ggT}(a,b)$, es gibt also Zahlen $u$ und $v$ derart, -dass $a=ug$ und $b=vg$. +Teilers $g=\operatorname{ggT}(a,b)$. +Es gibt daher Zahlen $u$ und $v$ derart, dass $a=ug$ und $b=vg$. Wenn $t$ ein gemeinsamer Teiler von $u$ und $v$ ist, dann ist $tg$ ein grösserer gemeinsamer Teiler von $a$ und $b$. Dies kann nicht sein, also müssen $u$ und $v$ teilerfremd sein. @@ -641,6 +656,7 @@ Die Bestimmung des kleinsten gemeinsamen Vielfachen ist also gleichbedeutend mit der Bestimmung der Zahlen $u$ und $v$. Die definierende Eigenschaften von $u$ und $v$ kann man in Matrixform als +\index{Matrixform des kgV-Algorithmus}% \begin{equation} \begin{pmatrix} a\\b @@ -669,7 +685,7 @@ Algorithmus beschreiben, ergeben ihn als \operatorname{ggT}(a,b)\\0 \end{pmatrix} = -Q(q_n)Q(q_{n-1}) \dots Q(q_1)Q(q_0) +Q(q_n)Q(q_{n-1}) \cdots Q(q_1)Q(q_0) \begin{pmatrix}a\\b\end{pmatrix}. \] Indem wir die Matrizen $Q(q_n)$ bis $Q(q_0)$ auf die linke Seite der @@ -679,7 +695,7 @@ Gleichung schaffen, erhalten wir = Q(q_0)^{-1} Q(q_1)^{-1} -\dots +\cdots Q(q_{n-1})^{-1} Q(q_n)^{-1} \begin{pmatrix}\operatorname{ggT}(a,b)\\0\end{pmatrix}. @@ -692,15 +708,14 @@ K = Q(q_0)^{-1} Q(q_1)^{-1} -\dots +\cdots Q(q_{n-1})^{-1} 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 sehr -effizient. +Die Berechnung der Matrix $K$ als Inverse von $Q$ ist nicht schwierig. 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. @@ -709,7 +724,7 @@ Schreiben wir die gesuchte Matrix \[ K_k = -Q(q_0)^{-1}\dots Q(q_{k-1})^{-1} +Q(q_0)^{-1}\cdots Q(q_{k-1})^{-1} = \begin{pmatrix} e_k & e_{k-1}\\ @@ -825,13 +840,12 @@ va \] \end{beispiel} +\subsection{Kleinstes gemeinsames Vielfaches von Polynomen} Der erweiterte Algorithmus kann auch dazu verwendet werden, das kleinste gemeinsame Vielfache zweier Polynome zu berechnen. Dies wird zum Beispiel bei der Decodierung des Reed-Solomon-Codes in Kapitel~\ref{chapter:reedsolomon} verwendet. -\subsubsection{Polynome -\label{buch:endlichekoerper:eqn:polynomkgv}} Im Beispiel auf Seite~\pageref{buch:endlichekoerper:eqn:polynomggt} wird der grösste gemeinsame Teiler der Polynome \[ @@ -844,6 +858,8 @@ b = X^4 + X^3 -7X^2 -X + 6 berechnet. Dies kann jetzt erweitert werden für die Berechnung des kleinsten gemeinsamen Vielfachen. +\index{kleinstes gemeinsames Vielfaches von Polynomen}% +\index{kgV von Polynomen}% \begin{beispiel} Die Berechnungstabelle nur für die Spalten $e_k$ und $f_k$ ergibt @@ -890,8 +906,9 @@ Daraus ergibt sich das kleinste gemeinsame Vielfache auf zwei verschiedene Weise Die beiden Berechnungsmöglichkeiten stimmen wie erwartet überein. \end{beispiel} -\subsubsection{Anwendung: Decodierung des Reed-Solomon-Codes} +\subsection{Anwendung: Decodierung des Reed-Solomon-Codes} Der Reed-Solomon-Code verwendet Polynome zur Codierung der Daten, +\index{Reed-Solomon-Code}% dies wird in Kapitel~\ref{chapter:reedsolomon} im Detail beschrieben. Bei der Decodierung muss der Faktor $u$ für zwei gegebene Polynome $n(X)$ und $r(X)$ bestimmt werden. @@ -902,6 +919,7 @@ Algorithmus braucht. Daraus lässt sich genügend Information gewinnen, um die Faktoren $u$ und $v$ zu bestimmen. Das Video \url{https://youtu.be/uOLW43OIZJ0} von Edmund Weitz +\index{Weitz, Edmund} erklärt die Theorie hinter dieser Teilaufgabe anhand von Beispielen. \begin{beispiel} -- cgit v1.2.1