add devide and conquor slides

4 files changed, 207 insertions, 0 deletions

diff --git a/vorlesungen/slides/a/dc/beispiel.tex b/vorlesungen/slides/a/dc/beispiel.tex
new file mode 100644
index 0000000..4c99e9e
--- /dev/null
+++ b/vorlesungen/slides/a/dc/beispiel.tex
@@ -0,0 +1,54 @@
+%
+% beispiel.tex -- slide template
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\def\u#1#2{\uncover<#1->{#2}}
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Beispiel}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{block}{Aufgabe}
+Berechne $1291^{17}\in\mathbb{F}_{2027}$
+\end{block}
+\uncover<2->{%
+\begin{block}{Exponent}
+\vspace{-10pt}
+\[
+17 = 2^4 + 1
+=
+\texttt{10001}_2
+=
+\texttt{0x11}
+\]
+\end{block}}
+\end{column}
+\begin{column}{0.48\textwidth}
+\uncover<3->{%
+\begin{block}{Divide-and-Conquor}
+\begin{center}
+\begin{tabular}{|>{$}r<{$}>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|}
+\hline
+i&2^i&    a^{2^i} &       n &     n_i &                      m \\
+\hline
+0&  1&       1291 &      17 & \u{4}{1}&\u{5}{             1291}\\
+1&  2& \u{6}{ 487}& \u{7}{8}& \u{8}{0}& \u{9}{\color{gray}1291}\\
+2&  4&\u{10}{  10}&\u{11}{4}&\u{12}{0}&\u{13}{\color{gray}1291}\\
+3&  8&\u{14}{ 100}&\u{15}{2}&\u{16}{0}&\u{17}{\color{gray}1291}\\
+4& 16&\u{18}{1892}&\u{19}{1}&\u{20}{1}&\u{21}{              37}\\
+\hline
+\end{tabular}
+\end{center}
+\end{block}}
+\uncover<22->{%
+\begin{block}{Resultat}
+\(1291^{17} \equiv 37\mod 2027\)
+\end{block}}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/a/dc/effizient.tex b/vorlesungen/slides/a/dc/effizient.tex
new file mode 100644
index 0000000..327ee7e
--- /dev/null
+++ b/vorlesungen/slides/a/dc/effizient.tex
@@ -0,0 +1,65 @@
+%
+% effizient.tex -- Effiziente Berechnung der Potenz
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\definecolor{darkgreen}{rgb}{0,0.6,0}
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Effiziente Berechnung}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{block}{Prinzip}
+\begin{enumerate}
+\item<3-> {\color{red}Bits mit Shift isolieren}
+\item<4-> {\color{blue}Laufend reduzieren}
+\item<5-> {\color{darkgreen}effizient quadrieren}
+\end{enumerate}
+\end{block}
+\end{column}
+\begin{column}{0.48\textwidth}
+\begin{block}{Algorithmus}
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+\uncover<3->{
+\fill[color=red!20] (2.3,-2.44) rectangle (3.8,-1.98);
+\fill[color=red!20] (1.45,-3.88) rectangle (3.2,-3.42);
+}
+\uncover<4->{
+\fill[color=blue!20] (2.15,-2.94) rectangle (3.7,-2.48);
+}
+\uncover<5->{
+\fill[color=darkgreen!20] (1.45,-4.37) rectangle (3.8,-3.91);
+}
+\node at (0,0) [below right] {\begin{minipage}{6cm}\obeylines
+{\tt int potenz(int $a$, int $n$) \{}\\
+\hspace*{0.7cm}{\tt int m = 1;}\\
+\hspace*{0.7cm}{\tt int q = $a$;}\\
+\uncover<2->{%
+\hspace*{0.7cm}{\tt while ($n$ > 0) \{}\\
+\uncover<3->{%
+\hspace*{1.4cm}{\tt if (0x1 \& $n$) \{}\\
+\uncover<4->{%
+\hspace*{2.1cm}{\tt m *= q;}\\
+}%
+\hspace*{1.4cm}{\tt \}}\\
+\hspace*{1.4cm}{\tt $n$ >{}>= 1;}\\
+}%
+\uncover<5->{%
+\hspace*{1.4cm}{\tt q = sqr(q);}\\
+}%
+\hspace*{0.7cm}{\tt \}}\\
+}%
+\hspace*{0.7cm}{\tt return m;}\\
+{\tt \}}
+\end{minipage}};
+\end{tikzpicture}
+\end{center}
+\end{block}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/a/dc/naiv.txt b/vorlesungen/slides/a/dc/naiv.txt
new file mode 100644
index 0000000..bf5569d
--- /dev/null
+++ b/vorlesungen/slides/a/dc/naiv.txt
@@ -0,0 +1,2 @@
+int m = 1, i = 0;
+while (i++ < n) { m *= a; }
diff --git a/vorlesungen/slides/a/dc/prinzip.tex b/vorlesungen/slides/a/dc/prinzip.tex
new file mode 100644
index 0000000..c75af61
--- /dev/null
+++ b/vorlesungen/slides/a/dc/prinzip.tex
@@ -0,0 +1,86 @@
+%
+% prinzip.tex -- slide template
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Potenzieren $\mod p$}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{block}{Aufgabe}
+Berechne $a^n\in\mathbb{F}_p$ für grosses $n$
+\end{block}
+\uncover<2->{%
+\begin{block}{Mengengerüst}
+\(
+\log_2 n > 2000
+\)
+\\
+\uncover<3->{%
+RSA mit $N=pq$: Exponenten sind $e,d$, $e$ klein, aber 
+\(
+ed\equiv 1 \mod \varphi(N)
+\)}
+\end{block}}
+\uncover<4->{%
+\begin{block}{Naive Idee}
+\verbatiminput{../slides/a/dc/naiv.txt}
+Laufzeit: $O(n) \uncover<5->{= O(2^{\log_2n})}$%
+\uncover<5->{, d.~h.~exponentiell in der Bitlänge von $n$}
+\end{block}}
+\end{column}
+\begin{column}{0.48\textwidth}
+\uncover<6->{%
+\begin{block}{Idee 1: Exponent binär schreiben}
+\vspace{-12pt}
+\[
+n = n_k2^k + n_{k-1}2^{k-1} + \dots  +n_12^1 + n_02^0
+\]
+\end{block}}
+\vspace{-5pt}
+\uncover<7->{%
+\begin{block}{Idee 2: Potenzgesetze}
+\vspace{-12pt}
+\[
+a^n
+=
+a^{n_k2^k}
+a^{n_{k-1}2^k}
+\dots
+a^{n_12^1}
+a^{n_02^0}
+\uncover<8->{=
+\prod_{n_i = 1}
+a^{2^i}}
+\]
+\end{block}}
+\vspace{-15pt}
+\uncover<9->{%
+\begin{block}{Idee 3: Quadrieren}
+\vspace{-10pt}
+\begin{align*}
+a^{2^i}
+&=
+a^{2\cdot 2^{i-1}}
+\uncover<10->{=
+(a^{2^{i-1}})^2}
+\\
+&\uncover<11->{=
+(\dots(a\underbrace{\mathstrut^2)^2\dots)^2}_{\displaystyle i}}
+\end{align*}
+\end{block}}
+\vspace{-18pt}
+\uncover<12->{%
+\begin{block}{Laufzeit}
+Multiplikationen: $\le 2 \cdot(\log_2(n) - 1)$
+\\
+\uncover<13->{Worst case Laufzeit: $O(\log_2 n)$}
+\end{block}}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup