diff options
| -rw-r--r-- | buch/chapters/references.bib | 10 | ||||
| -rw-r--r-- | vorlesungen/00_template/Makefile | 9 | ||||
| -rw-r--r-- | vorlesungen/03_endlichekoerper/Makefile | 11 | ||||
| -rw-r--r-- | vorlesungen/03_endlichekoerper/MathSem-03-endlichekoerper.tex | 4 | ||||
| -rw-r--r-- | vorlesungen/03_endlichekoerper/dh.jpg | bin | 0 -> 154552 bytes | |||
| -rw-r--r-- | vorlesungen/03_endlichekoerper/slides.tex | 16 | ||||
| -rw-r--r-- | vorlesungen/slides/4/Makefile.inc | 2 | ||||
| -rw-r--r-- | vorlesungen/slides/4/alpha.tex | 54 | ||||
| -rw-r--r-- | vorlesungen/slides/4/chapter.tex | 2 | ||||
| -rw-r--r-- | vorlesungen/slides/4/division.tex | 41 | ||||
| -rw-r--r-- | vorlesungen/slides/4/euklidbeispiel.tex | 66 | ||||
| -rw-r--r-- | vorlesungen/slides/4/euklidmatrix.tex | 39 | ||||
| -rw-r--r-- | vorlesungen/slides/4/euklidtabelle.tex | 43 | ||||
| -rw-r--r-- | vorlesungen/slides/4/fp.tex | 41 | ||||
| -rw-r--r-- | vorlesungen/slides/4/gauss.tex | 12 | ||||
| -rw-r--r-- | vorlesungen/slides/4/ggt.tex | 43 | ||||
| -rw-r--r-- | vorlesungen/slides/4/polynomefp.tex | 21 | ||||
| -rw-r--r-- | vorlesungen/slides/4/schieberegister.tex | 98 | ||||
| -rw-r--r-- | vorlesungen/slides/test.tex | 9 |
19 files changed, 396 insertions, 125 deletions
diff --git a/buch/chapters/references.bib b/buch/chapters/references.bib index b58af7d..2eed953 100644 --- a/buch/chapters/references.bib +++ b/buch/chapters/references.bib @@ -82,7 +82,6 @@ abstract = "In this paper, we present Google, a prototype of a large-scale searc @online{buch:lissajous, title = {Makeing Shapes with PSLab Oscilloscope}, author = {CloudyPadmal}, - year = 2018, url = {https://blog.fossasia.org/making-shapes-with-pslab-oscilloscope/}, DAY = 7, month = 3, @@ -115,3 +114,12 @@ abstract = "In this paper, we present Google, a prototype of a large-scale searc author = { Hans-Dieter Ebbinghaus et al }, isbn = { 3-540-12666-X } } + +@online{buch:primitivepolynomiallist, + title = {Primitive Polynomial List}, + url = {https://www.partow.net/programming/polynomials/index.html}, + day = 8, + month = 3, + year = 2021 +} + diff --git a/vorlesungen/00_template/Makefile b/vorlesungen/00_template/Makefile index fe6bbb7..14c254d 100644 --- a/vorlesungen/00_template/Makefile +++ b/vorlesungen/00_template/Makefile @@ -15,7 +15,7 @@ MathSem-yyy-xxx.pdf: MathSem-yyy-xxx.tex $(SOURCES) xxx-handout.pdf: xxx-handout.tex $(SOURCES) pdflatex xxx-handout.tex -thumbnail: thumbnail.jpg +thumbnail: thumbnail.jpg # fix1.jpg thumbnail.pdf: MathSem-yyy-xxx.pdf pdfjam --outfile thumbnail.pdf --papersize '{16cm,9cm}' \ @@ -24,3 +24,10 @@ thumbnail.jpg: thumbnail.pdf convert -density 300 thumbnail.pdf \ -resize 1920x1080 -units PixelsPerInch thumbnail.jpg +fix1.pdf: MathSem-yyy-xxx.pdf + pdfjam --outfile fix1.pdf --papersize '{16cm,9cm}' \ + MathSem-yyy-xxx.pdf 1 +fix1.jpg: fix1.pdf + convert -density 300 fix1.pdf \ + -resize 1920x1080 -units PixelsPerInch fix1.jpg + diff --git a/vorlesungen/03_endlichekoerper/Makefile b/vorlesungen/03_endlichekoerper/Makefile index 316e749..cc2ded5 100644 --- a/vorlesungen/03_endlichekoerper/Makefile +++ b/vorlesungen/03_endlichekoerper/Makefile @@ -15,7 +15,7 @@ MathSem-03-endlichekoerper.pdf: MathSem-03-endlichekoerper.tex $(SOURCES) endlichekoerper-handout.pdf: endlichekoerper-handout.tex $(SOURCES) pdflatex endlichekoerper-handout.tex -thumbnail: thumbnail.jpg +thumbnail: thumbnail.jpg fix1.jpg thumbnail.pdf: MathSem-03-endlichekoerper.pdf pdfjam --outfile thumbnail.pdf --papersize '{16cm,9cm}' \ @@ -24,3 +24,12 @@ thumbnail.jpg: thumbnail.pdf convert -density 300 thumbnail.pdf \ -resize 1920x1080 -units PixelsPerInch thumbnail.jpg +fix1.pdf: MathSem-03-endlichekoerper.pdf + pdfjam --outfile fix1.pdf --papersize '{16cm,9cm}' \ + MathSem-03-endlichekoerper.pdf 76 +fix1.jpg: fix1.pdf + convert -density 300 fix1.pdf \ + -resize 1920x1080 -units PixelsPerInch fix1.jpg +dh.jpg: fix1.jpg + convert -extract 1598x860+256+186 fix1.jpg dh.jpg + diff --git a/vorlesungen/03_endlichekoerper/MathSem-03-endlichekoerper.tex b/vorlesungen/03_endlichekoerper/MathSem-03-endlichekoerper.tex index 31229d7..9ff79e6 100644 --- a/vorlesungen/03_endlichekoerper/MathSem-03-endlichekoerper.tex +++ b/vorlesungen/03_endlichekoerper/MathSem-03-endlichekoerper.tex @@ -9,6 +9,10 @@ \begin{document} \begin{frame} \titlepage +\vspace{-1.6cm} +\begin{center} +\includegraphics[width=11cm]{dh.jpg} +\end{center} \end{frame} \input{slides.tex} \end{document} diff --git a/vorlesungen/03_endlichekoerper/dh.jpg b/vorlesungen/03_endlichekoerper/dh.jpg Binary files differnew file mode 100644 index 0000000..8bd07c3 --- /dev/null +++ b/vorlesungen/03_endlichekoerper/dh.jpg diff --git a/vorlesungen/03_endlichekoerper/slides.tex b/vorlesungen/03_endlichekoerper/slides.tex index 19a9ab0..2111463 100644 --- a/vorlesungen/03_endlichekoerper/slides.tex +++ b/vorlesungen/03_endlichekoerper/slides.tex @@ -10,19 +10,19 @@ \section{Die Galois-Körper $\mathbb{F}_p$} \folie{4/fp.tex} \folie{4/division.tex} -% XXX \folie{4/gauss.tex} -% XXX \folie{4/dh.tex} -% XXX ? \folie{4/polynomefp.tex} +\folie{4/gauss.tex} +\folie{4/dh.tex} % XXX \folie{4/frobenius.tex} \section{Rechnen in $\mathbb{F}_p(\alpha)$} -% XXX \folie{4/ggtpoly.tex} -% XXX \folie{4/divisionpoly.tex} -% XXX \folie{4/euklidpoly.tex} +\folie{4/divisionpoly.tex} +\folie{4/euklidpoly.tex} +\folie{4/polynomefp.tex} +\folie{4/alpha.tex} -\section{$\mathbb{F}_2(\alpha)$} +\section{Spezialfall $\mathbb{F}_2(\alpha)$} % XXX \folie{4/f2.tex} -% XXX \folie{4/schieberegister.tex} +\folie{4/schieberegister.tex} \section{Anwendung: elliptische Kurven} % XXX Idee der elliptischen Kurve 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 diff --git a/vorlesungen/slides/test.tex b/vorlesungen/slides/test.tex index b7b696a..659be92 100644 --- a/vorlesungen/slides/test.tex +++ b/vorlesungen/slides/test.tex @@ -26,8 +26,8 @@ %\folie{4/ggt.tex} %\folie{4/euklidmatrix.tex} -\folie{4/euklidbeispiel.tex} -\folie{4/euklidtabelle.tex} +%\folie{4/euklidbeispiel.tex} +%\folie{4/euklidtabelle.tex} %\folie{4/fp.tex} %\folie{4/division.tex} %\folie{4/gauss.tex} @@ -35,11 +35,12 @@ % XXX \folie{4/frobenius.tex} %\folie{4/divisionpoly.tex} -\folie{4/euklidpoly.tex} +%\folie{4/euklidpoly.tex} %\folie{4/polynomefp.tex} +%\folie{4/alpha.tex} % XXX \folie{4/f2.tex} -% XXX \folie{4/schieberegister.tex} +\folie{4/schieberegister.tex} % XXX Idee der elliptischen Kurve % XXX \folie{4/ecidee.tex} |
