diff options
| -rw-r--r-- | vorlesungen/slides/4/Makefile.inc | 2 | ||||
| -rw-r--r-- | vorlesungen/slides/4/chapter.tex | 2 | ||||
| -rw-r--r-- | vorlesungen/slides/4/division.tex | 62 | ||||
| -rw-r--r-- | vorlesungen/slides/4/euklidtabelle.tex | 64 | ||||
| -rw-r--r-- | vorlesungen/slides/4/fp.tex | 25 | ||||
| -rw-r--r-- | vorlesungen/slides/test.tex | 3 |
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} |