aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorAndreas Müller <andreas.mueller@ost.ch>2021-03-02 10:23:02 +0100
committerAndreas Müller <andreas.mueller@ost.ch>2021-03-02 10:23:02 +0100
commita04efb8ee3eef6ec32b1381801ee244744db1201 (patch)
tree7d3ac94373d0c4ad7e5fa01b24152742851a2357
parentadd slides (diff)
downloadSeminarMatrizen-a04efb8ee3eef6ec32b1381801ee244744db1201.tar.gz
SeminarMatrizen-a04efb8ee3eef6ec32b1381801ee244744db1201.zip
division in F_p
Diffstat (limited to '')
-rw-r--r--vorlesungen/slides/4/Makefile.inc2
-rw-r--r--vorlesungen/slides/4/chapter.tex2
-rw-r--r--vorlesungen/slides/4/division.tex62
-rw-r--r--vorlesungen/slides/4/euklidtabelle.tex64
-rw-r--r--vorlesungen/slides/4/fp.tex25
-rw-r--r--vorlesungen/slides/test.tex3
6 files changed, 155 insertions, 3 deletions
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}