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/chapter.tex | 3 +- buch/chapters/30-endlichekoerper/euklid.tex | 80 ++++++----- buch/chapters/30-endlichekoerper/galois.tex | 146 +++++++++++++++++---- buch/chapters/30-endlichekoerper/images/Makefile | 6 +- buch/chapters/30-endlichekoerper/images/fermat.pdf | Bin 0 -> 24470 bytes buch/chapters/30-endlichekoerper/images/fermat.tex | 138 +++++++++++++++++++ buch/chapters/30-endlichekoerper/wurzeln.tex | 44 +++++-- 7 files changed, 345 insertions(+), 72 deletions(-) create mode 100644 buch/chapters/30-endlichekoerper/images/fermat.pdf create mode 100644 buch/chapters/30-endlichekoerper/images/fermat.tex (limited to 'buch/chapters') diff --git a/buch/chapters/30-endlichekoerper/chapter.tex b/buch/chapters/30-endlichekoerper/chapter.tex index 1a0a323..b4c602e 100644 --- a/buch/chapters/30-endlichekoerper/chapter.tex +++ b/buch/chapters/30-endlichekoerper/chapter.tex @@ -8,13 +8,14 @@ \lhead{Endliche Körper} \rhead{} Aus den ganzen Zahlen $\mathbb{Z}$ entsteht ein Körper, indem wir Brüche -bilden alle von $0$ verschiedenen Nenner zulassen. +bilden und dabei alle von $0$ verschiedenen Nenner zulassen. Der Körper der rationalen Zahlen $\mathbb{Q}$ enthält unendliche viele Zahlen und hat zusätzlich die sogenannte archimedische Eigenschaft, nämliche dass es zu zwei positiven rationalen Zahlen $a$ und $b$ immer eine ganze Zahl $n$ gibt derart, dass $na>b$. Dies bedeutet auch, dass es in den rationalen Zahlen beliebig grosse Zahlen gibt. + Man kann aus den ganzen Zahlen aber auch eine Reihe von Körpern ableiten, die diese Eigenschaft nicht haben. Nicht überraschend werden die ersten derartigen Körper, die wir 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} diff --git a/buch/chapters/30-endlichekoerper/galois.tex b/buch/chapters/30-endlichekoerper/galois.tex index c7147bf..5189dec 100644 --- a/buch/chapters/30-endlichekoerper/galois.tex +++ b/buch/chapters/30-endlichekoerper/galois.tex @@ -9,11 +9,11 @@ \rhead{Galois-Körper} Ein Körper $\Bbbk$ enthält mindestens die Zahlen $0$ und $1$. Die Null ist nötig, damit $\Bbbk$ eine Gruppe bezüglich der -Addition ist, die immer ein neutrales Element, geschrieben $0$ +Addition ist, die immer ein neutrales Element, geschrieben $0$, enthält. Die Eins ist nötig, damit $\Bbbk^*=\Bbbk\setminus\{0\}$ eine Gruppe bezüglich der Multiplikation ist, die immer eine neutrales -Element, geschrieben $1$ enthält. +Element, geschrieben $1$, enthält. Durch wiederholte Addition entstehen auch die Zahlen $2=1+1$, $3=2+1$ und so weiter. Es sieht also so aus, als ob ein Körper immer unendliche viele @@ -21,6 +21,8 @@ Elemente enthalten müsste. Wie können also endliche Körper entstehen? In diesem Abschnitt sollen die sogenannten Galois-Körper $\mathbb{F}_p$ +\index{Galois-Körper}% +\index{Fp@$\mathbb{F}_p$}% mit genau $p$ Elementen konstruiert werden, die es für jede Primzahl $p$ gibt. Sie sind die Basis für weitere endliche Körper, die eine beliebige Primzahlpotenz $p^n$ von Elementen haben und die die Basis wichtiger @@ -51,6 +53,7 @@ Zahlen $\{0,1,2,\dots,n-1\}$ identifiziert werden kann. \begin{definition} Die Zahlen $a,b\in\mathbb{Z}$ heissen {\em kongruent modulo $n$}, +\index{kongruent modulo $n$}% geschrieben \[ a\equiv b\mod n, @@ -60,6 +63,7 @@ wenn $a-b$ durch $n$ teilbar ist, also $n|(a-b)$. Die Zahlen mit gleichem Rest sind Äquivalenzklassen der Kongruenz modulo $n$. Die Zahlen mit Rest $k$ modulo $n$ bilden die {\em Restklasse} +\index{Restklasse}% \[ \llbracket k\rrbracket=\{\dots,k-2n,k-n,k,k+n,k+2n,\dots\} \subset\mathbb{Z}. \] @@ -90,7 +94,7 @@ Tatsächlich kann man auf den Restklassen eine Ringstruktur definieren. Dazu muss man sicherstellen, dass die Auswahl eines Repräsentanten keinen Einfluss auf den Rest hat. Der Rest $a$ kann jede Zahl der Form $a+kn$ darstellen. -Ebenso kann der Rest $b$ jede zahl der Form $b+ln$ 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. @@ -121,8 +125,9 @@ Insbesondere darf kein Produkt $a\cdot b$ mit Faktoren in $\mathbb{Z}/n\mathbb{Z} \setminus \{\llbracket0\rrbracket\}$ zu Null werden. Für $n=15$ funktioniert dies nicht, das Produkt $3\cdot 5\equiv 0\mod 15$. -Man nennt von Null verschiedene Faktoren, deren Produkt Null ist, einen -{\em Nullteiler}. +Wir kommen daher zu der Forderung, dass der Ring $\mathbb{Z}/n\mathbb{Z}$ +nur dann ein Körper sein kann, wenn er nullteilerfrei ist. + Falls sich $n=p_1\cdot p_2$ in zwei Faktoren zerlegen lässt, dann sind $p_1$ und $p_2$ Nullteiler in $\mathbb{Z}/n\mathbb{Z}$. Ein Körper kann also nur entstehen, wenn $n$ eine Primzahl ist. @@ -130,7 +135,9 @@ Ein Körper kann also nur entstehen, wenn $n$ eine Primzahl ist. \begin{definition} \label{buch:endlichekoerper:def:galois-koerper} Ist $p$ eine Primzahl, dann heisst $\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$ +\index{Primzahl}% der Galois-Körper der Ordnung $p$. +\index{Galois-Körper}% \end{definition} Diese Definition ist nur gerechtfertigt, wenn $\mathbb{F}_p^*$ tatsächlich @@ -152,6 +159,7 @@ lösen kann, wenn die beiden gegebenen Zahlen $a$ und $p$ teilerfremd sind. Dies ist aber dadurch garantiert, dass $p$ eine Primzahl ist und $1\le a =latex,thick,scale=\skala] + +\def\s{34} + +\definecolor{farbe1}{rgb}{0.0,0.4,0.0} +\definecolor{farbe2}{rgb}{0.0,1.0,1.0} +\definecolor{farbe3}{rgb}{0.0,0.4,0.6} +\definecolor{farbe4}{rgb}{0.0,0.0,0.8} +\definecolor{farbe5}{rgb}{0.4,0.0,1.0} +\definecolor{farbe6}{rgb}{0.8,0.0,0.0} +\definecolor{farbe7}{rgb}{0.8,0.4,0.4} +\definecolor{farbe8}{rgb}{1.0,0.8,0.0} + +\def\perle#1#2#3{ + \fill[color=#3] ($#1+({#2*0.15},0)$) circle[radius=0.075]; +} + +\def\perlena#1#2#3#4#5#6{ + \draw #1 -- ($#1+({0.15*9},0)$); + \perle{#1}{0}{#2} + \perle{#1}{1}{#3} + \perle{#1}{2}{#4} + \perle{#1}{3}{#5} + \perle{#1}{4}{#6} +} +\def\perlenb#1#2#3#4#5#6{ + \perle{#1}{5}{#2} + \perle{#1}{6}{#3} + \perle{#1}{7}{#4} + \perle{#1}{8}{#5} + \perle{#1}{9}{#6} +} + +\begin{scope}[xshift=3cm] +\draw (0,0) circle[radius=4]; +\foreach \k in {-1,...,8}{ + \draw (0,0) -- ({90+\k*\s}:4); +} +\foreach \k in {1,...,8}{ + \node at ({90+\s*(\k-0.5)}:3.7) {$A_{\k\mathstrut}$}; +} + +\pgfmathparse{90-(360-9*\s)/2-\s} +\xdef\b{\pgfmathresult} +\foreach \d in {-10,-5,...,10}{ + \fill ({\b+\d}:2.8) circle[radius=0.04]; +} +\node at ({90-(\s/2)}:3.7) {$A_{p\mathstrut}$}; + +\node at (-4,4) {$s_1$}; +\node at (-3.8,2.6) {$s_2$}; +\node at (-4.8,0.6) {$s_3$}; +\node at (-4.2,-2) {$s_4$}; +\node at (-4,-4) {$s_5$}; + +\perlena{({-3*sin(-0.5*\s)-0.54},{3*cos(-0.5*\s)})}{farbe8}{farbe1}{farbe2}{farbe3}{farbe4} +\perlenb{({-3*sin(-0.5*\s)-0.54},{3*cos(-0.5*\s)})}{farbe5}{farbe6}{farbe7}{black,opacity=0}{black,opacity=0} + +\perlena{({-3*sin(0.5*\s)-0.74},{3*cos(0.5*\s)})}{farbe1}{farbe2}{farbe3}{farbe4}{farbe5} +\perlenb{({-3*sin(0.5*\s)-0.74},{3*cos(0.5*\s)})}{farbe6}{farbe7}{black,opacity=0}{black,opacity=0}{farbe8} + +\perlena{({-3*sin(1.5*\s)-0.74},{3*cos(1.5*\s)-0.2})}{farbe2}{farbe3}{farbe4}{farbe5}{farbe6} +\perlenb{({-3*sin(1.5*\s)-0.74},{3*cos(1.5*\s)-0.2})}{farbe7}{black,opacity=0}{black,opacity=0}{farbe8}{farbe1} + +\perlena{({-3*sin(2.5*\s)-0.0},{3*cos(2.5*\s)-0.0})}{farbe3}{farbe4}{farbe5}{farbe6}{farbe7} +\perlenb{({-3*sin(2.5*\s)-0.0},{3*cos(2.5*\s)-0.0})}{black,opacity=0}{black,opacity=0}{farbe8}{farbe1}{farbe2} + +\perlena{({-3*sin(3.5*\s)-0.74},{3*cos(3.5*\s)+0.2})}{farbe4}{farbe5}{farbe6}{farbe7}{black,opacity=0} +\perlenb{({-3*sin(3.5*\s)-0.74},{3*cos(3.5*\s)+0.2})}{black,opacity=0}{farbe8}{farbe1}{farbe2}{farbe3} + +\perlena{({-3*sin(4.5*\s)-0.74},{3*cos(4.5*\s)})}{farbe5}{farbe6}{farbe7}{black,opacity=0}{black,opacity=0} +\perlenb{({-3*sin(4.5*\s)-0.74},{3*cos(4.5*\s)})}{farbe8}{farbe1}{farbe2}{farbe3}{farbe4} + +\perlena{({-3*sin(5.5*\s)-0.64},{3*cos(5.5*\s)})}{farbe6}{farbe7}{black,opacity=0}{black,opacity=0}{farbe8} +\perlenb{({-3*sin(5.5*\s)-0.64},{3*cos(5.5*\s)})}{farbe1}{farbe2}{farbe3}{farbe4}{farbe5} + +\perlena{({-3*sin(6.5*\s)-0.64},{3*cos(6.5*\s)})}{farbe7}{black,opacity=0}{black,opacity=0}{farbe8}{farbe1} +\perlenb{({-3*sin(6.5*\s)-0.64},{3*cos(6.5*\s)})}{farbe2}{farbe3}{farbe4}{farbe5}{farbe6} + +\perlena{({-3*sin(7.5*\s)-1.14},{3*cos(7.5*\s)+0.1})}{black,opacity=0}{black,opacity=0}{farbe8}{farbe1}{farbe2} +\perlenb{({-3*sin(7.5*\s)-1.14},{3*cos(7.5*\s)+0.1})}{farbe3}{farbe4}{farbe5}{farbe6}{farbe7} + +\node at (45:4) [above right] {$A$}; + +\clip (-7,-4.4) rectangle (0,4.8); +\foreach \k in {1,...,5}{ + \pgfmathparse{20*(3-\k)} + \xdef\c{\pgfmathresult} + \pgfmathparse{90+(\k-0.5)*\s} + \xdef\a{\pgfmathresult} + \pgfmathparse{\a-180} + \xdef\b{\pgfmathresult} + \draw[->] (-7.5,0) to[out={\c},in={180+\b}] (\a:4); + %\node at (\a:4) [left] {$\b$}; +} +\end{scope} + +\def\pearl#1#2{ + \fill[color=#2] ($({90+(#1-0.5)*\s}:0.6)$) circle[radius=0.12]; + \draw[line width=0.1pt] ($({90+(#1-0.5)*\s}:0.6)$) circle[radius=0.12]; +} + +\def\kette{ + \draw (0,0) circle[radius=0.6]; + \pearl{1}{farbe1} + \pearl{2}{farbe2} + \pearl{3}{farbe3} + \pearl{4}{farbe4} + \pearl{5}{farbe5} + \pearl{6}{farbe6} + \pearl{7}{farbe7} + \pearl{0}{farbe8} +} + +\begin{scope}[xshift=-4.5cm] +\fill[color=white] (-1.5,-2.5) rectangle (1.5,2.5); +\draw (-1.5,-2.5) rectangle (1.5,2.5); +\kette +\node at (-1.5,2.5) [below right] {$G$}; +\end{scope} + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/30-endlichekoerper/wurzeln.tex b/buch/chapters/30-endlichekoerper/wurzeln.tex index 600336c..b066969 100644 --- a/buch/chapters/30-endlichekoerper/wurzeln.tex +++ b/buch/chapters/30-endlichekoerper/wurzeln.tex @@ -52,10 +52,10 @@ Inverse kann zum Beispiel als die inverse Matrix mit dem Gauss-Algorithmus berechnet werden. In einem zweiten Schritt zeigen wir dann, dass man die Rechnung noch etwas vereinfachen kann, wenn man in Polynomringen arbeitet. -Schliesslich zeigen wir dann im -Abschnitt~\ref{buch:subsection:zerfaellungskoerper}, wie man -den Prozess iterieren kann und so für beliebige Polynome immer einen -Körper finden kann, der alle Nullstellen enthält. +%Schliesslich zeigen wir dann im +%Abschnitt~\ref{buch:subsection:zerfaellungskoerper}, wie man +%den Prozess iterieren kann und so für beliebige Polynome immer einen +%Körper finden kann, der alle Nullstellen enthält. Wir beginnen in Abschnitt~\ref{buch:subsection:irreduziblepolynome} damit, die Polynome, die für die Konstruktion in Frage kommen, etwas genauer zu charakterisieren. @@ -608,7 +608,17 @@ $J$ mit $I\subset J\subset R$ entweder $I=J$ oder $J=R$ gilt. Die Ideale $p\mathbb{Z}\subset \mathbb{Z}$ sind maximal genau dann, wenn $p$ eine Primzahl ist. -TODO: XXX Begründung +Ist nämlich $p=n_1n_2$ eine Faktorisierung, dann ist +$\mathbb{Z}\supset n_1\mathbb{Z} \supset p\mathbb{Z}$ +und $n_1\mathbb{Z}$ ist ein grössers Ideal als $p\mathbb{Z}$, +d.~h.~$p\mathbb{Z}$ ist nicht maximal. + +In $\mathbb{Z}$ sind alle Ideale von der Form $n\mathbb{Z}$. +Wenn es also ein Ideal $I\supset p\mathbb{Z}$ gibt, welches +$p\mathbb{Z}$ echt enthält, dann gibt es $n\in\mathbb{Z}$ derart, +dass $n\mathbb{Z} \subset p\mathbb{Z}$. +Dies ist gleichbedeutend damit, dass $n$ ein echter Teiler von $p$ +ist, also ist $p$ keine Primzahl. \end{beispiel} \begin{satz} @@ -616,6 +626,23 @@ Der Ring $R/I$ ist genau dann ein Körper, wenn $I$ ein maximales Ideal ist. \end{satz} \begin{proof}[Beweis] +Nehmen wir zunächst an, dass $I$ ein maximales Ideal ist. +Damit $R/I$ ein Körper ist, muss jedes von $0$ verschiedene Element +eine multiplikatives Inverses haben. +Sei als $a\in R\setminus I$, dann ist $a+I$ ein von $0$ verschiedenes +Körperelement. +Die Menge $Ra+I$ ist dann ein Ideal von $R$, welches $I$ echt enthält. +Weil $I$ maximal ist, ist $Ra+I=R$, also gibt es ein Element $b\in I$ +derart, dass $ab+I=1+I$, d.~h.~$b+I$ ist das gesuchte multiplikative +Inverse. + +Sei nun umgekehrt $R/I$ ein Körper und $J\supset I$ sei ein Ideal, +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$. +Andererseits ist $1\in Ra$, also ist $J=R$ und das Ideal $J$ ist maximal. \end{proof} Ein irreduzibles Polynom $m\in\Bbbk[X]$ erzeugt ein maximales Ideal, @@ -894,10 +921,3 @@ 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. -\subsection{Zerfällungskörper -\label{buch:subsection:zerfaellungskoerper}} -XXX TODO - - - - -- cgit v1.2.1