aboutsummaryrefslogtreecommitdiffstats
path: root/vorlesungen/slides/4
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--vorlesungen/slides/4/Makefile.inc2
-rw-r--r--vorlesungen/slides/4/alpha.tex54
-rw-r--r--vorlesungen/slides/4/chapter.tex2
-rw-r--r--vorlesungen/slides/4/division.tex41
-rw-r--r--vorlesungen/slides/4/euklidbeispiel.tex66
-rw-r--r--vorlesungen/slides/4/euklidmatrix.tex39
-rw-r--r--vorlesungen/slides/4/euklidtabelle.tex43
-rw-r--r--vorlesungen/slides/4/fp.tex41
-rw-r--r--vorlesungen/slides/4/gauss.tex12
-rw-r--r--vorlesungen/slides/4/ggt.tex43
-rw-r--r--vorlesungen/slides/4/polynomefp.tex21
-rw-r--r--vorlesungen/slides/4/schieberegister.tex98
12 files changed, 352 insertions, 110 deletions
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
generated by cgit v1.2.1 (git 2.18.0) at 2024-12-01 19:35:15 +0100