From 6a56afa0e79fb4ac6f04c1d3c3a8e6314331989b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 1 Mar 2021 16:04:13 +0100 Subject: new slides --- vorlesungen/slides/4/Makefile.inc | 10 ++++++ vorlesungen/slides/4/chapter.tex | 6 ++++ vorlesungen/slides/4/euklidmatrix.tex | 9 +++++ vorlesungen/slides/4/ggt.tex | 62 +++++++++++++++++++++++++++++++++++ 4 files changed, 87 insertions(+) create mode 100644 vorlesungen/slides/4/Makefile.inc create mode 100644 vorlesungen/slides/4/chapter.tex create mode 100644 vorlesungen/slides/4/euklidmatrix.tex create mode 100644 vorlesungen/slides/4/ggt.tex (limited to 'vorlesungen/slides/4') diff --git a/vorlesungen/slides/4/Makefile.inc b/vorlesungen/slides/4/Makefile.inc new file mode 100644 index 0000000..dabdb7c --- /dev/null +++ b/vorlesungen/slides/4/Makefile.inc @@ -0,0 +1,10 @@ + +# +# Makefile.inc -- additional depencencies +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +chapter4 = \ + ../slides/4/ggt.tex \ + ../slides/4/chapter.tex + diff --git a/vorlesungen/slides/4/chapter.tex b/vorlesungen/slides/4/chapter.tex new file mode 100644 index 0000000..1e04e9f --- /dev/null +++ b/vorlesungen/slides/4/chapter.tex @@ -0,0 +1,6 @@ +% +% chapter.tex +% +% (c) 2021 Prof Dr Andreas Müller, Hochschule Rapperswi +% +\folie{4/ggt.tex} diff --git a/vorlesungen/slides/4/euklidmatrix.tex b/vorlesungen/slides/4/euklidmatrix.tex new file mode 100644 index 0000000..2090c0a --- /dev/null +++ b/vorlesungen/slides/4/euklidmatrix.tex @@ -0,0 +1,9 @@ +% +% euklidmatrix.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostscheizer Fachhochschule +% +\begin{frame}[t] +\frametitle{Matrixform} + +\end{frame} diff --git a/vorlesungen/slides/4/ggt.tex b/vorlesungen/slides/4/ggt.tex new file mode 100644 index 0000000..77b2a1d --- /dev/null +++ b/vorlesungen/slides/4/ggt.tex @@ -0,0 +1,62 @@ +% +% ggt.tex -- GGT, Definition und Algorithmus +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschuöe +% +\begin{frame}[t] +\frametitle{Grösster gemeinsamer Teiler} +\vspace{-15pt} +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{block}{Definition} +Gegeben: $a,b\in\mathbb Z$ +\\ +Gesucht: grösster gemeinsamer Teiler $\operatorname{ggT}(a,b)$ +\end{block} +\begin{block}{Euklidischer Algorithmus} +$a_0 = a$, $b_0=b$ +\begin{align*} +a_0&=b_0q_0 + r_0 & a_1 &=b_0 & b_1&=r_0 \\ +a_1&=b_1q_1 + r_1 & a_2 &=b_1 & b_2&=r_1 \\ +a_2&=b_2q_2 + r_2 & a_3 &=b_2 & b_3&=r_2 \\ + &\;\vdots & & & & \\ +a_n&=b_nq_n + r_n & r_n &= 0 & r_{n-1}&)=\operatorname{ggT}(a,b) +\end{align*} +\end{block} +\end{column} +\begin{column}{0.48\textwidth} +\begin{block}{$\operatorname{ggT}(15,25) = 5$} +\begin{center} +\begin{tikzpicture}[>=latex,thick,scale=0.09] +\draw[->] (-1,0) -- (65,0) coordinate[label={$a$}]; +\draw[->] (0,-1) -- (0,65) coordinate[label={right:$b$}]; +\begin{scope} +\clip (-1,-1) rectangle (65,65); +\foreach \x in {0,...,4}{ + \draw[line width=0.2pt] ({\x*15},-2) -- ({\x*15},65); +} +\foreach \y in {0,...,2}{ + \draw[line width=0.2pt] (-2,{\y*25}) -- (65,{\y*25}); +} +\foreach \x in {0,5,...,120}{ + \draw[color=blue] ({\x+2},-2) -- ({\x+2-70},{-2+70}); + \node[color=blue] at ({0.5*\x-0.5},{0.5*\x-0.5}) [rotate=-45,above] {\tiny $\x$}; +} +\foreach \x in {0,...,4}{ + \foreach \y in {0,...,2}{ + \fill[color=red] ({\x*15},{\y*25}) circle[radius=0.8]; + } +} +\foreach \x in {0,5,...,60}{ + \fill[color=blue] (\x,0) circle[radius=0.5]; + \node at (\x,0) [below] {\tiny $\x$}; +} +\end{scope} +\end{tikzpicture} +\end{center} +\end{block} +\end{column} +\end{columns} +\end{frame} -- cgit v1.2.1 From ca12778acdf6f2da84aec311c5ab63cde5d847cd Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 1 Mar 2021 21:20:36 +0100 Subject: add slides --- vorlesungen/slides/4/Makefile.inc | 3 + vorlesungen/slides/4/chapter.tex | 3 + vorlesungen/slides/4/euklidbeispiel.tex | 44 ++++++++++ vorlesungen/slides/4/euklidmatrix.tex | 86 +++++++++++++++++- vorlesungen/slides/4/fp.tex | 150 ++++++++++++++++++++++++++++++++ vorlesungen/slides/4/ggt.tex | 2 +- 6 files changed, 286 insertions(+), 2 deletions(-) create mode 100644 vorlesungen/slides/4/euklidbeispiel.tex create mode 100644 vorlesungen/slides/4/fp.tex (limited to 'vorlesungen/slides/4') diff --git a/vorlesungen/slides/4/Makefile.inc b/vorlesungen/slides/4/Makefile.inc index dabdb7c..24e4a80 100644 --- a/vorlesungen/slides/4/Makefile.inc +++ b/vorlesungen/slides/4/Makefile.inc @@ -6,5 +6,8 @@ # chapter4 = \ ../slides/4/ggt.tex \ + ../slides/4/euklidmatrix.tex \ + ../slides/4/euklidbeispiel.tex \ + ../slides/4/fp.tex \ ../slides/4/chapter.tex diff --git a/vorlesungen/slides/4/chapter.tex b/vorlesungen/slides/4/chapter.tex index 1e04e9f..4fec776 100644 --- a/vorlesungen/slides/4/chapter.tex +++ b/vorlesungen/slides/4/chapter.tex @@ -4,3 +4,6 @@ % (c) 2021 Prof Dr Andreas Müller, Hochschule Rapperswi % \folie{4/ggt.tex} +\folie{4/euklidmatrix.tex} +\folie{4/euklidbeispiel.tex} +\folie{4/fp.tex} diff --git a/vorlesungen/slides/4/euklidbeispiel.tex b/vorlesungen/slides/4/euklidbeispiel.tex new file mode 100644 index 0000000..cbc3137 --- /dev/null +++ b/vorlesungen/slides/4/euklidbeispiel.tex @@ -0,0 +1,44 @@ +% +% euklidmatrix.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostscheizer Fachhochschule +% +\bgroup +\definecolor{darkgreen}{rgb}{0,0.6,0} +\begin{frame}[t] +\frametitle{Beispiel} +\setlength{\abovedisplayskip}{0pt} +\setlength{\belowdisplayskip}{0pt} +\vspace{-0pt} +\begin{block}{Finde $\operatorname{ggT}(25,15)$} +\vspace{-12pt} +\begin{align*} +a_0&=25 & b_0 &= 15 &25&=15 \cdot {\color{red} 1} + 10 &q_0 &= {\color{red}1} & r_0 &= 10\\ +a_1&=15 & b_1 &= 10 &15&=10 \cdot {\color{darkgreen}1} + \phantom{0}5 &q_1 &= {\color{darkgreen}1} & r_1 &= \phantom{0}5 \\ +a_2&=10 & b_2 &= \phantom{0}5 &10&=\phantom{0}5 \cdot {\color{blue} 2} + \phantom{0}0 &q_2 &= {\color{blue}2} & r_2 &= \phantom{0}0 +\end{align*} +\end{block} +\vspace{-5pt} +\begin{block}{Matrix-Operationen} +\begin{align*} +Q +&= +Q({\color{blue}2}) Q({\color{darkgreen}1}) Q({\color{red}1}) += +\begin{pmatrix}0&1\\1&-{\color{blue}2}\end{pmatrix} +\begin{pmatrix}0&1\\1&-{\color{darkgreen}1}\end{pmatrix} +\begin{pmatrix}0&1\\1&-{\color{red}1}\end{pmatrix} +=\begin{pmatrix} +-1&2\\3&-5 +\end{pmatrix} +\end{align*} +\end{block} +\vspace{-5pt} +\begin{block}{Relationen ablesen} +\begin{align*} +\operatorname{ggT}({\usebeamercolor[fg]{title}25},{\usebeamercolor[fg]{title}15}) &= 5 = -1\cdot {\usebeamercolor[fg]{title}25} + 2\cdot {\usebeamercolor[fg]{title}15} \\ + 0 &= \phantom{5=-}3\cdot {\usebeamercolor[fg]{title}25} -5\cdot {\usebeamercolor[fg]{title}15} +\end{align*} +\end{block} + +\end{frame} diff --git a/vorlesungen/slides/4/euklidmatrix.tex b/vorlesungen/slides/4/euklidmatrix.tex index 2090c0a..6ffa4c2 100644 --- a/vorlesungen/slides/4/euklidmatrix.tex +++ b/vorlesungen/slides/4/euklidmatrix.tex @@ -4,6 +4,90 @@ % (c) 2021 Prof Dr Andreas Müller, OST Ostscheizer Fachhochschule % \begin{frame}[t] -\frametitle{Matrixform} +\frametitle{Matrixform des euklidischen Algorithmus} +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.52\textwidth} +\begin{block}{Einzelschritt} +\vspace{-10pt} +\[ +a_k = b_kq_k + r_k +\;\Rightarrow\; +\left\{ +\begin{aligned} +a_{k+1} &= b_k = \phantom{a_k-q_k}\llap{$-\mathstrut$}b_k \\ +b_{k+1} &= \phantom{b_k}\llap{$r_k$} = a_k - q_kb_k +\end{aligned} +\right. +\] +\end{block} +\end{column} +\begin{column}{0.44\textwidth} +\begin{block}{Matrixschreibweise} +\vspace{-10pt} +\begin{align*} +\begin{pmatrix} +a_{k+1}\\ +b_{k+1} +\end{pmatrix} +&= +\begin{pmatrix} +b_k\\r_k +\end{pmatrix} += +\underbrace{\begin{pmatrix}0&1\\1&-q_k\end{pmatrix}}_{\displaystyle =Q(q_k)} +\begin{pmatrix} +a_k\\b_k +\end{pmatrix} +\end{align*} +\end{block} +\end{column} +\end{columns} +\vspace{-10pt} +\begin{block}{Ende des Algorithmus} +\vspace{-10pt} +\begin{align*} +\begin{pmatrix} +a_{n+1}\\ +b_{n+1}\\ +\end{pmatrix} +&= +\begin{pmatrix} +r_{n-1}\\ +r_{n} +\end{pmatrix} += +\begin{pmatrix} +\operatorname{ggT}(a,b) \\ +0 +\end{pmatrix} += +\underbrace{Q(q_n) +\dots +Q(q_1) +Q(q_0)}_{\displaystyle =Q} +\begin{pmatrix} a_0\\ b_0\end{pmatrix} += +Q\begin{pmatrix}a\\b\end{pmatrix} +\end{align*} +\end{block} +\begin{block}{Konsequenzen} +\[ +Q=\begin{pmatrix} +q_{11}&q_{12}\\ +a_{21}&q_{22} +\end{pmatrix} +\quad\Rightarrow\quad +\left\{ +\quad +\begin{aligned} +\operatorname{ggT}(a,b) &= q_{11}a + q_{12}b \\ + 0 &= q_{21}a + q_{22}b +\end{aligned} +\right. +\] +\end{block} \end{frame} diff --git a/vorlesungen/slides/4/fp.tex b/vorlesungen/slides/4/fp.tex new file mode 100644 index 0000000..a893238 --- /dev/null +++ b/vorlesungen/slides/4/fp.tex @@ -0,0 +1,150 @@ +% +% fp.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\def\feld#1#2#3{ + \node at ({#1},{5-#2}) {$#3$}; +} +\def\geld#1#2#3{ + \node at ({#1},{6-#2}) {$#3$}; +} +\def\rot#1#2{ + \fill[color=red!20] ({#1-0.5},{5-#2-0.5}) rectangle ({#1+0.5},{5-#2+0.5}); +} +\begin{frame}[t] +\frametitle{Galois-Körper} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{block}{Restklassenring$\mathstrut$} +$\mathbb{Z}/n\mathbb{Z} +=\{ \llbracket r\rrbracket\;|\; 0\le r < n \} \mathstrut$ +ist ein Ring +\end{block} +\begin{block}{Nullteiler} +Falls $n=n_1n_2$, dann sind $\llbracket n_1\rrbracket$ und +$\llbracket n_2\rrbracket$ Nullteiler in $\mathbb{Z}/n\mathbb{Z}$: +\[ +\llbracket n_1\rrbracket +\llbracket n_2\rrbracket += +\llbracket n_1n_2 \rrbracket += +\llbracket n\rrbracket += +\llbracket 0 \rrbracket +\] +\end{block} +\end{column} +\begin{column}{0.48\textwidth} +\begin{block}{Galois-Körper $\mathbb{F}_p\mathstrut$} +$\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}\mathstrut$ +\end{block} +\begin{block}{$n$ prim} +Für $n=p$ prim ist $\mathbb{Z}/n\mathbb{Z}$ nullteilerfrei +\medskip + +$\Rightarrow \quad \mathbb{F}_p$ ist ein Körper +\end{block} +\end{column} +\end{columns} +\vspace{-20pt} +\begin{center} +\begin{tikzpicture}[>=latex,thick,scale=0.45] +\begin{scope}[xshift=-7cm] +\rot{2}{3} +\rot{4}{3} +\rot{3}{2} +\rot{3}{4} +\fill[color=gray!40] (-0.5,5.5) rectangle (5.5,6.5); +\fill[color=gray!40] (-1.5,-0.5) rectangle (-0.5,5.5); +\foreach \x in {-0.5,5.5}{ + \draw (\x,-0.5) -- (\x,6.5); +} +\foreach \x in {0.5,...,4.5}{ + \draw[line width=0.3pt] (\x,-0.5) -- (\x,6.5); +} +\foreach \y in {0.5,...,5.5}{ + \draw[line width=0.3pt] (-1.5,\y) -- (5.5,\y); +} +\foreach \y in {-0.5,5.5}{ + \draw (-1.5,\y) -- (5.5,\y); +} +\draw (-1.5,-0.5) -- (-1.5,5.5); +\draw (-0.5,6.5) -- (5.5,6.5); +\foreach \x in {0,...,5}{ + \node at (\x,6) {$\x$}; + \node at (-1,{5-\x}) {$\x$}; +} +\foreach \x in {0,...,5}{ + \feld{\x}{0}{0} + \feld{0}{\x}{0} +} +\foreach \x in {2,...,5}{ + \feld{\x}{1}{\x} + \feld{1}{\x}{\x} +} +\feld{1}{1}{1} +\feld{2}{2}{4} +\feld{2}{3}{0} \feld{3}{2}{0} +\feld{2}{4}{2} \feld{4}{2}{2} +\feld{2}{5}{4} \feld{5}{2}{4} +\feld{3}{3}{3} +\feld{4}{3}{0} \feld{3}{4}{0} +\feld{5}{3}{3} \feld{3}{5}{3} +\feld{4}{4}{4} +\feld{4}{5}{2} \feld{5}{4}{2} +\feld{5}{5}{1} +\end{scope} +\begin{scope}[xshift=7cm] +\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}{ + \draw (\x,-0.5) -- (\x,7.5); +} +\foreach \x in {0.5,...,5.5}{ + \draw[line width=0.3pt] (\x,-0.5) -- (\x,7.5); +} +\foreach \y in {0.5,...,6.5}{ + \draw[line width=0.3pt] (-1.5,\y) -- (6.5,\y); +} +\foreach \y in {-0.5,6.5}{ + \draw (-1.5,\y) -- (6.5,\y); +} +\draw (-1.5,-0.5) -- (-1.5,6.5); +\draw (-0.5,7.5) -- (6.5,7.5); +\foreach \x in {0,...,6}{ + \node at (\x,7) {$\x$}; + \node at (-1,{6-\x}) {$\x$}; +} +\foreach \x in {0,...,6}{ + \geld{\x}{0}{0} + \geld{0}{\x}{0} +} +\foreach \x in {2,...,6}{ + \geld{\x}{1}{\x} + \geld{1}{\x}{\x} +} +\geld{1}{1}{1} +\geld{2}{2}{4} +\geld{2}{3}{6} \geld{3}{2}{6} +\geld{2}{4}{1} \geld{4}{2}{1} +\geld{2}{5}{3} \geld{5}{2}{3} +\geld{2}{6}{5} \geld{6}{2}{5} +\geld{3}{3}{2} +\geld{4}{3}{5} \geld{3}{4}{5} +\geld{5}{3}{1} \geld{3}{5}{1} +\geld{6}{3}{4} \geld{3}{6}{4} +\geld{4}{4}{2} +\geld{5}{4}{6} \geld{4}{5}{6} +\geld{6}{4}{3} \geld{4}{6}{3} +\geld{5}{5}{4} +\geld{6}{5}{2} \geld{5}{6}{2} +\geld{6}{6}{1} +\end{scope} +\end{tikzpicture} +\end{center} +\end{frame} +\egroup diff --git a/vorlesungen/slides/4/ggt.tex b/vorlesungen/slides/4/ggt.tex index 77b2a1d..e3c55e6 100644 --- a/vorlesungen/slides/4/ggt.tex +++ b/vorlesungen/slides/4/ggt.tex @@ -22,7 +22,7 @@ a_0&=b_0q_0 + r_0 & a_1 &=b_0 & b_1&=r_0 \\ a_1&=b_1q_1 + r_1 & a_2 &=b_1 & b_2&=r_1 \\ a_2&=b_2q_2 + r_2 & a_3 &=b_2 & b_3&=r_2 \\ &\;\vdots & & & & \\ -a_n&=b_nq_n + r_n & r_n &= 0 & r_{n-1}&)=\operatorname{ggT}(a,b) +a_n&=b_nq_n + r_n & r_n &= 0 & r_{n-1}&=\operatorname{ggT}(a,b) \end{align*} \end{block} \end{column} -- cgit v1.2.1 From a04efb8ee3eef6ec32b1381801ee244744db1201 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= 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 +++++++++++-- 5 files changed, 153 insertions(+), 2 deletions(-) create mode 100644 vorlesungen/slides/4/division.tex create mode 100644 vorlesungen/slides/4/euklidtabelle.tex (limited to 'vorlesungen/slides/4') 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} -- cgit v1.2.1 From 9243858393d79e761f03b4454547310056d7fcea Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sun, 7 Mar 2021 21:00:59 +0100 Subject: Gauss --- vorlesungen/slides/4/Makefile.inc | 1 + vorlesungen/slides/4/chapter.tex | 1 + vorlesungen/slides/4/gauss.tex | 143 ++++++++++++++++++++++++++++++++++++++ 3 files changed, 145 insertions(+) create mode 100644 vorlesungen/slides/4/gauss.tex (limited to 'vorlesungen/slides/4') diff --git a/vorlesungen/slides/4/Makefile.inc b/vorlesungen/slides/4/Makefile.inc index 0adf913..91767a9 100644 --- a/vorlesungen/slides/4/Makefile.inc +++ b/vorlesungen/slides/4/Makefile.inc @@ -11,5 +11,6 @@ chapter4 = \ ../slides/4/euklidtabelle.tex \ ../slides/4/fp.tex \ ../slides/4/division.tex \ + ../slides/4/gauss.tex \ ../slides/4/chapter.tex diff --git a/vorlesungen/slides/4/chapter.tex b/vorlesungen/slides/4/chapter.tex index 1c23783..27884a1 100644 --- a/vorlesungen/slides/4/chapter.tex +++ b/vorlesungen/slides/4/chapter.tex @@ -9,3 +9,4 @@ \folie{4/euklidtabelle.tex} \folie{4/fp.tex} \folie{4/division.tex} +\folie{4/gauss.tex} diff --git a/vorlesungen/slides/4/gauss.tex b/vorlesungen/slides/4/gauss.tex new file mode 100644 index 0000000..960e8e1 --- /dev/null +++ b/vorlesungen/slides/4/gauss.tex @@ -0,0 +1,143 @@ +% +% gauss.tex +% +% (c) 2021 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\bgroup +\def\ds{0.5} +\def\punkt#1#2{({(#1)*\ds},{-(#2)*\ds})} +\def\tabelle{ + \foreach \x in {-0.5,0.5,3.5}{ + \draw \punkt{\x}{-0.5} -- \punkt{\x}{3.5}; + \draw \punkt{-0.5}{\x} -- \punkt{3.5}{\x}; + } + \node at \punkt{0}{1} {$0$}; + \node at \punkt{0}{2} {$1$}; + \node at \punkt{0}{3} {$2$}; + \node at \punkt{1}{0} {$0$}; + \node at \punkt{2}{0} {$1$}; + \node at \punkt{3}{0} {$2$}; +} +\begin{frame}[t] +\frametitle{Gauss-Algorithmus in $\mathbb{F}_3$} +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.44\textwidth} +\begin{block}{Additions-/Multiplikationstabelle} +\begin{center} +\begin{tikzpicture}[>=latex,thick] +\begin{scope}[xshift=-1.6cm] +\tabelle +\node at \punkt{0}{0} {$+$}; +\node at \punkt{1}{1} {$0$}; +\node at \punkt{1}{2} {$1$}; +\node at \punkt{1}{3} {$2$}; +\node at \punkt{2}{1} {$1$}; +\node at \punkt{2}{2} {$2$}; +\node at \punkt{2}{3} {$0$}; +\node at \punkt{3}{1} {$2$}; +\node at \punkt{3}{2} {$0$}; +\node at \punkt{3}{3} {$1$}; +\end{scope} +\begin{scope}[xshift=1.6cm] +\tabelle +\node at \punkt{0}{0} {$\cdot$}; +\node at \punkt{1}{1} {$0$}; +\node at \punkt{1}{2} {$0$}; +\node at \punkt{1}{3} {$0$}; +\node at \punkt{2}{1} {$0$}; +\node at \punkt{2}{2} {$1$}; +\node at \punkt{2}{3} {$2$}; +\node at \punkt{3}{1} {$0$}; +\node at \punkt{3}{2} {$2$}; +\node at \punkt{3}{3} {$1$}; +\end{scope} +\end{tikzpicture} +\end{center} + +\end{block} +\end{column} +\begin{column}{0.52\textwidth} +\uncover<2->{% +\begin{block}{Gleichungssystem\uncover<9->{/Lösung}} +\[ +\left. +\begin{array}{rcrcrcrcr} + x&+&y&+2z&=&1\\ +2x& & &+ z&=&2\\ + x&+&y& &=&2 +\end{array} +\uncover<9->{ +\right\} +\Rightarrow +\left\{ +\begin{aligned} +x&=2\\ +y&=0\\ +z&=1 +\end{aligned} +\right.} +\] +\end{block}} +\end{column} +\end{columns} +\uncover<3->{% +\begin{block}{Gauss-Algorithmus} +\begin{center} +\begin{tikzpicture}[>=latex,thick] +\node at (0,0) {\begin{minipage}{13cm}% +\[ +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|} +\hline + 1 & 1 & 2 & 1 \\ + 2 & 0 & 1 & 2 \\ + 1 & 1 & 0 & 2 \\ +\hline +\end{tabular} +\uncover<4->{% +\to +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|} +\hline + 1 & 1 & 2 & 1 \\ + 0 & 1 & 0 & 0 \\ + 0 & 0 & 1 & 1 \\ +\hline +\end{tabular}} +\uncover<6->{% +\to +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|} +\hline + 1 & 1 & 0 & 2 \\ + 0 & 1 & 0 & 0 \\ + 0 & 0 & 1 & 1 \\ +\hline +\end{tabular}} +\uncover<8->{% +\to +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|} +\hline + 1 & 0 & 0 & 2 \\ + 0 & 1 & 0 & 0 \\ + 0 & 0 & 1 & 1 \\ +\hline +\end{tabular}} +\] +\end{minipage}}; +\begin{scope}[yshift=0.2cm] +\uncover<3->{ +\draw[color=red] (-5.6,0.3) circle[radius=0.2]; +\draw[color=blue] (-5.4,-0.8) -- (-5.4,-0.2) arc (0:180:0.2) -- (-5.8,-0.8); +} +\uncover<5->{ +\draw[color=blue] (-1.45,0.5) -- (-1.45,-0.2) arc (180:360:0.2) -- (-1.05,0.5); +} +\uncover<7->{ +\draw[color=blue] (1.05,0.5) -- (1.05,0.2) arc (180:360:0.2) -- (1.45,0.5); +} +\end{scope} +\end{tikzpicture} +\end{center} +\end{block}} +\end{frame} +\egroup -- cgit v1.2.1 From a5eaa4838f81fe396b428708702bc392189e7484 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sun, 7 Mar 2021 21:15:31 +0100 Subject: Diffie-Hellmann --- vorlesungen/slides/4/Makefile.inc | 1 + vorlesungen/slides/4/chapter.tex | 1 + vorlesungen/slides/4/dh.tex | 62 +++++++++++++++++++++++++++++++++++++++ 3 files changed, 64 insertions(+) create mode 100644 vorlesungen/slides/4/dh.tex (limited to 'vorlesungen/slides/4') diff --git a/vorlesungen/slides/4/Makefile.inc b/vorlesungen/slides/4/Makefile.inc index 91767a9..4eae5b0 100644 --- a/vorlesungen/slides/4/Makefile.inc +++ b/vorlesungen/slides/4/Makefile.inc @@ -12,5 +12,6 @@ chapter4 = \ ../slides/4/fp.tex \ ../slides/4/division.tex \ ../slides/4/gauss.tex \ + ../slides/4/dh.tex \ ../slides/4/chapter.tex diff --git a/vorlesungen/slides/4/chapter.tex b/vorlesungen/slides/4/chapter.tex index 27884a1..38e90eb 100644 --- a/vorlesungen/slides/4/chapter.tex +++ b/vorlesungen/slides/4/chapter.tex @@ -10,3 +10,4 @@ \folie{4/fp.tex} \folie{4/division.tex} \folie{4/gauss.tex} +\folie{4/dh.tex} diff --git a/vorlesungen/slides/4/dh.tex b/vorlesungen/slides/4/dh.tex new file mode 100644 index 0000000..b0a88e5 --- /dev/null +++ b/vorlesungen/slides/4/dh.tex @@ -0,0 +1,62 @@ +% +% dh.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\begin{frame}[t] +\frametitle{Diffie-Hellmann Schlüsselaushandlung} + +\begin{center} +\definecolor{darkgreen}{rgb}{0,0.6,0} +\def\skala{0.95} +\begin{tikzpicture}[>=latex,thick,scale=\skala] +\def\l{2.5} +\fill[color=blue!20] (-7,-6.5) rectangle (7,0.5); +\fill[color=red!20] (-\l,-6.5) rectangle (\l,0.501); +\node[color=red] at (0,-1.5) {öffentliches Netzwerk}; +\node[color=blue] at (-7,0.2) [right] {privat}; +\node[color=blue] at (7,0.2) [left] {privat}; +\coordinate (A) at (-\l,-2.5); +\coordinate (C) at (\l,-5.0); +\coordinate (B) at (\l,-2.5); +\coordinate (D) at (-\l,-5.0); +\node at (0,0) {$p\in\mathbb{N},g\in\mathbb{F}_p$ aushandeln}; +\fill[color=white] (-\l,-0.7) circle[radius=0.3]; +\draw (-\l,-0.7) circle[radius=0.3]; +\fill[color=white] (\l,-0.7) circle[radius=0.3]; +\draw (\l,-0.7) circle[radius=0.3]; +\node at (-\l,-0.7) {$A$}; +\node at (\l,-0.7) {$B$}; +\uncover<2->{ + \node at (-\l,-1.5) [left] {$a$ auswählen\strut}; + \node at (-\l,-2.0) [left] {$x=g^a\in\mathbb{F}_p$\strut}; + \node at (\l,-1.5) [right] {$b$ auswählen\strut}; + \node at (\l,-2.0) [right] {$y=g^b\in\mathbb{F}_p$\strut}; +} +\draw[->] (-\l,-1) -- (-\l,-6); +\draw[->] (\l,-1) -- (\l,-6); +\uncover<3->{ + \draw[->] (A) -- (C); + \draw[->] (B) -- (D); + \fill (A) circle[radius=0.08]; + \fill (B) circle[radius=0.08]; + \node at ($0.8*(A)+0.2*(C)+(-0.4,0)$) [above right] {$x=g^a$}; + \node at ($0.8*(B)+0.2*(D)+(0.4,0)$) [above left] {$y=g^b$}; +} +\uncover<4->{ + \node at (-\l,-5.0) [left] {$s=g^{ab}=y^a\in\mathbb{F}_p$}; + \node at (-\l,-5.5) [left] {ausrechnen}; + \node at (\l,-5.0) [right] {$s=g^{ab}=x^b\in\mathbb{F}_p$}; + \node at (\l,-5.5) [right] {ausrechnen}; +} +\uncover<5->{ + \fill[rounded corners=0.3cm,color=darkgreen!20] + ({-\l-1.7},-7) rectangle ({\l+1.7},-6); + \draw[rounded corners=0.3cm] ({-\l-1.7},-7) rectangle ({\l+1.7},-6); + \node at (0,-6.5) {$A$ und $B$ haben den gemeinsamen Schlüssel $s$}; +} +\end{tikzpicture} + +\end{center} + +\end{frame} -- cgit v1.2.1 From ccac1b9539544b1f782ea8351dea314512d19c4b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sun, 7 Mar 2021 22:01:23 +0100 Subject: add new slides --- vorlesungen/slides/4/Makefile.inc | 2 ++ vorlesungen/slides/4/chapter.tex | 2 ++ vorlesungen/slides/4/divisionpoly.tex | 37 +++++++++++++++++++++++ vorlesungen/slides/4/polynomefp.tex | 57 +++++++++++++++++++++++++++++++++++ 4 files changed, 98 insertions(+) create mode 100644 vorlesungen/slides/4/divisionpoly.tex create mode 100644 vorlesungen/slides/4/polynomefp.tex (limited to 'vorlesungen/slides/4') diff --git a/vorlesungen/slides/4/Makefile.inc b/vorlesungen/slides/4/Makefile.inc index 4eae5b0..13de58c 100644 --- a/vorlesungen/slides/4/Makefile.inc +++ b/vorlesungen/slides/4/Makefile.inc @@ -13,5 +13,7 @@ chapter4 = \ ../slides/4/division.tex \ ../slides/4/gauss.tex \ ../slides/4/dh.tex \ + ../slides/4/divisionpoly.tex \ + ../slides/4/polynomefp.tex \ ../slides/4/chapter.tex diff --git a/vorlesungen/slides/4/chapter.tex b/vorlesungen/slides/4/chapter.tex index 38e90eb..84b1f8f 100644 --- a/vorlesungen/slides/4/chapter.tex +++ b/vorlesungen/slides/4/chapter.tex @@ -11,3 +11,5 @@ \folie{4/division.tex} \folie{4/gauss.tex} \folie{4/dh.tex} +\folie{4/divisionpoly.tex} +\folie{4/polynomefp.tex} diff --git a/vorlesungen/slides/4/divisionpoly.tex b/vorlesungen/slides/4/divisionpoly.tex new file mode 100644 index 0000000..5e71c95 --- /dev/null +++ b/vorlesungen/slides/4/divisionpoly.tex @@ -0,0 +1,37 @@ +% +% divisionpoly.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\begin{frame}[t] +\frametitle{Polynomdivision in $\mathbb{F}_3[X]$} +Rechenregeln in $\mathbb{F}_3$: $1+2=0$, $2\cdot 2 = 1$ +\[ +\arraycolsep=1.4pt +\begin{array}{rcrcrcrcrcrcrcrcrcrc} +\llap{$ ($}X^4&+&X^3&+& X^2&+& X&+&1\rlap{$)$}&\;\;:&(X^2&+&X&+&2)&=&\uncover<2->{X^2}&\uncover<5->{+&2=q}\\ +\uncover<3->{\llap{$-($}X^4&+&X^3&+&2X^2\rlap{$)$}}& & & & & & & & & & & & & & & \\ +\uncover<4->{ & & & &2X^2&+& X&+& 1} & & & & & & & & & & \\ +\uncover<6->{ & & & &\llap{$-($}2X^2&+&2X&+& 2\rlap{$)$}}& & & & & & & & & & \\ +\uncover<7->{ & & & & & &2X&+&2\rlap{$\mathstrut=r$}& & & & & & & & & &} +\end{array} +\] +\uncover<8->{% +Kontrolle: +\[ +\arraycolsep=1.4pt +\begin{array}{rclcrcr} +(\underbrace{X^2+2}_{\displaystyle=q}) +(X^2+X+2) + &=&\rlap{$\uncover<9->{X^4+X^3+2X^2}\uncover<10->{ + 2X^2+2X+2}$} +\\ +\uncover<11->{&=& X^4+X^3+X^2&+&2X&+&2} +\\ +\uncover<12->{& & &&\llap{$r=\mathstrut$}2X&+&2} +\\ +\uncover<13->{&=& X^4+X^3+X^2&+&1X&+&1} +\end{array} +\] +} + +\end{frame} diff --git a/vorlesungen/slides/4/polynomefp.tex b/vorlesungen/slides/4/polynomefp.tex new file mode 100644 index 0000000..fe514dd --- /dev/null +++ b/vorlesungen/slides/4/polynomefp.tex @@ -0,0 +1,57 @@ +% +% polynomefp.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\begin{frame}[t] +\frametitle{Polynome über $\mathbb{F}_p[X]$} +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\vspace{-15pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{block}{Polynomring} +$\mathbb{F}_p[X]$ sind Polynome +\[ +p(X) += +a_0+a_1X+\dots+a_nX^n +\] +mit $a_i\in\mathbb{F}_p$. +ObdA: $a_n=1$ + +\end{block} +\begin{block}{Irreduzible Polynome} +$m(X)$ ist irreduzibel, wenn es keine Faktorisierung +$m(X)=p(X)q(X)$ mit $p,q\in\mathbb{F}_p[X]$ gibt +\end{block} +\begin{block}{Rest modulo $m(X)$} +$X^{n+k}$ kann immer reduziert werden: +\[ +X^{n+k} = -(a_0+a_1X+\dots+a_{n-1}X^{n-1})X^k +\] +\end{block} +\end{column} +\begin{column}{0.48\textwidth} +\begin{block}{Körper $\mathbb{F}_p/(m(X))$} +Wenn $m(X)$ irreduzibel ist, dann ist +$\mathbb{F}_p[X]$ nullteilerfrei. +\medskip + +$a\in \mathbb{F}_p[X]$ mit $\deg a < \deg m$, dann ist +\begin{enumerate} +\item +$\operatorname{ggT}(a,m) = 1$ +\item +Es gibt $s,t\in\mathbb{F}_p[X]$ mit +\[ +s(X)m(X)+t(X)a(X) = 1 +\] +(aus dem euklidischen Algorithmus) +\item +$a^{-1} = t(X)$ +\end{enumerate} +\end{block} +\end{column} +\end{columns} +\end{frame} -- cgit v1.2.1 From f7987f342c3f9153a0f05c2f940f370aa61960ee Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sun, 7 Mar 2021 22:34:49 +0100 Subject: euklidslide --- vorlesungen/slides/4/Makefile.inc | 1 + vorlesungen/slides/4/chapter.tex | 1 + vorlesungen/slides/4/euklidpoly.tex | 47 +++++++++++++++++++++++++++++++++++++ 3 files changed, 49 insertions(+) create mode 100644 vorlesungen/slides/4/euklidpoly.tex (limited to 'vorlesungen/slides/4') diff --git a/vorlesungen/slides/4/Makefile.inc b/vorlesungen/slides/4/Makefile.inc index 13de58c..2329e4a 100644 --- a/vorlesungen/slides/4/Makefile.inc +++ b/vorlesungen/slides/4/Makefile.inc @@ -14,6 +14,7 @@ chapter4 = \ ../slides/4/gauss.tex \ ../slides/4/dh.tex \ ../slides/4/divisionpoly.tex \ + ../slides/4/euklidpoly.tex \ ../slides/4/polynomefp.tex \ ../slides/4/chapter.tex diff --git a/vorlesungen/slides/4/chapter.tex b/vorlesungen/slides/4/chapter.tex index 84b1f8f..830537e 100644 --- a/vorlesungen/slides/4/chapter.tex +++ b/vorlesungen/slides/4/chapter.tex @@ -12,4 +12,5 @@ \folie{4/gauss.tex} \folie{4/dh.tex} \folie{4/divisionpoly.tex} +\folie{4/euklidpoly.tex} \folie{4/polynomefp.tex} diff --git a/vorlesungen/slides/4/euklidpoly.tex b/vorlesungen/slides/4/euklidpoly.tex new file mode 100644 index 0000000..432b6b4 --- /dev/null +++ b/vorlesungen/slides/4/euklidpoly.tex @@ -0,0 +1,47 @@ +% +% euklidpoly.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Euklidischer Algorithmus in $\mathbb{F}_2[X]$} +Gegeben: $m(X)=X^4+X+1$, $b(X) = {\color{blue}X^2+1}$ +\\ +\uncover<2->{Berechne $s,t\in\mathbb{F}_2[X]$ derart, dass $sm+tb=1$} +\uncover<3->{% +\begin{center} +\begin{tabular}{|>{$}c<{$}|>{$}c<{$}>{$}c<{$}|>{$}c<{$}|>{$}c<{$}|>{$}c<{$}>{$}c<{$}|} +\hline +k& a_k& b_k& q_k&r_k& c_k& d_k\\ +\hline + & & & & & 1& 0\\ +0&X^4+X+1&{\color{blue}X^2+1}&\uncover<4->{X^2+1}&\uncover<4->{X}& 0& 1\\ +1&\uncover<5->{X^2+1 }&\uncover<5->{X}&\uncover<5->{X}&\uncover<5->{1}&\uncover<5->{1}&\uncover<5->{X^2+1}\\ +2&\uncover<6->{X }&\uncover<6->{1}&\uncover<6->{X}&\uncover<6->{0}&\uncover<6->{{\color{red}X}}&\uncover<6->{{\color{red}X^3+X+1}}\\ +3&\uncover<7->{1 }&\uncover<7->{0}&&&\uncover<7->{X^2+1}&\uncover<7->{X^4+X+1} \\ +\hline +\end{tabular} +\end{center}} +\ifthenelse{\boolean{presentation}}{ +\only<8->{% +\begin{block}{Kontrolle} +\vspace{-10pt} +\begin{align*} +{\color{red}X}\cdot (X^4+X+1) + ({\color{red}X^3+X+1})({\color{blue}X^2+1}) +&\uncover<9->{= +(X^5+X^2+X)}\\ +&\qquad \uncover<10->{+ (X^5+X^3+X^2+X^3+X+1)} +\\ +&\uncover<11->{=(X^5+X^2+X) + (X^5+X^2+X+1)} +\\ +&\uncover<12->{=1} +\end{align*} +\end{block}}}{} +\begin{block}{Rechenregeln in $\mathbb{F}_2$} +$1+1=0$, +$2=0$, $+1=-1$. +\end{block} + +\end{frame} -- cgit v1.2.1 From f2454006fa4e2a0b4093507300fab8a29e3b5901 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 8 Mar 2021 09:40:32 +0100 Subject: final preparation --- vorlesungen/slides/4/Makefile.inc | 2 + vorlesungen/slides/4/alpha.tex | 54 ++++++++++++++++++ vorlesungen/slides/4/chapter.tex | 2 + vorlesungen/slides/4/division.tex | 41 ++++++------- vorlesungen/slides/4/euklidbeispiel.tex | 66 +++++++++++++++------ vorlesungen/slides/4/euklidmatrix.tex | 39 +++++++++---- vorlesungen/slides/4/euklidtabelle.tex | 43 ++++++++------ vorlesungen/slides/4/fp.tex | 41 +++++++------ vorlesungen/slides/4/gauss.tex | 12 ++-- vorlesungen/slides/4/ggt.tex | 43 +++++++++----- vorlesungen/slides/4/polynomefp.tex | 21 ++++--- vorlesungen/slides/4/schieberegister.tex | 98 ++++++++++++++++++++++++++++++++ 12 files changed, 352 insertions(+), 110 deletions(-) create mode 100644 vorlesungen/slides/4/alpha.tex create mode 100644 vorlesungen/slides/4/schieberegister.tex (limited to 'vorlesungen/slides/4') diff --git a/vorlesungen/slides/4/Makefile.inc b/vorlesungen/slides/4/Makefile.inc index 2329e4a..ad1081e 100644 --- a/vorlesungen/slides/4/Makefile.inc +++ b/vorlesungen/slides/4/Makefile.inc @@ -16,5 +16,7 @@ chapter4 = \ ../slides/4/divisionpoly.tex \ ../slides/4/euklidpoly.tex \ ../slides/4/polynomefp.tex \ + ../slides/4/schieberegister.tex \ + ../slides/4/alpha.tex \ ../slides/4/chapter.tex diff --git a/vorlesungen/slides/4/alpha.tex b/vorlesungen/slides/4/alpha.tex new file mode 100644 index 0000000..3cd54c0 --- /dev/null +++ b/vorlesungen/slides/4/alpha.tex @@ -0,0 +1,54 @@ +% +% alpha.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\frametitle{Was ist $\alpha$?} +$m(X)$ ein irreduzibles Polynome in $\mathbb{F}_2[X]$ + +Beispiel: $m(X) = X^8{\color{red}\mathstrut+X^4+X^3+X^2+1}\in\mathbb{F}_2[X]$ +\begin{columns}[t] +\begin{column}{0.40\textwidth} +\uncover<2->{% +\begin{block}{Abstrakt} +$\alpha$ ist ein ``imaginäres'' +Objekt mit der Rechenregel $m(\alpha)=0$ +\begin{align*} +\alpha^8 &= {\color{red}\alpha^4+\alpha^3+\alpha^2+1}\\ +\uncover<3->{ +\alpha^9 &= \alpha^5+\alpha^4+\alpha^3+\alpha}\\ +\uncover<4->{ +\alpha^{10}&= \alpha^6+\alpha^5+\alpha^4+\alpha^2}\\ +\uncover<5->{ +\alpha^{11}&= \alpha^7+\alpha^6+\alpha^5+\alpha^3}\\ +\uncover<6->{ +\alpha &= \alpha^7+\alpha^3+\alpha^2+\alpha} +\\ +\end{align*} +\end{block}} +\end{column} +\begin{column}{0.54\textwidth} +\uncover<7->{% +\begin{block}{Matrix} +Eine konkretes Element in $M_n(\mathbb{F}_2)$ +\[ +\alpha += +\begin{pmatrix} +0& 0& 0& 0& 0& 0& 0& {\color{red}1}\\ +1& 0& 0& 0& 0& 0& 0& {\color{red}0}\\ +0& 1& 0& 0& 0& 0& 0& {\color{red}1}\\ +0& 0& 1& 0& 0& 0& 0& {\color{red}1}\\ +0& 0& 0& 1& 0& 0& 0& {\color{red}1}\\ +0& 0& 0& 0& 1& 0& 0& {\color{red}0}\\ +0& 0& 0& 0& 0& 1& 0& {\color{red}0}\\ +0& 0& 0& 0& 0& 0& 1& {\color{red}0} +\end{pmatrix} +\] +\end{block}} +\end{column} +\end{columns} + +\end{frame} diff --git a/vorlesungen/slides/4/chapter.tex b/vorlesungen/slides/4/chapter.tex index 830537e..a10712a 100644 --- a/vorlesungen/slides/4/chapter.tex +++ b/vorlesungen/slides/4/chapter.tex @@ -14,3 +14,5 @@ \folie{4/divisionpoly.tex} \folie{4/euklidpoly.tex} \folie{4/polynomefp.tex} +\folie{4/alpha.tex} +\folie{4/schieberegister.tex} diff --git a/vorlesungen/slides/4/division.tex b/vorlesungen/slides/4/division.tex index aeab1e3..846738f 100644 --- a/vorlesungen/slides/4/division.tex +++ b/vorlesungen/slides/4/division.tex @@ -13,26 +13,28 @@ \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 +\uncover<2->{&& a{\color{blue}b} &\equiv 1 \mod p} \\ -&\Leftrightarrow& a{\color{red}b}&=1 + {\color{red}n}p +\uncover<3->{&\Leftrightarrow& a{\color{blue}b}&=1 + {\color{blue}n}p} \\ -&&a{\color{red}b}-{\color{red}n}p&=1 +\uncover<4->{&&a{\color{blue}b}-{\color{blue}n}p&=1} \end{align*} -Wegen +\uncover<5->{Wegen $\operatorname{ggT}(a,p)=1$ gibt es $s$ und $t$ mit \[ -sa+tb=1 +{\color{red}s}a+{\color{red}t}p=1 \Rightarrow -{\color{red}b}=s,\; -{\color{red}n}=-t -\] +{\color{blue}b}={\color{red}s},\; +{\color{blue}n}=-{\color{red}t} +\]} +\uncover<6->{% $\Rightarrow$ Die Inverse kann mit dem euklidischen Algorithmus -berechnet werden +berechnet werden} \end{block} \end{column} \begin{column}{0.48\textwidth} +\uncover<7->{% \begin{block}{Beispiel in $\mathbb{F}_{1291}$} Finde $47^{-1}\in\mathbb{F}_{1291}$ %\vspace{-10pt} @@ -42,21 +44,22 @@ Finde $47^{-1}\in\mathbb{F}_{1291}$ 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\\ +0& 47&1291&\uncover<8->{ 0}& 0& 1\\ +1&\uncover<9->{ 1291& 47}&\uncover<11->{ 27}&\uncover<10->{ 1& 0}\\ +2&\uncover<12->{ 47& 22}&\uncover<14->{ 2}&\uncover<13->{ -27& 1}\\ +3&\uncover<15->{ 22& 3}&\uncover<17->{ 7}&\uncover<16->{ 55& -2}\\ +4&\uncover<18->{ 3& 1}&\uncover<20->{ 3}&\uncover<19->{{\color{red}-412}&{\color{red}15}}\\ +5&\uncover<21->{ 1& 0}& &\uncover<22->{ 1291& -47}\\ \hline \end{tabular} \end{center} +\uncover<23->{% \[ {\color{red}-412}\cdot 47 +{\color{red}15}\cdot 1291 = 1 -\;\Rightarrow\; -47^{-1}={\color{red}879} -\] -\end{block} +\uncover<24->{\;\Rightarrow\; +47^{-1}={\color{red}879}} +\]} +\end{block}} \end{column} \end{columns} \end{frame} diff --git a/vorlesungen/slides/4/euklidbeispiel.tex b/vorlesungen/slides/4/euklidbeispiel.tex index cbc3137..366a7a6 100644 --- a/vorlesungen/slides/4/euklidbeispiel.tex +++ b/vorlesungen/slides/4/euklidbeispiel.tex @@ -6,39 +6,73 @@ \bgroup \definecolor{darkgreen}{rgb}{0,0.6,0} \begin{frame}[t] -\frametitle{Beispiel} +\frametitle{Euklidischer Algorithmus: Beispiel} \setlength{\abovedisplayskip}{0pt} \setlength{\belowdisplayskip}{0pt} \vspace{-0pt} \begin{block}{Finde $\operatorname{ggT}(25,15)$} \vspace{-12pt} \begin{align*} -a_0&=25 & b_0 &= 15 &25&=15 \cdot {\color{red} 1} + 10 &q_0 &= {\color{red}1} & r_0 &= 10\\ -a_1&=15 & b_1 &= 10 &15&=10 \cdot {\color{darkgreen}1} + \phantom{0}5 &q_1 &= {\color{darkgreen}1} & r_1 &= \phantom{0}5 \\ -a_2&=10 & b_2 &= \phantom{0}5 &10&=\phantom{0}5 \cdot {\color{blue} 2} + \phantom{0}0 &q_2 &= {\color{blue}2} & r_2 &= \phantom{0}0 +a_0&=25 & b_0 &= 15 &\uncover<2->{25&=15 \cdot {\color{orange} 1} + 10 &q_0 &= {\color{orange}1} & r_0 &= 10}\\ +\uncover<3->{a_1&=15 & b_1 &= 10}&\uncover<4->{15&=10 \cdot {\color{darkgreen}1} + \phantom{0}5 &q_1 &= {\color{darkgreen}1} & r_1 &= \phantom{0}5}\\ +\uncover<5->{a_2&=10 & b_2 &= \phantom{0}5}&\uncover<6->{10&=\phantom{0}5 \cdot {\color{blue} 2} + \phantom{0}0 &q_2 &= {\color{blue}2} & r_2 &= \phantom{0}0 } \end{align*} \end{block} \vspace{-5pt} +\uncover<7->{% \begin{block}{Matrix-Operationen} \begin{align*} Q &= -Q({\color{blue}2}) Q({\color{darkgreen}1}) Q({\color{red}1}) +\uncover<9->{Q({\color{blue}2})} +\uncover<8->{Q({\color{darkgreen}1})} +Q({\color{orange}1}) = -\begin{pmatrix}0&1\\1&-{\color{blue}2}\end{pmatrix} -\begin{pmatrix}0&1\\1&-{\color{darkgreen}1}\end{pmatrix} -\begin{pmatrix}0&1\\1&-{\color{red}1}\end{pmatrix} -=\begin{pmatrix} --1&2\\3&-5 -\end{pmatrix} +\uncover<9->{ +\begin{pmatrix*}[r]0&1\\1&-{\color{blue}2}\end{pmatrix*} +} +\uncover<8->{ +\begin{pmatrix*}[r]0&1\\1&-{\color{darkgreen}1}\end{pmatrix*} +} +\begin{pmatrix*}[r]0&1\\1&-{\color{orange}1}\end{pmatrix*} += +\ifthenelse{\boolean{presentation}}{ +\only<7>{ +\begin{pmatrix*}[r]\phantom{-}0&1\\1&-1\end{pmatrix*} +} +\only<8>{ +\begin{pmatrix*}[r] +1&-1\\-1&2 +\end{pmatrix*} +} +}{} +\only<9->{ +\begin{pmatrix*}[r] +{\color{red}-1}&{\color{red}2}\\3&-5 +\end{pmatrix*}} \end{align*} -\end{block} +\end{block}} \vspace{-5pt} +\uncover<10->{% \begin{block}{Relationen ablesen} -\begin{align*} -\operatorname{ggT}({\usebeamercolor[fg]{title}25},{\usebeamercolor[fg]{title}15}) &= 5 = -1\cdot {\usebeamercolor[fg]{title}25} + 2\cdot {\usebeamercolor[fg]{title}15} \\ +\[ +\begin{pmatrix} +\operatorname{ggT}(a,b)\\0 +\end{pmatrix} += +Q +\begin{pmatrix}a\\b\end{pmatrix} +\uncover<11->{% +\quad +\Rightarrow\quad +\left\{ +\begin{aligned} +\operatorname{ggT}({\usebeamercolor[fg]{title}25},{\usebeamercolor[fg]{title}15}) &= 5 = +{\color{red}-1}\cdot {\usebeamercolor[fg]{title}25} + {\color{red}2}\cdot {\usebeamercolor[fg]{title}15} \\ 0 &= \phantom{5=-}3\cdot {\usebeamercolor[fg]{title}25} -5\cdot {\usebeamercolor[fg]{title}15} -\end{align*} -\end{block} +\end{aligned} +\right.} +\] +\end{block}} \end{frame} diff --git a/vorlesungen/slides/4/euklidmatrix.tex b/vorlesungen/slides/4/euklidmatrix.tex index 6ffa4c2..be5b3ca 100644 --- a/vorlesungen/slides/4/euklidmatrix.tex +++ b/vorlesungen/slides/4/euklidmatrix.tex @@ -14,17 +14,19 @@ \vspace{-10pt} \[ a_k = b_kq_k + r_k +\uncover<2->{ \;\Rightarrow\; \left\{ \begin{aligned} a_{k+1} &= b_k = \phantom{a_k-q_k}\llap{$-\mathstrut$}b_k \\ b_{k+1} &= \phantom{b_k}\llap{$r_k$} = a_k - q_kb_k \end{aligned} -\right. +\right.} \] \end{block} \end{column} \begin{column}{0.44\textwidth} +\uncover<3->{% \begin{block}{Matrixschreibweise} \vspace{-10pt} \begin{align*} @@ -37,23 +39,30 @@ b_{k+1} b_k\\r_k \end{pmatrix} = -\underbrace{\begin{pmatrix}0&1\\1&-q_k\end{pmatrix}}_{\displaystyle =Q(q_k)} +\uncover<4->{ +\underbrace{\begin{pmatrix} +\uncover<5->{0&1}\\ +\uncover<6->{1&-q_k} +\end{pmatrix}}_{\uncover<7->{\displaystyle =Q(q_k)}} +} \begin{pmatrix} a_k\\b_k \end{pmatrix} \end{align*} -\end{block} +\end{block}} \end{column} \end{columns} \vspace{-10pt} +\uncover<8->{% \begin{block}{Ende des Algorithmus} \vspace{-10pt} \begin{align*} +\uncover<9->{ \begin{pmatrix} a_{n+1}\\ b_{n+1}\\ \end{pmatrix} -&= +&=} \begin{pmatrix} r_{n-1}\\ r_{n} @@ -63,31 +72,37 @@ r_{n} \operatorname{ggT}(a,b) \\ 0 \end{pmatrix} +\uncover<11->{ = -\underbrace{Q(q_n) -\dots -Q(q_1) -Q(q_0)}_{\displaystyle =Q} +\underbrace{\uncover<15->{Q(q_n)} +\uncover<14->{\dots} +\uncover<13->{Q(q_1)} +\uncover<12->{Q(q_0)}}_{\displaystyle =Q}} +\uncover<10->{ \begin{pmatrix} a_0\\ b_0\end{pmatrix} +\uncover<6->{ = Q\begin{pmatrix}a\\b\end{pmatrix} +} +} \end{align*} -\end{block} +\end{block}} +\uncover<16->{% \begin{block}{Konsequenzen} \[ Q=\begin{pmatrix} q_{11}&q_{12}\\ -a_{21}&q_{22} +q_{21}&q_{22} \end{pmatrix} \quad\Rightarrow\quad \left\{ \quad \begin{aligned} -\operatorname{ggT}(a,b) &= q_{11}a + q_{12}b \\ +\operatorname{ggT}(a,b) &= q_{11}a + q_{12}b = {\color{red}s}a+{\color{red}t}b\\ 0 &= q_{21}a + q_{22}b \end{aligned} \right. \] -\end{block} +\end{block}} \end{frame} diff --git a/vorlesungen/slides/4/euklidtabelle.tex b/vorlesungen/slides/4/euklidtabelle.tex index 2d67823..3f1b8d7 100644 --- a/vorlesungen/slides/4/euklidtabelle.tex +++ b/vorlesungen/slides/4/euklidtabelle.tex @@ -8,22 +8,29 @@ \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$ +\uncover<2->{% \begin{block}{Multiplikation mit $Q(q_k)$} \vspace{-12pt} \begin{align*} Q(q_k) -%\begin{pmatrix} -%0&1\\1&-q_k -%\end{pmatrix} +\ifthenelse{\boolean{presentation}}{ +\only<-3>{ \begin{pmatrix} u&v\\c&d \end{pmatrix} -&= +=\begin{pmatrix} +0&1\\1&-q_k +\end{pmatrix} +}}{} +\begin{pmatrix} +u&v\\c&d +\end{pmatrix} +&\uncover<3->{= \begin{pmatrix} c&d\\ u-q_kc&v-q_kd -\end{pmatrix} -&&\Rightarrow& +\end{pmatrix}} +&&\uncover<5->{\Rightarrow& \begin{pmatrix} c_k&d_k\\c_{k+1}&d_{k+1} \end{pmatrix} @@ -34,31 +41,33 @@ Q(q_k) %\end{pmatrix} \begin{pmatrix} c_{k-1}&d_{k-1}\\c_{k}&d_{k} -\end{pmatrix} +\end{pmatrix}} \end{align*} -\end{block} +\end{block}} \vspace{-10pt} +\uncover<6->{% \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} \\ + 0 &\uncover<7->{q_0 }& 0 & 1 \\ + 1 &\uncover<9->{q_1 }&\uncover<8->{c_{-1} -q_0 \cdot c_0 &d_{-1} -q_0 \cdot d_0 }\\ + 2 &\uncover<11->{q_2 }&\uncover<10->{c_0 -q_1 \cdot c_1 &d_0 -q_1 \cdot d_1 }\\ +\vdots&\uncover<12->{\vdots}&\uncover<12->{\vdots &\vdots }\\ + n &\uncover<14->{q_n }&\uncover<13->{{\color{red}c_{n-2}-q_{n-1}\cdot c_{n-1}}&{\color{red}d_{n-2}-q_{n-1}\cdot d_{n-1}}}\\ +n+1& &\uncover<15->{c_{n-1}-q_{n} \cdot c_{n} &d_{n-1}-q_{n} \cdot d_{n} }\\ \hline \end{tabular} +\uncover<16->{ \Rightarrow \left\{ \begin{aligned} -\rlap{$c_{n}$}\phantom{c_{n+1}} a + \rlap{$d_n$}\phantom{d_{n+1}}b &= \operatorname{ggT}(a,b) +\rlap{${\color{red}c_{n}}$}\phantom{c_{n+1}} a + \rlap{${\color{red}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*} +\right.} +\end{equation*}} \end{frame} diff --git a/vorlesungen/slides/4/fp.tex b/vorlesungen/slides/4/fp.tex index caa6ceb..968b777 100644 --- a/vorlesungen/slides/4/fp.tex +++ b/vorlesungen/slides/4/fp.tex @@ -30,6 +30,7 @@ $\mathbb{Z}/n\mathbb{Z} =\{ \llbracket r\rrbracket\;|\; 0\le r < n \} \mathstrut$ ist ein Ring \end{block} +\uncover<2->{% \begin{block}{Nullteiler} Falls $n=n_1n_2$, dann sind $\llbracket n_1\rrbracket$ und $\llbracket n_2\rrbracket$ Nullteiler in $\mathbb{Z}/n\mathbb{Z}$: @@ -43,18 +44,22 @@ $\llbracket n_2\rrbracket$ Nullteiler in $\mathbb{Z}/n\mathbb{Z}$: = \llbracket 0 \rrbracket \] -\end{block} +\end{block}} \end{column} \begin{column}{0.48\textwidth} +\uncover<5->{% \begin{block}{Galois-Körper $\mathbb{F}_p\mathstrut$} $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}\mathstrut$ -\end{block} +\end{block}} +\uncover<4->{% \begin{block}{$n$ prim} Für $n=p$ prim ist $\mathbb{Z}/n\mathbb{Z}$ nullteilerfrei \medskip +\uncover<5->{ $\Rightarrow \quad \mathbb{F}_p$ ist ein Körper -\end{block} +} +\end{block}} \end{column} \end{columns} \vspace{-20pt} @@ -62,6 +67,7 @@ $\Rightarrow \quad \mathbb{F}_p$ ist ein Körper \begin{tikzpicture}[>=latex,thick,scale=0.45] \fill[color=white] (-12,0) circle[radius=0.1]; \fill[color=white] (12,0) circle[radius=0.1]; +\uncover<3->{ \begin{scope}[xshift=-8cm] \rot{2}{3} \rot{4}{3} @@ -106,14 +112,15 @@ $\Rightarrow \quad \mathbb{F}_p$ ist ein Körper \feld{4}{4}{4} \feld{4}{5}{2} \feld{5}{4}{2} \feld{5}{5}{1} -\end{scope} +\end{scope}} +\uncover<6->{ \begin{scope}[xshift=6cm] -\gruen{1}{1} -\gruen{2}{4} -\gruen{3}{5} -\gruen{4}{2} -\gruen{5}{3} -\gruen{6}{6} +\uncover<7->{ \gruen{1}{1} } +\uncover<8->{ \gruen{4}{2} } +\uncover<9->{ \gruen{5}{3} } +\uncover<10->{ \gruen{2}{4} } +\uncover<11->{ \gruen{3}{5} } +\uncover<12->{ \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}{ @@ -158,13 +165,13 @@ $\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} +\uncover<7->{ \inverse{1}{1} } +\uncover<8->{ \inverse{2}{4} } +\uncover<9->{ \inverse{3}{5} } +\uncover<10->{ \inverse{4}{2} } +\uncover<11->{ \inverse{5}{3} } +\uncover<12->{ \inverse{6}{6} } +\end{scope}} \end{tikzpicture} \end{center} \end{frame} diff --git a/vorlesungen/slides/4/gauss.tex b/vorlesungen/slides/4/gauss.tex index 960e8e1..23cdfee 100644 --- a/vorlesungen/slides/4/gauss.tex +++ b/vorlesungen/slides/4/gauss.tex @@ -95,7 +95,7 @@ z&=1 1 & 1 & 0 & 2 \\ \hline \end{tabular} -\uncover<4->{% +\uncover<5->{% \to \begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|} \hline @@ -104,7 +104,7 @@ z&=1 0 & 0 & 1 & 1 \\ \hline \end{tabular}} -\uncover<6->{% +\uncover<7->{% \to \begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|} \hline @@ -113,7 +113,7 @@ z&=1 0 & 0 & 1 & 1 \\ \hline \end{tabular}} -\uncover<8->{% +\uncover<9->{% \to \begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|} \hline @@ -125,14 +125,14 @@ z&=1 \] \end{minipage}}; \begin{scope}[yshift=0.2cm] -\uncover<3->{ +\uncover<4->{ \draw[color=red] (-5.6,0.3) circle[radius=0.2]; \draw[color=blue] (-5.4,-0.8) -- (-5.4,-0.2) arc (0:180:0.2) -- (-5.8,-0.8); } -\uncover<5->{ +\uncover<6->{ \draw[color=blue] (-1.45,0.5) -- (-1.45,-0.2) arc (180:360:0.2) -- (-1.05,0.5); } -\uncover<7->{ +\uncover<8->{ \draw[color=blue] (1.05,0.5) -- (1.05,0.2) arc (180:360:0.2) -- (1.45,0.5); } \end{scope} diff --git a/vorlesungen/slides/4/ggt.tex b/vorlesungen/slides/4/ggt.tex index e3c55e6..ef97182 100644 --- a/vorlesungen/slides/4/ggt.tex +++ b/vorlesungen/slides/4/ggt.tex @@ -15,16 +15,22 @@ Gegeben: $a,b\in\mathbb Z$ \\ Gesucht: grösster gemeinsamer Teiler $\operatorname{ggT}(a,b)$ \end{block} +\uncover<4->{% \begin{block}{Euklidischer Algorithmus} $a_0 = a$, $b_0=b$ \begin{align*} -a_0&=b_0q_0 + r_0 & a_1 &=b_0 & b_1&=r_0 \\ -a_1&=b_1q_1 + r_1 & a_2 &=b_1 & b_2&=r_1 \\ -a_2&=b_2q_2 + r_2 & a_3 &=b_2 & b_3&=r_2 \\ - &\;\vdots & & & & \\ -a_n&=b_nq_n + r_n & r_n &= 0 & r_{n-1}&=\operatorname{ggT}(a,b) +\uncover<5->{ +a_0&=b_0q_0 + r_0 & a_1 &=b_0 & b_1&=r_0}\\ +\uncover<6->{ +a_1&=b_1q_1 + r_1 & a_2 &=b_1 & b_2&=r_1}\\ +\uncover<7->{ +a_2&=b_2q_2 + r_2 & a_3 &=b_2 & b_3&=r_2}\\ +\uncover<8->{ + &\;\vdots & & & & }\\ +\uncover<9->{ +a_n&=b_nq_n + r_n & r_n &= 0 & r_{n-1}&=\operatorname{ggT}(a,b)} \end{align*} -\end{block} +\end{block}} \end{column} \begin{column}{0.48\textwidth} \begin{block}{$\operatorname{ggT}(15,25) = 5$} @@ -40,18 +46,25 @@ a_n&=b_nq_n + r_n & r_n &= 0 & r_{n-1}&=\operatorname{ggT}(a,b) \foreach \y in {0,...,2}{ \draw[line width=0.2pt] (-2,{\y*25}) -- (65,{\y*25}); } -\foreach \x in {0,5,...,120}{ - \draw[color=blue] ({\x+2},-2) -- ({\x+2-70},{-2+70}); - \node[color=blue] at ({0.5*\x-0.5},{0.5*\x-0.5}) [rotate=-45,above] {\tiny $\x$}; +\uncover<3->{ + \foreach \x in {0,5,...,120}{ + \draw[color=blue] ({\x+2},-2) -- ({\x+2-70},{-2+70}); + \node[color=blue] at ({0.5*\x-0.5},{0.5*\x-0.5}) + [rotate=-45,above] {\tiny $\x$}; + } } -\foreach \x in {0,...,4}{ - \foreach \y in {0,...,2}{ - \fill[color=red] ({\x*15},{\y*25}) circle[radius=0.8]; +\uncover<2->{ + \foreach \x in {0,...,4}{ + \foreach \y in {0,...,2}{ + \fill[color=red] ({\x*15},{\y*25}) circle[radius=0.8]; + } } } -\foreach \x in {0,5,...,60}{ - \fill[color=blue] (\x,0) circle[radius=0.5]; - \node at (\x,0) [below] {\tiny $\x$}; +\uncover<3->{ + \foreach \x in {0,5,...,60}{ + \fill[color=blue] (\x,0) circle[radius=0.5]; + \node at (\x,0) [below] {\tiny $\x$}; + } } \end{scope} \end{tikzpicture} diff --git a/vorlesungen/slides/4/polynomefp.tex b/vorlesungen/slides/4/polynomefp.tex index fe514dd..1db50e1 100644 --- a/vorlesungen/slides/4/polynomefp.tex +++ b/vorlesungen/slides/4/polynomefp.tex @@ -18,40 +18,45 @@ p(X) a_0+a_1X+\dots+a_nX^n \] mit $a_i\in\mathbb{F}_p$. -ObdA: $a_n=1$ +\uncover<2->{ObdA: $a_n=1$}% \end{block} +\uncover<3->{% \begin{block}{Irreduzible Polynome} $m(X)$ ist irreduzibel, wenn es keine Faktorisierung $m(X)=p(X)q(X)$ mit $p,q\in\mathbb{F}_p[X]$ gibt -\end{block} +\end{block}} +\uncover<4->{% \begin{block}{Rest modulo $m(X)$} $X^{n+k}$ kann immer reduziert werden: \[ X^{n+k} = -(a_0+a_1X+\dots+a_{n-1}X^{n-1})X^k \] -\end{block} +\end{block}} \end{column} \begin{column}{0.48\textwidth} +\uncover<5->{% \begin{block}{Körper $\mathbb{F}_p/(m(X))$} Wenn $m(X)$ irreduzibel ist, dann ist $\mathbb{F}_p[X]$ nullteilerfrei. \medskip -$a\in \mathbb{F}_p[X]$ mit $\deg a < \deg m$, dann ist +\uncover<6->{$a\in \mathbb{F}_p[X]$ mit $\deg a < \deg m$, dann ist} \begin{enumerate} -\item +\item<7-> $\operatorname{ggT}(a,m) = 1$ -\item +\item<8-> Es gibt $s,t\in\mathbb{F}_p[X]$ mit \[ s(X)m(X)+t(X)a(X) = 1 \] (aus dem euklidischen Algorithmus) -\item +\item<9-> $a^{-1} = t(X)$ \end{enumerate} -\end{block} +\uncover<9->{$\Rightarrow$ $\mathbb{F}_p[X]/(m(X))$ ist ein Körper +mit genau $p^n$ Elementen} +\end{block}} \end{column} \end{columns} \end{frame} diff --git a/vorlesungen/slides/4/schieberegister.tex b/vorlesungen/slides/4/schieberegister.tex new file mode 100644 index 0000000..6914c79 --- /dev/null +++ b/vorlesungen/slides/4/schieberegister.tex @@ -0,0 +1,98 @@ +% +% schieberegister.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\def\ds{0.7} +\def\punkt#1#2{({(#1)*\ds},{(#2)*\ds})} +\def\rahmen{ + \draw ({-0.5*\ds},{-0.5*\ds}) rectangle ({7.5*\ds},{0.5*\ds}); + \foreach \x in {0.5,1.5,...,6.5}{ + \draw ({\x*\ds},{-0.5*\ds}) rectangle ({\x*\ds},{0.5*\ds}); + } +} +\def\polynom#1#2#3#4#5#6#7#8{ + \node at \punkt{0}{0} {$#1$}; + \node at \punkt{1}{0} {$#2$}; + \node at \punkt{2}{0} {$#3$}; + \node at \punkt{3}{0} {$#4$}; + \node at \punkt{4}{0} {$#5$}; + \node at \punkt{5}{0} {$#6$}; + \node at \punkt{6}{0} {$#7$}; + \node at \punkt{7}{0} {$#8$}; +} +\begin{frame}[t] +\frametitle{Schieberegister} +Rechnen mit Polynomen in $\mathbb{F}_2(\alpha)$ ist speziell einfach +\\ +Minimalpolynom von $\alpha$: $m(X) = X^8 + X^4+X^3+X+1$ (aus dem AES Standard) + +\begin{center} +\begin{tikzpicture}[>=latex,thick] + +\uncover<2->{ +\begin{scope} + \rahmen + \node at \punkt{0}{1} {$X^7$\strut}; + \node at \punkt{2.5}{1}{$+$\strut}; + \node at \punkt{3}{1} {$X^4$\strut}; + \node at \punkt{4.5}{1}{$+$\strut}; + \node at \punkt{5}{1} {$X^2$\strut}; + \node at \punkt{6.5}{1}{$+$\strut}; + \node at \punkt{7}{1} {$1$\strut}; + \polynom10010101 +\end{scope}} + +\uncover<3->{ + \draw[->] ({7.7*\ds},-0.2) to[out=-45,in=45] ({7.7*\ds},-1.8); + \node at ({8*\ds},-1) [right] {$\mathstrut\cdot X = \text{Shift}$}; +} + +\uncover<3->{ + \begin{scope}[yshift=-2cm] + \uncover<4->{ + \rahmen + \polynom00101010 + } + \node at \punkt{2}{1} {$X^5$\strut}; + \node at \punkt{3.5}{1}{$+$\strut}; + \node at \punkt{4}{1} {$X^3$\strut}; + \node at \punkt{5.5}{1}{$+$\strut}; + \node at \punkt{6}{1} {$X$\strut}; + \begin{scope}[xshift=0.4cm] + \node at \punkt{-1}{1} [left] + {$\uncover<5->{X^4+X^3+X+1=}X^8$\strut}; + \end{scope} + \node at \punkt{-1}{0} {$1$\strut}; + \end{scope} +} + +\uncover<6->{ + {\color<8->{red} + \draw[->] (-3,-1.5) to[out=-90,in=180] (-0.5,-2.7); + } + \begin{scope}[yshift=-2.7cm] + \rahmen + \polynom00011011 + \end{scope} +} + +\uncover<7->{ + \node at ({3.5*\ds},-3.45) {$\|$}; + + \begin{scope}[yshift=-4.2cm] + \rahmen + \polynom00110111 + \end{scope} +} + +\uncover<8->{ + \node[color=red] at (-3.5,-2.7) {Feedback}; +} + +\end{tikzpicture} +\end{center} + +\end{frame} +\egroup -- cgit v1.2.1 From 18c273cb55ea5f54b125d8d6e3032b25cf56f8f3 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 8 Mar 2021 10:27:04 +0100 Subject: besser strukturierung --- vorlesungen/slides/4/schieberegister.tex | 38 +++++++++++++++++++++++++------- 1 file changed, 30 insertions(+), 8 deletions(-) (limited to 'vorlesungen/slides/4') diff --git a/vorlesungen/slides/4/schieberegister.tex b/vorlesungen/slides/4/schieberegister.tex index 6914c79..f349337 100644 --- a/vorlesungen/slides/4/schieberegister.tex +++ b/vorlesungen/slides/4/schieberegister.tex @@ -5,6 +5,7 @@ % \bgroup \def\ds{0.7} +\definecolor{darkgreen}{rgb}{0,0.6,0} \def\punkt#1#2{({(#1)*\ds},{(#2)*\ds})} \def\rahmen{ \draw ({-0.5*\ds},{-0.5*\ds}) rectangle ({7.5*\ds},{0.5*\ds}); @@ -23,17 +24,25 @@ \node at \punkt{7}{0} {$#8$}; } \begin{frame}[t] -\frametitle{Schieberegister} -Rechnen mit Polynomen in $\mathbb{F}_2(\alpha)$ ist speziell einfach +\frametitle{Implementation der Multiplikation in $\mathbb{F}_2(\alpha)$\uncover<10->{: Schieberegister}} +Rechnen in $\mathbb{F}_2[X]$\only<5->{ und $\mathbb{F}_2(\alpha)$} +ist speziell einfach \\ -Minimalpolynom von $\alpha$: $m(X) = X^8 + X^4+X^3+X+1$ (aus dem AES Standard) +Minimalpolynom von $\alpha$: ${\color{darkgreen}m(X) = X^8 + X^4+X^3+X+1}$ +(aus dem AES Standard) \begin{center} \begin{tikzpicture}[>=latex,thick] +\uncover<4->{ + \fill[color=blue!20] + \punkt{-0.5}{-0.5} rectangle \punkt{7.5}{0.5}; +} + \uncover<2->{ \begin{scope} \rahmen + \node at \punkt{-0.5}{1} [left] {$p(X)=\mathstrut$}; \node at \punkt{0}{1} {$X^7$\strut}; \node at \punkt{2.5}{1}{$+$\strut}; \node at \punkt{3}{1} {$X^4$\strut}; @@ -48,10 +57,20 @@ Minimalpolynom von $\alpha$: $m(X) = X^8 + X^4+X^3+X+1$ (aus dem AES Standard) \draw[->] ({7.7*\ds},-0.2) to[out=-45,in=45] ({7.7*\ds},-1.8); \node at ({8*\ds},-1) [right] {$\mathstrut\cdot X = \text{Shift}$}; } +\uncover<4->{ + \foreach \x in {0,...,7}{ + \draw[->,color=blue!40] + ({\x*\ds},{-0.6*\ds}) -- ({(\x-1)*\ds},{-2+0.6*\ds}); + } +} + +\fill[color=white] (-4.65,0) circle[radius=0.01]; \uncover<3->{ \begin{scope}[yshift=-2cm] \uncover<4->{ + \fill[color=blue!20] + \punkt{-1.5}{-0.5} rectangle \punkt{6.5}{0.5}; \rahmen \polynom00101010 } @@ -62,7 +81,7 @@ Minimalpolynom von $\alpha$: $m(X) = X^8 + X^4+X^3+X+1$ (aus dem AES Standard) \node at \punkt{6}{1} {$X$\strut}; \begin{scope}[xshift=0.4cm] \node at \punkt{-1}{1} [left] - {$\uncover<5->{X^4+X^3+X+1=}X^8$\strut}; + {$\uncover<5->{{\color{darkgreen}\alpha^4+\alpha^3+\alpha+1=\alpha^8}}\only<-4>{X^8}$\strut}; \end{scope} \node at \punkt{-1}{0} {$1$\strut}; \end{scope} @@ -70,11 +89,13 @@ Minimalpolynom von $\alpha$: $m(X) = X^8 + X^4+X^3+X+1$ (aus dem AES Standard) \uncover<6->{ {\color<8->{red} - \draw[->] (-3,-1.5) to[out=-90,in=180] (-0.5,-2.7); + \draw[->] (-2.5,-1.5) to[out=-90,in=180] (-0.5,-2.7); } \begin{scope}[yshift=-2.7cm] \rahmen - \polynom00011011 + {\color{darkgreen} + \polynom00011011 + } \end{scope} } @@ -83,12 +104,13 @@ Minimalpolynom von $\alpha$: $m(X) = X^8 + X^4+X^3+X+1$ (aus dem AES Standard) \begin{scope}[yshift=-4.2cm] \rahmen - \polynom00110111 + \polynom00110001 + \node at \punkt{7.6}{0} [right] {$\mathstrut=\alpha\cdot p(\alpha)$}; \end{scope} } \uncover<8->{ - \node[color=red] at (-3.5,-2.7) {Feedback}; + \node[color=red] at (-3.0,-2.5) {Feedback}; } \end{tikzpicture} -- cgit v1.2.1