From a04efb8ee3eef6ec32b1381801ee244744db1201 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Andreas=20M=C3=BCller?= <andreas.mueller@ost.ch>
Date: Tue, 2 Mar 2021 10:23:02 +0100
Subject: division in F_p

---
 vorlesungen/slides/4/Makefile.inc      |  2 ++
 vorlesungen/slides/4/chapter.tex       |  2 ++
 vorlesungen/slides/4/division.tex      | 62 ++++++++++++++++++++++++++++++++
 vorlesungen/slides/4/euklidtabelle.tex | 64 ++++++++++++++++++++++++++++++++++
 vorlesungen/slides/4/fp.tex            | 25 +++++++++++--
 vorlesungen/slides/test.tex            |  3 +-
 6 files changed, 155 insertions(+), 3 deletions(-)
 create mode 100644 vorlesungen/slides/4/division.tex
 create mode 100644 vorlesungen/slides/4/euklidtabelle.tex

diff --git a/vorlesungen/slides/4/Makefile.inc b/vorlesungen/slides/4/Makefile.inc
index 24e4a80..0adf913 100644
--- a/vorlesungen/slides/4/Makefile.inc
+++ b/vorlesungen/slides/4/Makefile.inc
@@ -8,6 +8,8 @@ chapter4 =								\
 	../slides/4/ggt.tex						\
 	../slides/4/euklidmatrix.tex					\
 	../slides/4/euklidbeispiel.tex					\
+	../slides/4/euklidtabelle.tex					\
 	../slides/4/fp.tex						\
+	../slides/4/division.tex					\
 	../slides/4/chapter.tex
 
diff --git a/vorlesungen/slides/4/chapter.tex b/vorlesungen/slides/4/chapter.tex
index 4fec776..1c23783 100644
--- a/vorlesungen/slides/4/chapter.tex
+++ b/vorlesungen/slides/4/chapter.tex
@@ -6,4 +6,6 @@
 \folie{4/ggt.tex}
 \folie{4/euklidmatrix.tex}
 \folie{4/euklidbeispiel.tex}
+\folie{4/euklidtabelle.tex}
 \folie{4/fp.tex}
+\folie{4/division.tex}
diff --git a/vorlesungen/slides/4/division.tex b/vorlesungen/slides/4/division.tex
new file mode 100644
index 0000000..aeab1e3
--- /dev/null
+++ b/vorlesungen/slides/4/division.tex
@@ -0,0 +1,62 @@
+%
+% division.tex
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\begin{frame}[t]
+\frametitle{Division in $\mathbb{F}_p$}
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{block}{Inverse {\bf berechnen}}
+Gegeben $a\in\mathbb{F}_p$, finde $b=a^{-1}\in\mathbb{F}_p$
+\begin{align*}
+&& a{\color{red}b} &\equiv 1 \mod p
+\\
+&\Leftrightarrow& a{\color{red}b}&=1 + {\color{red}n}p
+\\
+&&a{\color{red}b}-{\color{red}n}p&=1
+\end{align*}
+Wegen
+$\operatorname{ggT}(a,p)=1$ gibt es
+$s$ und $t$ mit
+\[
+sa+tb=1
+\Rightarrow
+{\color{red}b}=s,\;
+{\color{red}n}=-t
+\]
+$\Rightarrow$ Die Inverse kann mit dem euklidischen Algorithmus
+berechnet werden
+\end{block}
+\end{column}
+\begin{column}{0.48\textwidth}
+\begin{block}{Beispiel in $\mathbb{F}_{1291}$}
+Finde $47^{-1}\in\mathbb{F}_{1291}$
+%\vspace{-10pt}
+\begin{center}
+\begin{tabular}{|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|}
+\hline
+k& a_k& b_k&q_k&  c_k& d_k\\
+\hline
+ &    &    &   &    1&   0\\
+0&  47&1291&  0&    0&   1\\
+1&1291&  47& 27&    1&   0\\
+2&  47&  22&  2&  -27&   1\\
+3&  22&   3&  7&   55&  -2\\
+4&   3&   1&  3&{\color{red}-412}&{\color{red}15}\\
+5&   1&   0&   & 1291& -47\\
+\hline
+\end{tabular}
+\end{center}
+\[
+{\color{red}-412}\cdot 47 +{\color{red}15}\cdot 1291 = 1
+\;\Rightarrow\;
+47^{-1}={\color{red}879}
+\]
+\end{block}
+\end{column}
+\end{columns}
+\end{frame}
diff --git a/vorlesungen/slides/4/euklidtabelle.tex b/vorlesungen/slides/4/euklidtabelle.tex
new file mode 100644
index 0000000..2d67823
--- /dev/null
+++ b/vorlesungen/slides/4/euklidtabelle.tex
@@ -0,0 +1,64 @@
+%
+% euklidtabelle.tex
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Durchführung des euklidischen Algorithmus}
+Problem: Berechnung der Produkte $Q(q_k)\cdots Q(q_1)Q(q_0)$ für $k=0,1,\dots,n$
+\begin{block}{Multiplikation mit $Q(q_k)$}
+\vspace{-12pt}
+\begin{align*}
+Q(q_k)
+%\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}
+&&\Rightarrow&
+\begin{pmatrix}
+c_k&d_k\\c_{k+1}&d_{k+1}
+\end{pmatrix}
+&=
+Q(q_k)
+%\begin{pmatrix}
+%0&1\\1&-q_k
+%\end{pmatrix}
+\begin{pmatrix}
+c_{k-1}&d_{k-1}\\c_{k}&d_{k}
+\end{pmatrix}
+\end{align*}
+\end{block}
+\vspace{-10pt}
+\begin{equation*}
+\begin{tabular}{|>{\tiny$}r<{$}|>{$}c<{$}|>{$}c<{$}>{$}c<{$}|}
+\hline
+k  &q_k    &                     c_k    &                     d_k    \\
+\hline
+-1 &       &                     1      &                     0      \\
+ 0 &q_0    &                     0      &                     1      \\
+ 1 &q_1    &c_{-1} -q_0    \cdot c_0    &d_{-1} -q_0    \cdot d_0    \\
+ 2 &q_2    &c_0    -q_1    \cdot c_1    &d_0    -q_1    \cdot d_1    \\
+\vdots&\vdots&\vdots                    &\vdots                      \\
+ n &q_n    &c_{n-2}-q_{n-1}\cdot c_{n-1}&d_{n-2}-q_{n-1}\cdot d_{n-1}\\
+n+1&       &c_{n-1}-q_{n}  \cdot c_{n}  &d_{n-1}-q_{n}  \cdot d_{n}  \\
+\hline
+\end{tabular}
+\Rightarrow
+\left\{
+\begin{aligned}
+\rlap{$c_{n}$}\phantom{c_{n+1}} a + \rlap{$d_n$}\phantom{d_{n+1}}b &= \operatorname{ggT}(a,b)
+\\
+c_{n+1} a + d_{n+1} b &= 0
+\end{aligned}
+\right.
+\end{equation*}
+\end{frame}
diff --git a/vorlesungen/slides/4/fp.tex b/vorlesungen/slides/4/fp.tex
index a893238..caa6ceb 100644
--- a/vorlesungen/slides/4/fp.tex
+++ b/vorlesungen/slides/4/fp.tex
@@ -13,6 +13,13 @@
 \def\rot#1#2{
 	\fill[color=red!20] ({#1-0.5},{5-#2-0.5}) rectangle ({#1+0.5},{5-#2+0.5});
 }
+\definecolor{darkgreen}{rgb}{0,0.6,0}
+\def\gruen#1#2{
+	\fill[color=darkgreen!20] ({#1-0.5},{6-#2-0.5}) rectangle ({#1+0.5},{6-#2+0.5});
+}
+\def\inverse#1#2{
+	\node at (9,{6-#1}) {$#1^{-1}=#2\mathstrut$};
+}
 \begin{frame}[t]
 \frametitle{Galois-Körper}
 \vspace{-20pt}
@@ -53,7 +60,9 @@ $\Rightarrow \quad \mathbb{F}_p$ ist ein Körper
 \vspace{-20pt}
 \begin{center}
 \begin{tikzpicture}[>=latex,thick,scale=0.45]
-\begin{scope}[xshift=-7cm]
+\fill[color=white] (-12,0) circle[radius=0.1];
+\fill[color=white] (12,0) circle[radius=0.1];
+\begin{scope}[xshift=-8cm]
 \rot{2}{3}
 \rot{4}{3}
 \rot{3}{2}
@@ -98,7 +107,13 @@ $\Rightarrow \quad \mathbb{F}_p$ ist ein Körper
 \feld{4}{5}{2} \feld{5}{4}{2}
 \feld{5}{5}{1}
 \end{scope}
-\begin{scope}[xshift=7cm]
+\begin{scope}[xshift=6cm]
+\gruen{1}{1}
+\gruen{2}{4}
+\gruen{3}{5}
+\gruen{4}{2}
+\gruen{5}{3}
+\gruen{6}{6}
 \fill[color=gray!40] (-0.5,6.5) rectangle (6.5,7.5);
 \fill[color=gray!40] (-1.5,-0.5) rectangle (-0.5,6.5);
 \foreach \x in {-0.5,6.5}{
@@ -143,6 +158,12 @@ $\Rightarrow \quad \mathbb{F}_p$ ist ein Körper
 \geld{5}{5}{4}
 \geld{6}{5}{2} \geld{5}{6}{2}
 \geld{6}{6}{1}
+\inverse{1}{1}
+\inverse{2}{4}
+\inverse{3}{5}
+\inverse{4}{2}
+\inverse{5}{3}
+\inverse{6}{6}
 \end{scope}
 \end{tikzpicture}
 \end{center}
diff --git a/vorlesungen/slides/test.tex b/vorlesungen/slides/test.tex
index e7108ec..8d3d490 100644
--- a/vorlesungen/slides/test.tex
+++ b/vorlesungen/slides/test.tex
@@ -32,8 +32,9 @@
 \folie{4/ggt.tex}
 \folie{4/euklidmatrix.tex}
 \folie{4/euklidbeispiel.tex}
+\folie{4/euklidtabelle.tex}
 \folie{4/fp.tex}
-% XXX \folie{4/division.tex}
+\folie{4/division.tex}
 % XXX \folie{4/gauss.tex}
 % XXX \folie{4/dh.tex}
 % XXX ? \folie{4/polynomefp.tex}
-- 
cgit v1.2.1