diff options
Diffstat (limited to '')
| -rw-r--r-- | vorlesungen/slides/4/Makefile.inc | 22 | ||||
| -rw-r--r-- | vorlesungen/slides/4/alpha.tex | 54 | ||||
| -rw-r--r-- | vorlesungen/slides/4/chapter.tex | 18 | ||||
| -rw-r--r-- | vorlesungen/slides/4/dh.tex | 62 | ||||
| -rw-r--r-- | vorlesungen/slides/4/division.tex | 65 | ||||
| -rw-r--r-- | vorlesungen/slides/4/divisionpoly.tex | 37 | ||||
| -rw-r--r-- | vorlesungen/slides/4/euklidbeispiel.tex | 78 | ||||
| -rw-r--r-- | vorlesungen/slides/4/euklidmatrix.tex | 108 | ||||
| -rw-r--r-- | vorlesungen/slides/4/euklidpoly.tex | 47 | ||||
| -rw-r--r-- | vorlesungen/slides/4/euklidtabelle.tex | 73 | ||||
| -rw-r--r-- | vorlesungen/slides/4/fp.tex | 178 | ||||
| -rw-r--r-- | vorlesungen/slides/4/gauss.tex | 143 | ||||
| -rw-r--r-- | vorlesungen/slides/4/ggt.tex | 75 | ||||
| -rw-r--r-- | vorlesungen/slides/4/polynomefp.tex | 62 | ||||
| -rw-r--r-- | vorlesungen/slides/4/schieberegister.tex | 120 |
15 files changed, 1142 insertions, 0 deletions
diff --git a/vorlesungen/slides/4/Makefile.inc b/vorlesungen/slides/4/Makefile.inc new file mode 100644 index 0000000..ad1081e --- /dev/null +++ b/vorlesungen/slides/4/Makefile.inc @@ -0,0 +1,22 @@ + +# +# Makefile.inc -- additional depencencies +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +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/gauss.tex \ + ../slides/4/dh.tex \ + ../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 new file mode 100644 index 0000000..a10712a --- /dev/null +++ b/vorlesungen/slides/4/chapter.tex @@ -0,0 +1,18 @@ +% +% chapter.tex +% +% (c) 2021 Prof Dr Andreas Müller, Hochschule Rapperswi +% +\folie{4/ggt.tex} +\folie{4/euklidmatrix.tex} +\folie{4/euklidbeispiel.tex} +\folie{4/euklidtabelle.tex} +\folie{4/fp.tex} +\folie{4/division.tex} +\folie{4/gauss.tex} +\folie{4/dh.tex} +\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/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} diff --git a/vorlesungen/slides/4/division.tex b/vorlesungen/slides/4/division.tex new file mode 100644 index 0000000..846738f --- /dev/null +++ b/vorlesungen/slides/4/division.tex @@ -0,0 +1,65 @@ +% +% 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*} +\uncover<2->{&& a{\color{blue}b} &\equiv 1 \mod p} +\\ +\uncover<3->{&\Leftrightarrow& a{\color{blue}b}&=1 + {\color{blue}n}p} +\\ +\uncover<4->{&&a{\color{blue}b}-{\color{blue}n}p&=1} +\end{align*} +\uncover<5->{Wegen +$\operatorname{ggT}(a,p)=1$ gibt es +$s$ und $t$ mit +\[ +{\color{red}s}a+{\color{red}t}p=1 +\Rightarrow +{\color{blue}b}={\color{red}s},\; +{\color{blue}n}=-{\color{red}t} +\]} +\uncover<6->{% +$\Rightarrow$ Die Inverse kann mit dem euklidischen Algorithmus +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} +\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&\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 +\uncover<24->{\;\Rightarrow\; +47^{-1}={\color{red}879}} +\]} +\end{block}} +\end{column} +\end{columns} +\end{frame} 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/euklidbeispiel.tex b/vorlesungen/slides/4/euklidbeispiel.tex new file mode 100644 index 0000000..366a7a6 --- /dev/null +++ b/vorlesungen/slides/4/euklidbeispiel.tex @@ -0,0 +1,78 @@ +% +% euklidmatrix.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostscheizer Fachhochschule +% +\bgroup +\definecolor{darkgreen}{rgb}{0,0.6,0} +\begin{frame}[t] +\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 &\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 +&= +\uncover<9->{Q({\color{blue}2})} +\uncover<8->{Q({\color{darkgreen}1})} +Q({\color{orange}1}) += +\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}} +\vspace{-5pt} +\uncover<10->{% +\begin{block}{Relationen ablesen} +\[ +\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{aligned} +\right.} +\] +\end{block}} + +\end{frame} diff --git a/vorlesungen/slides/4/euklidmatrix.tex b/vorlesungen/slides/4/euklidmatrix.tex new file mode 100644 index 0000000..be5b3ca --- /dev/null +++ b/vorlesungen/slides/4/euklidmatrix.tex @@ -0,0 +1,108 @@ +% +% euklidmatrix.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostscheizer Fachhochschule +% +\begin{frame}[t] +\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 +\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.} +\] +\end{block} +\end{column} +\begin{column}{0.44\textwidth} +\uncover<3->{% +\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} += +\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{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} +\end{pmatrix} += +\begin{pmatrix} +\operatorname{ggT}(a,b) \\ +0 +\end{pmatrix} +\uncover<11->{ += +\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}} +\uncover<16->{% +\begin{block}{Konsequenzen} +\[ +Q=\begin{pmatrix} +q_{11}&q_{12}\\ +q_{21}&q_{22} +\end{pmatrix} +\quad\Rightarrow\quad +\left\{ +\quad +\begin{aligned} +\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{frame} 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} diff --git a/vorlesungen/slides/4/euklidtabelle.tex b/vorlesungen/slides/4/euklidtabelle.tex new file mode 100644 index 0000000..3f1b8d7 --- /dev/null +++ b/vorlesungen/slides/4/euklidtabelle.tex @@ -0,0 +1,73 @@ +% +% 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$ +\uncover<2->{% +\begin{block}{Multiplikation mit $Q(q_k)$} +\vspace{-12pt} +\begin{align*} +Q(q_k) +\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}} +&&\uncover<5->{\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} +\uncover<6->{% +\begin{equation*} +\begin{tabular}{|>{\tiny$}r<{$}|>{$}c<{$}|>{$}c<{$}>{$}c<{$}|} +\hline +k &q_k & c_k & d_k \\ +\hline +-1 & & 1 & 0 \\ + 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{${\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*}} +\end{frame} diff --git a/vorlesungen/slides/4/fp.tex b/vorlesungen/slides/4/fp.tex new file mode 100644 index 0000000..968b777 --- /dev/null +++ b/vorlesungen/slides/4/fp.tex @@ -0,0 +1,178 @@ +% +% 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}); +} +\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} +\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} +\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}$: +\[ +\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} +\uncover<5->{% +\begin{block}{Galois-Körper $\mathbb{F}_p\mathstrut$} +$\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}\mathstrut$ +\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{column} +\end{columns} +\vspace{-20pt} +\begin{center} +\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} +\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}} +\uncover<6->{ +\begin{scope}[xshift=6cm] +\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}{ + \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} +\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} +\egroup diff --git a/vorlesungen/slides/4/gauss.tex b/vorlesungen/slides/4/gauss.tex new file mode 100644 index 0000000..23cdfee --- /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<5->{% +\to +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|} +\hline + 1 & 1 & 2 & 1 \\ + 0 & 1 & 0 & 0 \\ + 0 & 0 & 1 & 1 \\ +\hline +\end{tabular}} +\uncover<7->{% +\to +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|>{$}c<{$}|} +\hline + 1 & 1 & 0 & 2 \\ + 0 & 1 & 0 & 0 \\ + 0 & 0 & 1 & 1 \\ +\hline +\end{tabular}} +\uncover<9->{% +\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<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<6->{ +\draw[color=blue] (-1.45,0.5) -- (-1.45,-0.2) arc (180:360:0.2) -- (-1.05,0.5); +} +\uncover<8->{ +\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 diff --git a/vorlesungen/slides/4/ggt.tex b/vorlesungen/slides/4/ggt.tex new file mode 100644 index 0000000..ef97182 --- /dev/null +++ b/vorlesungen/slides/4/ggt.tex @@ -0,0 +1,75 @@ +% +% 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} +\uncover<4->{% +\begin{block}{Euklidischer Algorithmus} +$a_0 = a$, $b_0=b$ +\begin{align*} +\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{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}); +} +\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$}; + } +} +\uncover<2->{ + \foreach \x in {0,...,4}{ + \foreach \y in {0,...,2}{ + \fill[color=red] ({\x*15},{\y*25}) circle[radius=0.8]; + } + } +} +\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} +\end{center} +\end{block} +\end{column} +\end{columns} +\end{frame} diff --git a/vorlesungen/slides/4/polynomefp.tex b/vorlesungen/slides/4/polynomefp.tex new file mode 100644 index 0000000..1db50e1 --- /dev/null +++ b/vorlesungen/slides/4/polynomefp.tex @@ -0,0 +1,62 @@ +% +% 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$. +\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}} +\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{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 + +\uncover<6->{$a\in \mathbb{F}_p[X]$ mit $\deg a < \deg m$, dann ist} +\begin{enumerate} +\item<7-> +$\operatorname{ggT}(a,m) = 1$ +\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<9-> +$a^{-1} = t(X)$ +\end{enumerate} +\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..f349337 --- /dev/null +++ b/vorlesungen/slides/4/schieberegister.tex @@ -0,0 +1,120 @@ +% +% schieberegister.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\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}); + \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{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$: ${\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}; + \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<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 + } + \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->{{\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} +} + +\uncover<6->{ + {\color<8->{red} + \draw[->] (-2.5,-1.5) to[out=-90,in=180] (-0.5,-2.7); + } + \begin{scope}[yshift=-2.7cm] + \rahmen + {\color{darkgreen} + \polynom00011011 + } + \end{scope} +} + +\uncover<7->{ + \node at ({3.5*\ds},-3.45) {$\|$}; + + \begin{scope}[yshift=-4.2cm] + \rahmen + \polynom00110001 + \node at \punkt{7.6}{0} [right] {$\mathstrut=\alpha\cdot p(\alpha)$}; + \end{scope} +} + +\uncover<8->{ + \node[color=red] at (-3.0,-2.5) {Feedback}; +} + +\end{tikzpicture} +\end{center} + +\end{frame} +\egroup |