%
% 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