diff options
author | JODBaer <JODBaer@github.com> | 2021-04-20 12:38:29 +0200 |
---|---|---|
committer | JODBaer <JODBaer@github.com> | 2021-04-20 12:38:29 +0200 |
commit | f9154b1070929ac3063a9676e11723e5ec0c8deb (patch) | |
tree | 3b2da1b4ee8f80ebe5c05a6c74f48832b57ffc9e /vorlesungen/slides/a/dc/prinzip.tex | |
parent | Merge remote-tracking branch 'upstream/master' (diff) | |
parent | Merge branch 'master' of github.com:AndreasFMueller/SeminarMatrizen (diff) | |
download | SeminarMatrizen-f9154b1070929ac3063a9676e11723e5ec0c8deb.tar.gz SeminarMatrizen-f9154b1070929ac3063a9676e11723e5ec0c8deb.zip |
Merge remote-tracking branch 'upstream/master'
Diffstat (limited to '')
-rw-r--r-- | vorlesungen/slides/a/dc/prinzip.tex | 86 |
1 files changed, 86 insertions, 0 deletions
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 |