diff options
| author | Nao Pross <np@0hm.ch> | 2021-04-19 18:02:30 +0200 |
|---|---|---|
| committer | Nao Pross <np@0hm.ch> | 2021-04-19 18:02:30 +0200 |
| commit | 675239e3d44e8d0b2d7bc022c0d0d773c81889c1 (patch) | |
| tree | f20ac2db0ae44384a5ee3781466aaec50f7fdee2 | |
| parent | Fix complex plane animation (diff) | |
| parent | Titleseite und Handout. (diff) | |
| download | SeminarMatrizen-675239e3d44e8d0b2d7bc022c0d0d773c81889c1.tar.gz SeminarMatrizen-675239e3d44e8d0b2d7bc022c0d0d773c81889c1.zip | |
Merge remote-tracking branch 'upstream/master'
Diffstat (limited to '')
56 files changed, 2867 insertions, 38 deletions
diff --git a/buch/.gitignore b/buch/.gitignore new file mode 100644 index 0000000..4600c1a --- /dev/null +++ b/buch/.gitignore @@ -0,0 +1,12 @@ +buch*.aux +buch*.bbl +buch*.bib +buch*.blg +buch*.idx +buch*.ilg +buch*.ind +buch*.log +buch*.out +buch*.pdf +buch*.run.xml +buch*.toc diff --git a/buch/chapters/30-endlichekoerper/euklid.tex b/buch/chapters/30-endlichekoerper/euklid.tex index 8aa2f71..094a07a 100644 --- a/buch/chapters/30-endlichekoerper/euklid.tex +++ b/buch/chapters/30-endlichekoerper/euklid.tex @@ -519,6 +519,7 @@ Insbesondere ist der euklidische Algorithmus genauso wie die Matrixschreibweise auch für Polynome durchführbar. \begin{beispiel} +\label{buch:endlichekoerper:eqn:polynomggt} Wir berechnen als Beispiel den grössten gemeinsamen Teiler der Polynome \[ @@ -829,5 +830,154 @@ das kleinste gemeinsame Vielfache zweier Polynome zu berechnen. Dies wird zum Beispiel bei der Decodierung des Reed-Solomon-Codes in Kapitel~\ref{chapter:reedsolomon} verwendet. +\subsubsection{Polynome +\label{buch:endlichekoerper:eqn:polynomkgv}} +Im Beispiel auf Seite~\pageref{buch:endlichekoerper:eqn:polynomggt} +wird der grösste gemeinsame Teiler der Polynome +\[ +a += +X^4 - 2X^3 -7 X^2 + 8X + 12, +\qquad +b = X^4 + X^3 -7X^2 -X + 6 +\] +berechnet. +Dies kann jetzt erweitert werden für die Berechnung des kleinsten +gemeinsamen Vielfachen. + +\begin{beispiel} +Die Berechnungstabelle nur für die Spalten $e_k$ und $f_k$ ergibt +\begin{center} +\renewcommand{\arraystretch}{1.4} +\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|} +\hline +k& q_k& e_k& f_k\\ +\hline + & & 0& 1\\ +0& 1& 1& 0\\ +1&-\frac13X-\frac13& 1& 1\\ +2& \frac34X+\frac34& -\frac13X+\frac23& -\frac13X-\frac13\\ + & &-\frac14X^2+\frac14X+\frac32&-\frac14X^2-\frac12X+\frac34\\ +\hline +\end{tabular} +\end{center} +Daraus kann man ablesen, dass +\[ +u += +-\frac14X^2+\frac14X+\frac32 +\qquad\text{und}\qquad +v += +-\frac14X^2-\frac12X+\frac34. +\] +Daraus ergibt sich das kleinste gemeinsame Vielfache auf zwei verschiedene Weisen: +\[ +\operatorname{ggT}(a,b) += +\left\{ +\begin{aligned} +\textstyle +(-\frac14X^2+\frac14X+\frac32)&\cdot(X^4 - 2X^3 -7 X^2 + 8X + 12) +\\ +\textstyle +(-\frac14X^2-\frac12X+\frac34)&\cdot(X^4 + X^3 -7X^2 -X + 6) +\end{aligned} +\right\} += +-\frac14X^6+\frac72X^4-\frac{49}4X^2+9. +\] +Die beiden Berechnungsmöglichkeiten stimmen wie erwartet überein. +\end{beispiel} + +\subsubsection{Anwendung: Decodierung des Reed-Solomon-Codes} +Der Reed-Solomon-Code verwendet Polynome zur Codierung der Daten, +dies wird in Kapitel~\ref{chapter:reedsolomon} im Detail beschrieben. +Bei der Decodierung muss der Faktor $u$ für zwei gegebene Polynome +$n(X)$ und $r(X)$ bestimmt werden. +Allerdings ist das Polynom $r(X)$ nicht vollständig bekannt, nur die +ersten paar Koeffizienten sind gegeben. +Dafür weiss man zusätzlich, wieviele Schritte genau der Euklidische +Algorithmus braucht. +Daraus lässt sich genügend Information gewinnen, um die Faktoren $u$ +und $v$ zu bestimmen. +Das Video \url{https://youtu.be/uOLW43OIZJ0} von Edmund Weitz +erklärt die Theorie hinter dieser Teilaufgabe anhand von Beispielen. + +\begin{beispiel} +Wir berechnen also die Faktoren $u$ und $v$ für die beiden Polynome +\begin{align*} +n(X) +&= +X^{12}+12 +\\ +r(X) +&= +7 X^{11} + 4 X^{10} + X^9 + 12 X^8 + 2 X^7 + 12 X^6 + w(X) +\end{align*} +in $\mathbb{F}_{13}[X]$, wobei $w(X)$ ein unbekanntes Polynom vom Grad $5$ ist. +Man weiss zusätzlich noch, dass der euklidische Algorithmus genau drei +Schritte braucht, es gibt also genau drei Quotienten, die in die +Berechnung der Zahlen $e_k$ und $f_k$ einfliessen. +Im ersten Schritt des euklidischen Algorithmus ist der Quotient +$n(X) / r(X)$ zu bestimmen, der Grad $1$ haben muss. +\begin{align*} +a_0=n(X) &= X^{12}+12 +\\ +b_0=r(X) &= 7 X^{11} + 4 X^{10} + X^9 + 12 X^8 + 2 X^7 + 12 X^6 + \dots +\\ +q_0 &= 2X+10 +\\ +r_0 = a_0-b_0\cdot q_0 &= 10X^{10} + 5X^9 + 6X^8 + 8X^7 + \dots +\\ +a_1 &= 7 X^{11} + 4 X^{10} + X^9 + 12 X^8 + 2 X^7 + 12 X^6 + \dots +\\ +b_1 &= 10X^{10} + 5X^9 + 6X^8 + 8X^7 + \dots +\\ +q_1 &= 2X+2 +\\ +r_1 = a_1 - b_1q_1 &= 5X^9 + 10 X^8 + \dots +\\ +a_2 &= 10X^{10} + 5X^9 + 6X^8 + 8X^7 + \dots +\\ +b_2 &= 5X^9 + 10 X^8 + \dots +\\ +q_2 &= 2X+10 +\end{align*} +Aus den Polynomen $q_k$ können jetzt die Faktoren $u$ und $v$ +bestimmt werden: +\begin{center} +\begin{tabular}{|>{$}c<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|} +\hline +k& q_k& e_k& f_k\\ +\hline + & & 0& 1\\ +0& 2X+10& 1& 0\\ +1& 2X+2 & 2X+10& 1\\ +2& 2X+10& 4X^2+11X+8& 2X+2\\ + & & 8X^3+10X^2+11X+12& 4X^2+11X+8\\ +\hline +\end{tabular} +\end{center} +Die Faktorisierung des Polynoms +\[ +u += +8X^3+10X^2+11X+12 +\] +kann bestimmt werden, indem man alle Zahlen $1,2,\dots,12\in\mathbb{F}_{13}$ +einsetzt. +Man findet so die Nullstellen $3$, $4$ und $8$, also muss das Polynom +$u$ faktorisiert werden können als +\[ +u= +8(X-3)(X-4)(X-8) += +8X^3 - 120X^2+544X-768 += +8X^3 +10X^2+11X+12. +\qedhere +\] +\end{beispiel} diff --git a/buch/chapters/30-endlichekoerper/galois.tex b/buch/chapters/30-endlichekoerper/galois.tex index fbacba6..2f8117e 100644 --- a/buch/chapters/30-endlichekoerper/galois.tex +++ b/buch/chapters/30-endlichekoerper/galois.tex @@ -27,7 +27,7 @@ Primzahlpotenz $p^n$ von Elementen haben und die die Basis wichtiger kryptographischer Algorithmen sind. % -% Arithmetik module $o$ +% Arithmetik modulo $o$ % \subsection{Arithmetik modulo $p$ \label{buch:subsection:arithmetik-modulo-p}} @@ -413,7 +413,7 @@ Elemente. \begin{figure} \centering \includegraphics{chapters/30-endlichekoerper/images/binomial2.pdf} -\caption{Binomialkoeffizienten module $2$ im Pascal-Dreieck. +\caption{Binomialkoeffizienten modulo $2$ im Pascal-Dreieck. Auf den rot hinterlegten Zeilen, die zu Exponenten der Form $2^k$ gehören, sind alle Koeffizienten ausser dem ersten und letzten durch $2$ teilbar. \label{buch:endliche-koerper:fig:binomial2}} @@ -423,7 +423,7 @@ sind alle Koeffizienten ausser dem ersten und letzten durch $2$ teilbar. \begin{figure} \centering \includegraphics{chapters/30-endlichekoerper/images/binomial5.pdf} -\caption{Binomialkoeffizienten module $5$ im Pascal-Dreieck. +\caption{Binomialkoeffizienten modulo $5$ im Pascal-Dreieck. Die von $0$ verschiedenen Reste werden durch Farben dargestellt: $1=\text{schwarz}$, $2=\text{\color{farbe2}rot}$, diff --git a/buch/chapters/30-endlichekoerper/rechnungen/rs.maxima b/buch/chapters/30-endlichekoerper/rechnungen/rs.maxima new file mode 100644 index 0000000..9116023 --- /dev/null +++ b/buch/chapters/30-endlichekoerper/rechnungen/rs.maxima @@ -0,0 +1,29 @@ +n: X^12 + 12; +r: 7*X^11 + 4*X^10 + X^9 + 12*X^8 + 2*X^7 + 12*X^6; + +q0: 2*X+10; +q1: 2*X+2; +q2: 2*X+10; + +a0: n; +b0: r; +r0: expand(a0 - q0 * b0); + +a1: b0; +b1: r0; +r1: expand(a1 - q1 * b1); + +a2: b1; +b2: r1; +r2: expand(a2 - q2 * b2); + +K: matrix([1,0],[0,1]); + +K: expand(K . matrix([q0,1],[1,0])); +K: expand(K . matrix([q1,1],[1,0])); +K: expand(K . matrix([q2,1],[1,0])); + +u: 8*X^3+10*X^2+11*X+12; +v: 4*X^2+11*X+8; + +factor(u), modulus:13; diff --git a/buch/chapters/30-endlichekoerper/wurzeln.tex b/buch/chapters/30-endlichekoerper/wurzeln.tex index 02429dc..600336c 100644 --- a/buch/chapters/30-endlichekoerper/wurzeln.tex +++ b/buch/chapters/30-endlichekoerper/wurzeln.tex @@ -731,7 +731,7 @@ dass sf+tm=1. \] Reduzieren wir modulo $m$, wird daraus $af=1$ in $\Bbbk[X]/m\Bbbk[X]$. -Das Polynom $a$, reduziert module $m$, ist also die multiplikative +Das Polynom $a$, reduziert modulo $m$, ist also die multiplikative Inverse von $f$. Bei der praktischen Durchführung des euklidischen Algorithmus ist der diff --git a/buch/chapters/90-crypto/arith.tex b/buch/chapters/90-crypto/arith.tex index 44eb6bb..dcc31b8 100644 --- a/buch/chapters/90-crypto/arith.tex +++ b/buch/chapters/90-crypto/arith.tex @@ -91,7 +91,7 @@ Die Berechnung der Quadratwurzel lässt sich in Hardware effizient implementieren. \begin{algorithmus} -Der folgende Algorithmsu berechnet $a^k$ in $O(\log_2(k))$ +Der folgende Algorithmus berechnet $a^k$ in $O(\log_2(k))$ Multiplikationen \begin{enumerate} \item Initialisiere $p=1$ und $q=a$ diff --git a/buch/papers/spannung/main.tex b/buch/papers/spannung/main.tex index b87a4d0..585a423 100644 --- a/buch/papers/spannung/main.tex +++ b/buch/papers/spannung/main.tex @@ -6,7 +6,7 @@ \chapter{Thema\label{chapter:spannung}} \lhead{Thema} \begin{refsection} -\chapterauthor{Hans Muster} +\chapterauthor{Adrian Schuler und Thomas Reichlin} Ein paar Hinweise für die korrekte Formatierung des Textes \begin{itemize} diff --git a/vorlesungen/07_msecrypto/Makefile b/vorlesungen/07_msecrypto/Makefile new file mode 100644 index 0000000..5d4ecd0 --- /dev/null +++ b/vorlesungen/07_msecrypto/Makefile @@ -0,0 +1,33 @@ +# +# Makefile -- crypto +# +# (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil +# +all: crypto-handout.pdf MathSemMSE-07-crypto.pdf + +include ../slides/Makefile.inc + +SOURCES = common.tex slides.tex $(slides) + +MathSemMSE-07-crypto.pdf: MathSemMSE-07-crypto.tex $(SOURCES) + pdflatex MathSemMSE-07-crypto.tex + +crypto-handout.pdf: crypto-handout.tex $(SOURCES) + pdflatex crypto-handout.tex + +thumbnail: thumbnail.jpg # fix1.jpg + +thumbnail.pdf: MathSemMSE-07-crypto.pdf + pdfjam --outfile thumbnail.pdf --papersize '{16cm,9cm}' \ + MathSemMSE-07-crypto.pdf 1 +thumbnail.jpg: thumbnail.pdf + convert -density 300 thumbnail.pdf \ + -resize 1920x1080 -units PixelsPerInch thumbnail.jpg + +fix1.pdf: MathSemMSE-07-crypto.pdf + pdfjam --outfile fix1.pdf --papersize '{16cm,9cm}' \ + MathSemMSE-07-crypto.pdf 1 +fix1.jpg: fix1.pdf + convert -density 300 fix1.pdf \ + -resize 1920x1080 -units PixelsPerInch fix1.jpg + diff --git a/vorlesungen/07_msecrypto/MathSemMSE-07-crypto.tex b/vorlesungen/07_msecrypto/MathSemMSE-07-crypto.tex new file mode 100644 index 0000000..179837b --- /dev/null +++ b/vorlesungen/07_msecrypto/MathSemMSE-07-crypto.tex @@ -0,0 +1,14 @@ +% +% MathSem-07-msecrypto.tex -- Präsentation +% +% (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\documentclass[aspectratio=169]{beamer} +\input{common.tex} +\setboolean{presentation}{true} +\begin{document} +\begin{frame} +\titlepage +\end{frame} +\input{slides.tex} +\end{document} diff --git a/vorlesungen/07_msecrypto/common.tex b/vorlesungen/07_msecrypto/common.tex new file mode 100644 index 0000000..0026619 --- /dev/null +++ b/vorlesungen/07_msecrypto/common.tex @@ -0,0 +1,16 @@ +% +% common.tex -- gemeinsame definition +% +% (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\input{../common/packages.tex} +\input{../common/common.tex} +\mode<beamer>{% +\usetheme[hideothersubsections,hidetitle]{Hannover} +} +\beamertemplatenavigationsymbolsempty +\title[Crypto]{Endliche Körper und Kryptographie} +\author[A.~Müller]{Prof. Dr. Andreas Müller} +\date[]{} +\newboolean{presentation} + diff --git a/vorlesungen/07_msecrypto/crypto-handout.tex b/vorlesungen/07_msecrypto/crypto-handout.tex new file mode 100644 index 0000000..d42a260 --- /dev/null +++ b/vorlesungen/07_msecrypto/crypto-handout.tex @@ -0,0 +1,11 @@ +% +% msecrypto-handout.tex -- Handout XXX +% +% (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\documentclass[handout,aspectratio=169]{beamer} +\input{common.tex} +\setboolean{presentation}{false} +\begin{document} +\input{slides.tex} +\end{document} diff --git a/vorlesungen/07_msecrypto/slides.tex b/vorlesungen/07_msecrypto/slides.tex new file mode 100644 index 0000000..cb0c548 --- /dev/null +++ b/vorlesungen/07_msecrypto/slides.tex @@ -0,0 +1,43 @@ +% +% slides.tex -- Präsentation zur Kryptographie +% +% (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\section{Diffie-Hellmann} +\folie{4/dh.tex} + +\section{Divide and Conquer} +% Potenzieren +\folie{a/dc/prinzip.tex} +% effiziente Durchführung +\folie{a/dc/effizient.tex} +% Beispieldurchführung +\folie{a/dc/beispiel.tex} + +\section{Elliptische Kurven} +% Idee +\folie{a/ecc/gruppendh.tex} +% Was ist eine elliptische Kurve (char 0 Bild) +\folie{a/ecc/kurve.tex} +% Involution/Inverse +\folie{a/ecc/inverse.tex} +% Verknüpfung +\folie{a/ecc/operation.tex} +% Quadrieren +\folie{a/ecc/quadrieren.tex} +% Oakley Gruppe +\ifthenelse{\boolean{presentation}}{ +\folie{a/ecc/oakley.tex} +}{} + +\section{AES} +% Byte-Operationen +\folie{a/aes/bytes.tex} +\folie{a/aes/sinverse.tex} +% Block-Operationen +\folie{a/aes/blocks.tex} +% Key-Schedule +\folie{a/aes/keys.tex} +% Zusammensetzung +\folie{a/aes/runden.tex} + diff --git a/vorlesungen/08_dgl/Makefile b/vorlesungen/08_dgl/Makefile new file mode 100644 index 0000000..7a3960a --- /dev/null +++ b/vorlesungen/08_dgl/Makefile @@ -0,0 +1,46 @@ +# +# Makefile -- dgl +# +# (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil +# +all: dgl-handout.pdf MathSem-08-dgl.pdf + +# SHELL = /bin/bash + +include ../slides/Makefile.inc + +SOURCES = common.tex slides.tex $(slides) +IMAGES = vektorfelder-1.pdf + + +MathSem-08-dgl.pdf: MathSem-08-dgl.tex $(SOURCES) $(IMAGES) + pdflatex --synctex=1 MathSem-08-dgl.tex > /dev/null + +dgl-handout.pdf: dgl-handout.tex $(SOURCES) $(IMAGES) + pdflatex dgl-handout.tex > /dev/null + +vektorfelder-1.pdf: ../slides/10/vektorfelder.mp + cd ../slides/10/; \ + TEX=latex mpost vektorfelder.mp; \ + for f in vektorfelder.[0-9]*; \ + do \ + mptopdf $${f} > /dev/null; \ + done; \ + rm -f vektorfelder.[0-9]* vektorfelder.log vektorfelder.mpx + +thumbnail: thumbnail.jpg # fix1.jpg + +thumbnail.pdf: MathSem-08-dgl.pdf + pdfjam --outfile thumbnail.pdf --papersize '{16cm,9cm}' \ + MathSem-08-dgl.pdf 1 +thumbnail.jpg: thumbnail.pdf + convert -density 300 thumbnail.pdf \ + -resize 1920x1080 -units PixelsPerInch thumbnail.jpg + +fix1.pdf: MathSem-08-dgl.pdf + pdfjam --outfile fix1.pdf --papersize '{16cm,9cm}' \ + MathSem-08-dgl.pdf 1 +fix1.jpg: fix1.pdf + convert -density 300 fix1.pdf \ + -resize 1920x1080 -units PixelsPerInch fix1.jpg + diff --git a/vorlesungen/08_dgl/MathSem-08-dgl.tex b/vorlesungen/08_dgl/MathSem-08-dgl.tex new file mode 100644 index 0000000..e4ece1b --- /dev/null +++ b/vorlesungen/08_dgl/MathSem-08-dgl.tex @@ -0,0 +1,35 @@ +% +% MathSem-08-dgl.tex -- Präsentation +% +% (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\documentclass[aspectratio=169]{beamer} +\input{common.tex} +\setboolean{presentation}{true} +\begin{document} + \begin{frame} + \titlepage + \vspace{-1.5cm} + \begin{columns} + \begin{column}{.48\textwidth} + \centering + \includegraphics[width=.7\linewidth]{../slides/10/vektorfelder-6.pdf} + \end{column} + \begin{column}{.48\textwidth} + \begin{align*} + x(t) + &= + \exp(At) x_0 + \\ + \exp(At) + &= + 1 + At + \frac{A^2t^2}{2} + \frac{A^3 t^3}{3!} + \ldots + \\ + &= + \lim_{n\to \infty} \left(1 + \frac{At}{n}\right)^n + \end{align*} + \end{column} + \end{columns} +\end{frame} +\input{slides.tex} +\end{document} diff --git a/vorlesungen/08_dgl/common.tex b/vorlesungen/08_dgl/common.tex new file mode 100644 index 0000000..fbf3ad9 --- /dev/null +++ b/vorlesungen/08_dgl/common.tex @@ -0,0 +1,27 @@ +% +% common.tex -- gemeinsame definition +% +% (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\input{../common/packages.tex} +\input{../common/common.tex} +\mode<beamer>{% +\usetheme[hideothersubsections,hidetitle]{Hannover} +} +\beamertemplatenavigationsymbolsempty +\title[DGL]{Differential-Gleichungen} +\author[R.~Seitz]{Roy Seitz} +\date[]{} +\newboolean{presentation} + +\newcommand{\gSL}[2]{\ensuremath{\text{SL}(#1, \mathbb{#2})}} +\newcommand{\gSO}[1]{\ensuremath{\text{SO}(#1)}} +\newcommand{\gGL}[2]{\ensuremath{\text{GL}(#1, \mathbb #2)}} + +\newcommand{\asl}[2]{\ensuremath{\mathfrak{sl}(#1, \mathbb{#2})}} +\newcommand{\aso}[1]{\ensuremath{\mathfrak{so}(#1)}} +\newcommand{\agl}[2]{\ensuremath{\mathfrak{gl}(#1, \mathbb #2)}} + +\DeclareMathOperator{\Spur}{Spur} + + diff --git a/vorlesungen/08_dgl/dgl-handout.tex b/vorlesungen/08_dgl/dgl-handout.tex new file mode 100644 index 0000000..2bd08a1 --- /dev/null +++ b/vorlesungen/08_dgl/dgl-handout.tex @@ -0,0 +1,11 @@ +% +% dgl-handout.tex -- Handout XXX +% +% (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\documentclass[handout,aspectratio=169]{beamer} +\input{common.tex} +\setboolean{presentation}{false} +\begin{document} +\input{slides.tex} +\end{document} diff --git a/vorlesungen/08_dgl/slides.tex b/vorlesungen/08_dgl/slides.tex new file mode 100644 index 0000000..029e1c7 --- /dev/null +++ b/vorlesungen/08_dgl/slides.tex @@ -0,0 +1,35 @@ +% +% slides.tex -- XXX +% +% (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil +% + +% Wie findet man die Lösung von \dot x = Ax? +% Fall \dot x = ax +% Potenzreihenansatz -> exp(ax) x_0 + +%% Plan: +% 1. Tailor-Reihen p_n -> f +% 2. x' = ax => x = exp(ax) x_0 via Potenzreihe finden +% 3. n-Dim-skalar -> 1-Dim-Matrix +% 4. Analogie zur Vektor-Matrix-Form +% 5. exp(Ax) x_0 als Fluss +% 6. Strömungslinien = Pfade für Lie-Theorie, A lokal, exp(Ax) global +% 7. Beispiele so(2), Jordan-Block, vielleicht [0 1; 1 0] + +\section{Einführung} +\folie{10/intro.tex} +\section{Woher kommt $\exp(At)$?} +\subsection{Taylor-Reihen} +\folie{10/taylor.tex} +\folie{10/potenzreihenmethode.tex} +\subsection{Ableitung von $\exp(At)$} +\folie{10/ableitung-exp.tex} +\section{Lösen einer Matrix-DGL} +\folie{10/n-zu-1.tex} +\folie{10/matrix-dgl.tex} +\section{Lie-Gruppen und -Algebren} +\folie{10/repetition.tex} +\folie{10/so2.tex} +\section{Was bedeutet $\exp(At)$?} +\folie{10/vektorfelder.tex} diff --git a/vorlesungen/common/packages.tex b/vorlesungen/common/packages.tex index d71438b..7e044ed 100644 --- a/vorlesungen/common/packages.tex +++ b/vorlesungen/common/packages.tex @@ -12,6 +12,7 @@ \usepackage{lmodern} \usepackage{amsmath} \usepackage{amssymb} +\usepackage{nccmath} \usepackage{mathtools} \usepackage{adjustbox} \usepackage{multimedia} diff --git a/vorlesungen/slides/10/ableitung-exp.tex b/vorlesungen/slides/10/ableitung-exp.tex new file mode 100644 index 0000000..10ce191 --- /dev/null +++ b/vorlesungen/slides/10/ableitung-exp.tex @@ -0,0 +1,60 @@ +% +% ableitung-exp.tex -- Ableitung von exp(x) +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% Erstellt durch Roy Seitz +% +% !TeX spellcheck = de_CH +\bgroup +\begin{frame}[t] + \setlength{\abovedisplayskip}{5pt} + \setlength{\belowdisplayskip}{5pt} + %\frametitle{Ableitung von $\exp(x)$} + %\vspace{-20pt} + \begin{columns}[t,onlytextwidth] + \begin{column}{0.48\textwidth} + \begin{block}{Ableitung von $\exp(at)$} + \begin{align*} + \frac{d}{dt} \exp(at) + &= + \frac{d}{dt} \sum_{k=0}^{\infty} a^k \frac{t^k}{k!} + \\ + &\uncover<2->{ + = \sum_{k=0}^{\infty} a^k\frac{kt^{k-1}}{k(k-1)!} + } + \\ + &\uncover<3->{ + = a \sum_{k=1}^{\infty} + a^{k-1}\frac{t^{k-1}}{(k-1)!} + } + \\ + &\uncover<4->{ + = a \exp(at) + } + \end{align*} + \end{block} + \end{column} + \begin{column}{0.48\textwidth} + \uncover<5->{ + \begin{block}{Ableitung von $\exp(At)$} + \begin{align*} + \frac{d}{dt} \exp(At) + &= + \frac{d}{dt} \sum_{k=0}^{\infty} A^k \frac{t^k}{k!} + \\ + &= + \sum_{k=0}^{\infty} A^k\frac{kt^{k-1}}{k(k-1)!} + \\ + &= + A \sum_{k=1}^{\infty} A^{k-1}\frac{t^{k-1}}{(k-1)!} + \\ + &= + A \exp(At) + \end{align*} + \end{block} + } + \end{column} + \end{columns} +\end{frame} + +\egroup diff --git a/vorlesungen/slides/10/intro.tex b/vorlesungen/slides/10/intro.tex new file mode 100644 index 0000000..276bf49 --- /dev/null +++ b/vorlesungen/slides/10/intro.tex @@ -0,0 +1,45 @@ +% +% intro.tex -- Repetition Lie-Gruppen und -Algebren +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% Erstellt durch Roy Seitz +% +% !TeX spellcheck = de_CH +\bgroup + + + +\begin{frame}[t] + \setlength{\abovedisplayskip}{5pt} + \setlength{\belowdisplayskip}{5pt} +% \frametitle{Repetition} +% \vspace{-20pt} + \begin{block}{Offene Fragen} + \begin{itemize}[<+->] + \item Woher kommt die Exponentialfunktion? + \begin{fleqn} + \[ + \exp(At) + = + 1 + + At + + A^2\frac{t^2}{2} + + A^3\frac{t^3}{3!} + + \ldots + \] + \end{fleqn} + \item Wie löst man eine Matrix-DGL? + \begin{fleqn} + \[ + \dot\gamma(t) = A\gamma(t), + \qquad + \gamma(t) \in G \subset M_n + \] + \end{fleqn} + \item Lie-Gruppen und Lie-Algebren + \item Was bedeutet $\exp(At)$? + \end{itemize} + \end{block} +\end{frame} + +\egroup diff --git a/vorlesungen/slides/10/matrix-dgl.tex b/vorlesungen/slides/10/matrix-dgl.tex new file mode 100644 index 0000000..ae68fb1 --- /dev/null +++ b/vorlesungen/slides/10/matrix-dgl.tex @@ -0,0 +1,83 @@ +% +% matrix-dgl.tex -- Matrix-Differentialgleichungen +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% Erstellt durch Roy Seitz +% +% !TeX spellcheck = de_CH +\bgroup + +\begin{frame}[t] + \setlength{\abovedisplayskip}{5pt} + \setlength{\belowdisplayskip}{5pt} + \frametitle{1.~Ordnung mit Skalaren} + \vspace{-20pt} + \begin{columns}[t,onlytextwidth] + \begin{column}{0.48\textwidth} + \begin{block}{Aufgabe} + Sei $a, x(t), x_0 \in \mathbb R$, + \[ + \dot x(t) = ax(t), + \quad + x(0) = x_0 + \] + \end{block} + \begin{block}{Potenzreihen-Ansatz} + Sei $a_k \in \mathbb R$, + \[ + x(t) = a_0 + a_1t + a_2t^2 + a_3t^3 \ldots + \] + \end{block} + \end{column} + \begin{column}{0.48\textwidth} + \begin{block}{Lösung} + Einsetzen in DGL, Koeffizientenvergleich liefert + \[ x(t) = \exp(at) \, x_0, \] + wobei + \begin{align*} + \exp(at) + &= 1 + at + \frac{a^2t^2}{2} + \frac{a^3t^3}{3!} + \ldots \\ + &{\color{gray}(= e^{at}.)} + \end{align*} + \end{block} + \end{column} + \end{columns} +\end{frame} + +\begin{frame}[t] + \setlength{\abovedisplayskip}{5pt} + \setlength{\belowdisplayskip}{5pt} + \frametitle{1.~Ordnung mit Matrizen} + \vspace{-20pt} + \begin{columns}[t,onlytextwidth] + \begin{column}{0.48\textwidth} + \begin{block}{Aufgabe} + Sei $A \in M_n$, $x(t), x_0 \in \mathbb R^n$, + \[ + \dot x(t) = Ax(t), + \quad + x(0) = x_0 + \] + \end{block} + \begin{block}{Potenzreihen-Ansatz} + Sei $A_k \in \mathbb M_n$, + \[ + x(t) = A_0 + A_1t + A_2t^2 + A_3t^3 \ldots + \] + \end{block} + \end{column} + \begin{column}{0.48\textwidth} + \begin{block}{Lösung} + Einsetzen in DGL, Koeffizientenvergleich liefert + \[ x(t) = \exp(At) \, x_0, \] + wobei + \[ + \exp(At) + = 1 + At + \frac{A^2t^2}{2} + \frac{A^3t^3}{3!} + \ldots + \] + \end{block} + \end{column} + \end{columns} +\end{frame} + +\egroup diff --git a/vorlesungen/slides/10/n-zu-1.tex b/vorlesungen/slides/10/n-zu-1.tex new file mode 100644 index 0000000..09475ad --- /dev/null +++ b/vorlesungen/slides/10/n-zu-1.tex @@ -0,0 +1,63 @@ +% +% n-zu-1.tex -- Umwandlend einer DGL n-ter Ordnung in ein System 1. Ordnung +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% Erstellt durch Roy Seitz +% +% !TeX spellcheck = de_CH +\bgroup +\begin{frame}[t] + \setlength{\abovedisplayskip}{5pt} + \setlength{\belowdisplayskip}{5pt} + %\frametitle{Reicht $1.$ Ordnung?} + %\vspace{-20pt} + \begin{columns}[t,onlytextwidth] + \begin{column}{0.48\textwidth} + \uncover<1->{ + \begin{block}{Beispiel: DGL 3.~Ordnung} \vspace*{-1ex} + \begin{align*} + x^{(3)} + a_2 \ddot x + a_1 \dot x + a_0 x = 0 \\ + \Rightarrow + x^{(3)} = -a_2 \ddot x - a_1 \dot x - a_0 x + \end{align*} + \end{block} + } + \uncover<2->{ + \begin{block}{Ziel: Nur noch 1.~Ableitungen} + Einführen neuer Variablen: + \begin{align*} + x_0 &\coloneqq x & + x_1 &\coloneqq \dot x & + x_2 &\coloneqq \ddot x + \end{align*} + System von Gleichungen 1.~Ordnung + \begin{align*} + \dot x_0 &= x_1 \\ + \dot x_1 &= x_2 \\ + \dot x_2 &= -a_2 x_2 - a_1 x_1 - a_0 x_0 + \end{align*} + \end{block} + } + \end{column} + \uncover<3->{ + \begin{column}{0.48\textwidth} + \begin{block}{Als Vektor-Gleichung} \vspace*{-1ex} + \begin{align*} + \frac{d}{dt} + \begin{pmatrix} x_0 \\ x_1 \\ x_2 \end{pmatrix} + = \begin{pmatrix} + 0 & 1 & 0 \\ + 0 & 0 & 1 \\ + -a_0 & -a_1 & -a_2 + \end{pmatrix} + \begin{pmatrix} x_0 \\ x_1 \\ x_2 \end{pmatrix} + \end{align*} + + \uncover<4->{Geht für jede lineare Differentialgleichung!} + + \end{block} + \end{column} + } + \end{columns} +\end{frame} +\egroup diff --git a/vorlesungen/slides/10/potenzreihenmethode.tex b/vorlesungen/slides/10/potenzreihenmethode.tex new file mode 100644 index 0000000..1715134 --- /dev/null +++ b/vorlesungen/slides/10/potenzreihenmethode.tex @@ -0,0 +1,91 @@ +% +% potenzreihenmethode.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% Bearbeitet durch Roy Seitz +% +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Potenzreihenmethode} +\vspace{-15pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{block}{Lineare Differentialgleichung} +\begin{align*} +x'&=ax&&\Rightarrow&x'-ax&=0 +\\ +x(0)&=C +\end{align*} +\end{block} +\end{column} +\begin{column}{0.48\textwidth} +\uncover<2->{% +\begin{block}{Potenzreihenansatz} +\begin{align*} +x(t) +&= +a_0+ a_1t + a_2t^2 + \dots +\\ +x(0)&=a_0=C +\end{align*} +\end{block}} +\end{column} +\end{columns} +\uncover<3->{% +\begin{block}{Lösung} +\[ +\arraycolsep=1.4pt +\begin{array}{rcrcrcrcrcr} +\uncover<3->{ x'(t)} + \uncover<5->{ + &=&\phantom{(} a_1\phantom{\mathstrut-aa_0)} + &+& 2a_2\phantom{\mathstrut-aa_1)}t + &+& 3a_3\phantom{\mathstrut-aa_2)}t^2 + &+& 4a_4\phantom{\mathstrut-aa_3)}t^3 + &+& \dots}\\ +\uncover<3->{-ax(t)} + \uncover<6->{ + &=&\mathstrut-aa_0 \phantom{)} + &-& aa_1\phantom{)}t + &-& aa_2\phantom{)}t^2 + &-& aa_3\phantom{)}t^3 + &-& \dots}\\[2pt] +\hline +\\[-10pt] +\uncover<3->{0} + \uncover<7->{ + &=&(a_1-aa_0) + &+& (2a_2-aa_1)t + &+& (3a_3-aa_2)t^2 + &+& (4a_4-aa_3)t^3 + &+& \dots}\\ +\end{array} +\] +\begin{align*} +\uncover<4->{ +a_0&=C}\uncover<8->{, +\quad +a_1=aa_0=aC}\uncover<9->{, +\quad +a_2=\frac12a^2C}\uncover<10->{, +\quad +a_3=\frac16a^3C}\uncover<11->{, +\ldots, +a_k=\frac1{k!}a^kC} +\hspace{3cm} +\\ +\uncover<4->{ +\Rightarrow x(t) &= C}\uncover<8->{+Cat}\uncover<9->{ + C\frac12(at)^2} +\uncover<10->{ + C \frac16(at)^3} +\uncover<11->{ + \dots+C\frac{1}{k!}(at)^k+\dots} +\ifthenelse{\boolean{presentation}}{ +\only<12>{ += +C\sum_{k=0}^\infty \frac{(at)^k}{k!}} +}{} +\uncover<13->{= +C\exp(at)} +\end{align*} +\end{block}} +\end{frame} diff --git a/vorlesungen/slides/10/repetition.tex b/vorlesungen/slides/10/repetition.tex new file mode 100644 index 0000000..7c007ca --- /dev/null +++ b/vorlesungen/slides/10/repetition.tex @@ -0,0 +1,119 @@ +% +% repetition.tex -- Repetition Lie-Gruppen und -Algebren +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% Erstellt durch Roy Seitz +% +% !TeX spellcheck = de_CH +\bgroup + +\begin{frame}[t] + \setlength{\abovedisplayskip}{5pt} + \setlength{\belowdisplayskip}{5pt} + \frametitle{Repetition} + \vspace{-20pt} + \begin{columns}[t,onlytextwidth] + \begin{column}{0.48\textwidth} + \uncover<1->{ + \begin{block}{Lie-Gruppe} + Kontinuierliche Matrix-Gruppe $G$ mit bestimmter Eigenschaft + \end{block} + } + \uncover<3->{ + \begin{block}{Ein-Parameter-Untergruppe} + Darstellung der Lie-Gruppe $G$: + \[ + \gamma \colon \mathbb R \to G + : \quad + t \mapsto \gamma(t), + \] + so dass + \[ \gamma(s + t) = \gamma(t) \gamma(s). \] + \end{block} + } + \end{column} + \begin{column}{0.48\textwidth} + \uncover<2->{ + \begin{block}{Beispiel} + Volumen-erhaltende Abbildungen: + \[ \gSL2R= \{A \in M_2 \,|\, \det(A) = 1\} .\] + \begin{align*} + \uncover<4->{ \gamma_x(t) } + & + \uncover<4->{= \begin{pmatrix} 1 & t \\ 0 & 1 \end{pmatrix} } + \\ + \uncover<5->{ \gamma_y(t) } + & + \uncover<5->{= \begin{pmatrix} 1 & 0 \\ t & 1 \end{pmatrix} } + \\ + \uncover<6->{ \gamma_h(t)} + & + \uncover<6->{= \begin{pmatrix} e^t & 0 \\ 0 & e^{-t} \end{pmatrix} } + \end{align*} + \end{block} + } + \end{column} + \end{columns} +\end{frame} + + +\begin{frame}[t] + \setlength{\abovedisplayskip}{5pt} + \setlength{\belowdisplayskip}{5pt} + \frametitle{Repetition} + \vspace{-20pt} + \begin{columns}[t,onlytextwidth] + \begin{column}{0.48\textwidth} + \uncover<1->{ + \begin{block}{Lie-Algebra aus Lie-Gruppe} + Ableitungen der Ein-Parameter-Untergruppen: + \begin{align*} + G &\to \mathcal A \\ + \gamma &\mapsto \dot\gamma(0) + \end{align*} + \uncover<3->{ + Lie-Klammer als Produkt: + \[ [A, B] = AB - BA \in \mathcal A \] + } + \end{block} + } + \uncover<7->{\vspace*{-4ex} + \begin{block}{Lie-Gruppe aus Lie-Algebra} + Lösung der Differentialgleichung: + \[ + \dot\gamma(t) = A\gamma(t) + \quad \text{mit} \quad + A = \dot\gamma(0) + \] + \[ + \Rightarrow \gamma(t) = \exp(At) + \] + \end{block} + } + \end{column} + \begin{column}{0.48\textwidth} + \uncover<2->{ + \begin{block}{Beispiel} + Lie-Algebra von \gSL2R: + \[ \asl2R = \{ A \in M_2 \,|\, \Spur(A) = 0 \} \] + \end{block} + } + \begin{align*} + \uncover<4->{ X(t) } + & + \uncover<4->{= \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} } + \\ + \uncover<5->{ Y(t) } + & + \uncover<5->{= \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix} } + \\ + \uncover<6->{ H(t) } + & + \uncover<6->{= \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} } + \end{align*} + + \end{column} + \end{columns} +\end{frame} + +\egroup diff --git a/vorlesungen/slides/10/so2.tex b/vorlesungen/slides/10/so2.tex new file mode 100644 index 0000000..dcbcdc8 --- /dev/null +++ b/vorlesungen/slides/10/so2.tex @@ -0,0 +1,141 @@ +% +% so2.tex -- Illustration of so(2) -> SO(2) +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% Erstellt durch Roy Seitz +% +% !TeX spellcheck = de_CH +\bgroup + +\begin{frame}[t] + \setlength{\abovedisplayskip}{5pt} + \setlength{\belowdisplayskip}{5pt} + \frametitle{Von der Lie-Gruppe zur -Algebra} + \vspace{-20pt} + \begin{columns}[t,onlytextwidth] + \begin{column}{0.48\textwidth} + \uncover<1->{ + \begin{block}{Lie-Gruppe} + Darstellung von \gSO2: + \begin{align*} + \mathbb R + &\to + \gSO2 + \\ + t + &\mapsto + \begin{pmatrix} + \cos t & -\sin t \\ + \sin t & \phantom-\cos t + \end{pmatrix} + \end{align*} + \end{block} + } + \uncover<2->{ + \begin{block}{Ableitung am neutralen Element} + \begin{align*} + \frac{d}{d t} + & + \left. + \begin{pmatrix} + \cos t & -\sin t \\ + \sin t & \phantom-\cos t + \end{pmatrix} + \right|_{ t = 0} + \\ + = + & + \begin{pmatrix} -\sin0 & -\cos0 \\ \phantom-\cos0 & -\sin0 \end{pmatrix} + = + \begin{pmatrix} 0 & -1 \\ 1 & \phantom-0 \end{pmatrix} + \end{align*} + \end{block} + } + \end{column} + \begin{column}{0.48\textwidth} + \uncover<3->{ + \begin{block}{Lie-Algebra} + Darstellung von \aso2: + \begin{align*} + \mathbb R + &\to + \aso2 + \\ + t + &\mapsto + \begin{pmatrix} + 0 & -t \\ + t & \phantom-0 + \end{pmatrix} + \end{align*} + \end{block} + } + \end{column} + \end{columns} +\end{frame} + + +\begin{frame}[t] + \setlength{\abovedisplayskip}{5pt} + \setlength{\belowdisplayskip}{5pt} + \frametitle{Von der Lie-Algebra zur -Gruppe} + \vspace{-20pt} + \begin{columns}[t,onlytextwidth] + \begin{column}{0.48\textwidth} + \uncover<1->{ + \begin{block}{Differentialgleichung} + Gegeben: + \[ + J + = + \dot\gamma(0) = \begin{pmatrix} 0 & -1 \\ 1 & \phantom-0 \end{pmatrix} + \] + Gesucht: + \[ \dot \gamma (t) = J \gamma(t) \qquad \gamma \in \gSO2 \] + \[ \Rightarrow \gamma(t) = \exp(Jt) \gamma(0) = \exp(Jt) \] + \end{block} + } + \end{column} + \begin{column}{0.48\textwidth} + \uncover<2->{ + \begin{block}{Lie-Algebra} + Potenzen von $J$: + \begin{align*} + J^2 &= -I & + J^3 &= -J & + J^4 &= I & + \ldots + \end{align*} + \end{block} + } + \end{column} + \end{columns} +\uncover<3->{ + Folglich: + \begin{align*} + \exp(Jt) + &= I + Jt + + J^2\frac{t^2}{2!} + + J^3\frac{t^3}{3!} + + J^4\frac{t^4}{4!} + + J^5\frac{t^5}{5!} + + \ldots \\ + &= \begin{pmatrix} + \vspace*{3pt} + 1 - \frac{t^2}{2} + \frac{t^4}{4!} - \ldots + & + -t + \frac{t^3}{3!} - \frac{t^5}{5!} + \ldots + \\ + t - \frac{t^3}{3!} + \frac{t^5}{5!} - \ldots + & + 1 - \frac{t^2}{2!} + \frac{t^4}{4!} - \ldots + \end{pmatrix} + = + \begin{pmatrix} + \cos t & -\sin t \\ + \sin t & \phantom-\cos t + \end{pmatrix} + \end{align*} + } +\end{frame} +\egroup diff --git a/vorlesungen/slides/10/taylor.tex b/vorlesungen/slides/10/taylor.tex new file mode 100644 index 0000000..8c71965 --- /dev/null +++ b/vorlesungen/slides/10/taylor.tex @@ -0,0 +1,216 @@ +% +% taylor.tex -- Repetition Taylot-Reihen +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% Erstellt durch Roy Seitz +% +% !TeX spellcheck = de_CH +\bgroup + +\begin{frame}[t] + \setlength{\abovedisplayskip}{5pt} + \setlength{\belowdisplayskip}{5pt} + \frametitle{Beispiel $\sin(x)$} + \ifthenelse{\boolean{presentation}}{\vspace{-20pt}}{\vspace{-8pt}} + \begin{block}{Taylor-Approximationen von $\sin(x)$} + \begin{align*} + p_{ + \only<1>{0} + \only<2>{1} + \only<3>{2} + \only<4>{3} + \only<5>{4} + \only<6>{5} + \only<7->{n} + }(x) + &= + \uncover<1->{0} + \uncover<2->{+ x} + \uncover<3->{+ 0 \frac{x^2}{2!}} + \uncover<4->{- 1 \frac{x^3}{3!}} + \uncover<5->{+ 0 \frac{x^4}{4!}} + \uncover<6->{+ 1 \frac{x^5}{5!}} + \uncover<7->{+ \ldots} + \uncover<8->{ + = \sum_{k=0}^{n/2} (-1)^{2k + 1}\frac{x^{2k+1}}{(2k+1)!} + } + \end{align*} + \end{block} + \begin{center} + \begin{tikzpicture}[>=latex,thick,scale=1.3] + \draw[->] (-5.0, 0.0) -- (5.0,0.0) coordinate[label=$x$]; + \draw[->] ( 0.0,-1.5) -- (0.0,1.5); + \clip (-5,-1.5) rectangle (5,1.5); + \draw[domain=-4:4, samples=50, smooth, blue] + plot ({\x}, {sin(180/3.1415968*\x)}) + node[above right] {$\sin(x)$}; + \uncover<1|handout:0>{ + \draw[domain=-4:4, samples=2, smooth, red] + plot ({\x}, {0}) + node[above right] {$p_0(x)$};} + \uncover<2|handout:0>{ + \draw[domain=-1.5:1.5, samples=2, smooth, red] + plot ({\x}, {\x}) + node[below right] {$p_1(x)$};} + \uncover<3|handout:0>{ + \draw[domain=-1.5:1.5, samples=2, smooth, red] + plot ({\x}, {\x}) + node[below right] {$p_2(x)$};} + \uncover<4>{ + \draw[domain=-3:3, samples=50, smooth, red] + plot ({\x}, {\x - \x*\x*\x/6}) + node[above right] {$p_3(x)$};} + \uncover<5|handout:0>{ + \draw[domain=-3:3, samples=50, smooth, red] + plot ({\x}, {\x - \x*\x*\x/6}) + node[above right] {$p_4(x)$};} + \uncover<6|handout:0>{ + \draw[domain=-3.9:3.9, samples=50, smooth, red] + plot ({\x}, {\x - \x*\x*\x/6 + \x*\x*\x*\x*\x/120}) + node[below right] {$p_5(x)$};} + \uncover<7|handout:0>{ + \draw[domain=-3.9:3.9, samples=50, smooth, red] + plot ({\x}, {\x - \x*\x*\x/6 + \x*\x*\x*\x*\x/120}) + node[below right] {$p_6(x)$};} + \uncover<8-|handout:0>{ + \draw[domain=-4:4, samples=50, smooth, red] + plot ({\x}, {\x - \x*\x*\x/6 + \x*\x*\x*\x*\x/120 - + \x*\x*\x*\x*\x*\x*\x/5040}) + node[above right] {$p_7(x)$};} + \end{tikzpicture} + \end{center} +\end{frame} + +\begin{frame}[t] + \setlength{\abovedisplayskip}{5pt} + \setlength{\belowdisplayskip}{5pt} + \frametitle{Taylor-Reihen} + \ifthenelse{\boolean{presentation}}{\vspace{-20pt}}{\vspace{-8pt}} + \begin{block}{Polynom-Approximationen von $f(t)$} + \begin{align*} + p_n(t) + &= + f(0) + \uncover<2->{ + f' (0) t } + \uncover<3->{ + f''(0)\frac{t^2}{2} } + \uncover<4->{ + \ldots + f^{(n)}(0) \frac{t^n}{n!} } + \uncover<5->{ = \sum_{k=0}^{n} f^{(k)} \frac{t^k}{k!} } + \end{align*} + \end{block} + \uncover<6->{ + \begin{block}{Erste $n$ Ableitungen von $f(0)$ und $p_n(0)$ sind gleich!}} + \begin{align*} + \uncover<6->{ p'_n(t) } + & + \uncover<7->{ + = f'(0) + + f''(0)t + + \mathcal O(t^2) + } + &\uncover<8->{\Rightarrow}&& + \uncover<8->{p'_n(0) = f'(0)} + \\ + \uncover<9->{ p''_n(t) } + & + \uncover<10->{ + = f''(0) + + \mathcal O(t) + } + &\uncover<11->{\Rightarrow}&& + \uncover<11->{ p''_n(0) = f''(0) } + \end{align*} + \end{block} + \uncover<12->{ + \begin{block}{Für alle praktisch relevanten Funktionen $f(t)$ gilt:} + \begin{align*} + \lim_{n\to \infty} p_n(t) + = + f(t) + \end{align*} + \end{block} + } +\end{frame} + + +\begin{frame}[t] + \setlength{\abovedisplayskip}{5pt} + \setlength{\belowdisplayskip}{5pt} + \frametitle{Beispiel $e^t$} + \ifthenelse{\boolean{presentation}}{\vspace{-20pt}}{\vspace{-8pt}} + \begin{block}{Taylor-Approximationen von $e^{at}$} + \begin{align*} + p_{ + \only<1>{0} + \only<2>{1} + \only<3>{2} + \only<4>{3} + \only<5>{4} + \only<6>{5} + \only<7->{n} + }(t) + &= + 1 + \uncover<2->{+ a t} + \uncover<3->{+ a^2 \frac{t^2}{2}} + \uncover<4->{+ a^3 \frac{t^3}{3!}} + \uncover<5->{+ a^4 \frac{t^4}{4!}} + \uncover<6->{+ a^5 \frac{t^5}{5!}} + \uncover<7->{+ a^6 \frac{t^6}{6!}} + \uncover<8->{+ \ldots + = \sum_{k=0}^{n} a^k \frac{t^k}{k!}} + \\ + & + \uncover<9->{= \exp(at)} + \end{align*} + \end{block} + \begin{center} + \begin{tikzpicture}[>=latex,thick,scale=1.3] + \draw[->] (-4.0, 0.0) -- (4.0,0.0) coordinate[label=$t$]; + \draw[->] ( 0.0,-0.5) -- (0.0,2.5); + \clip (-3,-0.5) rectangle (3,2.5); + \draw[domain=-4:1, samples=50, smooth, blue] + plot ({\x}, {exp(\x)}) + node[above right] {$\exp(t)$}; + \uncover<1|handout:0>{ + \draw[domain=-4:4, samples=12, smooth, red] + plot ({\x}, {1}) + node[below right] {$p_0(t)$};} + \uncover<2|handout:0>{ + \draw[domain=-4:1.5, samples=10, smooth, red] + plot ({\x}, {1 + \x}) + node[below right] {$p_1(t)$};} + \uncover<3|handout:0>{ + \draw[domain=-4:1, samples=50, smooth, red] + plot ({\x}, {1 + \x + \x*\x/2}) + node[below right] {$p_2(t)$};} + \uncover<4>{ + \draw[domain=-4:1, samples=50, smooth, red] + plot ({\x}, {1 + \x + \x*\x/2 + \x*\x*\x/6}) + node[below right] {$p_3(t)$};} + \uncover<5|handout:0>{ + \draw[domain=-4:0.9, samples=50, smooth, red] + plot ({\x}, {1 + \x + \x*\x/2 + \x*\x*\x/6 + \x*\x*\x*\x/24}) + node[below left] {$p_4(t)$};} + \uncover<6|handout:0>{ + \draw[domain=-4:0.9, samples=50, smooth, red] + plot ({\x}, {1 + \x + \x*\x/2 + \x*\x*\x/6 + \x*\x*\x*\x/24 + + \x*\x*\x*\x*\x/120}) + node[below left] {$p_5(t)$};} + \uncover<7|handout:0>{ + \draw[domain=-4:0.9, samples=50, smooth, red] + plot ({\x}, {1 + \x + \x*\x/2 + \x*\x*\x/6 + \x*\x*\x*\x/24 + + \x*\x*\x*\x*\x/120 + + \x*\x*\x*\x*\x*\x/720}) + node[below left] {$p_6(t)$};} + \uncover<8-|handout:0>{ + \draw[domain=-4:0.9, samples=50, smooth, red] + plot ({\x}, {1 + \x + \x*\x/2 + \x*\x*\x/6 + \x*\x*\x*\x/24 + + \x*\x*\x*\x*\x/120 + + \x*\x*\x*\x*\x*\x/720 + + \x*\x*\x*\x*\x*\x*\x/5040}) + node[below left] {$p_7(t)$};} + \end{tikzpicture} + \end{center} +\end{frame} + +\egroup diff --git a/vorlesungen/slides/10/template.tex b/vorlesungen/slides/10/template.tex new file mode 100644 index 0000000..50f0a3b --- /dev/null +++ b/vorlesungen/slides/10/template.tex @@ -0,0 +1,21 @@ +% +% template.tex -- slide template +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% Erstellt durch Roy Seitz +% +% !TeX spellcheck = de_CH +\bgroup +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Template} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\end{column} +\begin{column}{0.48\textwidth} +\end{column} +\end{columns} +\end{frame} +\egroup diff --git a/vorlesungen/slides/10/vektorfelder.mp b/vorlesungen/slides/10/vektorfelder.mp new file mode 100644 index 0000000..e63b2d5 --- /dev/null +++ b/vorlesungen/slides/10/vektorfelder.mp @@ -0,0 +1,361 @@ +% +% Stroemungsfelder linearer Differentialgleichungen +% +% (c) 2015 Prof Dr Andreas Mueller, Hochschule Rapperswil +% 2021-04-14, Roy Seitz, Copied for SeminarMatrizen +% +verbatimtex +\documentclass{book} +\usepackage{times} +\usepackage{amsmath} +\usepackage{amssymb} +\usepackage{amsfonts} +\usepackage{txfonts} +\begin{document} +etex; + +input TEX; + +TEXPRE("%&latex" & char(10) & +"\documentclass{book}" & +"\usepackage{times}" & +"\usepackage{amsmath}" & +"\usepackage{amssymb}" & +"\usepackage{amsfonts}" & +"\usepackage{txfonts}" & +"\begin{document}"); +TEXPOST("\end{document}"); + +% +% Vektorfeld in der Ebene mit Lösungskurve +% so(2) +% +beginfig(1) + +% Scaling parameter +numeric unit; +unit := 150; + +% Some points +z1 = (-1.5, 0) * unit; +z2 = ( 1.5, 0) * unit; +z3 = ( 0, -1.5) * unit; +z4 = ( 0, 1.5) * unit; + +pickup pencircle scaled 1pt; +drawarrow (z1 shifted (-10,0))--(z2 shifted (10,0)); +drawarrow (z3 shifted (0,-10))--(z4 shifted (0,10)); +label.top(btex $x_1$ etex, z2 shifted (10,0)); +label.rt(btex $x_2$ etex, z4 shifted (0,10)); + +% % Draw circles +% for x = 0.2 step 0.2 until 1.4: +% path p; +% p = (x,0); +% for a = 5 step 5 until 355: +% p := p--(x*cosd(a), x*sind(a)); +% endfor; +% p := p--cycle; +% pickup pencircle scaled 1pt; +% draw p scaled unit withcolor red; +% endfor; + +% Define DGL +def dglField(expr x, y) = + %(-0.5 * (x + y), -0.5 * (y - x)) + (-y, x) +enddef; + +pair A; +A := (1, 0); +draw A scaled unit withpen pencircle scaled 8bp withcolor red; + +% Draw arrows for each grid point +pickup pencircle scaled 0.5pt; +for x = -1.5 step 0.1 until 1.55: + for y = -1.5 step 0.1 until 1.55: + drawarrow ((x, y) * unit) + --(((x,y) * unit) shifted (8 * dglField(x,y))) + withcolor blue; + endfor; +endfor; + +endfig; + +% +% Vektorfeld in der Ebene mit Lösungskurve +% Euler(1) +% +beginfig(2) + +numeric unit; +unit := 150; + +z0 = ( 0, 0); +z1 = (-1.5, 0) * unit; +z2 = ( 1.5, 0) * unit; +z3 = ( 0, -1.5) * unit; +z4 = ( 0, 1.5) * unit; + +pickup pencircle scaled 1pt; +drawarrow (z1 shifted (-10,0))--(z2 shifted (10,0)); +drawarrow (z3 shifted (0,-10))--(z4 shifted (0,10)); +label.top(btex $x_1$ etex, z2 shifted (10,0)); +label.rt(btex $x_2$ etex, z4 shifted (0,10)); + +def dglField(expr x, y) = + (-y, x) +enddef; + +def dglFieldp(expr z) = + dglField(xpart z, ypart z) +enddef; + +def curve(expr z, l, s) = + path p; + p := z; + for t = 0 step 1 until l: + p := p--((point (length p) of p) shifted (s * dglFieldp(point (length p) of p))); + endfor; + draw p scaled unit withcolor red; +enddef; + +pair A; +A := (1, 0); +draw A scaled unit withpen pencircle scaled 8bp withcolor red; +curve(A, 0, 1); + +% Draw arrows for each grid point +pickup pencircle scaled 0.5pt; +for x = -1.5 step 0.1 until 1.55: + for y = -1.5 step 0.1 until 1.55: + drawarrow ((x, y) * unit) + --(((x,y) * unit) shifted (8 * dglField(x,y))) + withcolor blue; + endfor; +endfor; + +endfig; + +% +% Vektorfeld in der Ebene mit Lösungskurve +% Euler(2) +% +beginfig(3) + +numeric unit; +unit := 150; + +z0 = ( 0, 0); +z1 = (-1.5, 0) * unit; +z2 = ( 1.5, 0) * unit; +z3 = ( 0, -1.5) * unit; +z4 = ( 0, 1.5) * unit; + +pickup pencircle scaled 1pt; +drawarrow (z1 shifted (-10,0))--(z2 shifted (10,0)); +drawarrow (z3 shifted (0,-10))--(z4 shifted (0,10)); +label.top(btex $x_1$ etex, z2 shifted (10,0)); +label.rt(btex $x_2$ etex, z4 shifted (0,10)); + +def dglField(expr x, y) = + (-y, x) +enddef; + +def dglFieldp(expr z) = + dglField(xpart z, ypart z) +enddef; + +def curve(expr z, l, s) = + path p; + p := z; + for t = 0 step 1 until l: + p := p--((point (length p) of p) shifted (s * dglFieldp(point (length p) of p))); + endfor; + draw p scaled unit withcolor red; +enddef; + +pair A; +A := (1, 0); +draw A scaled unit withpen pencircle scaled 8bp withcolor red; +curve(A, 1, 0.5); + +% Draw arrows for each grid point +pickup pencircle scaled 0.5pt; +for x = -1.5 step 0.1 until 1.55: + for y = -1.5 step 0.1 until 1.55: + drawarrow ((x, y) * unit) + --(((x,y) * unit) shifted (8 * dglField(x,y))) + withcolor blue; + endfor; +endfor; + +endfig; + +% +% Vektorfeld in der Ebene mit Lösungskurve +% Euler(3) +% +beginfig(4) + +numeric unit; +unit := 150; + +z0 = ( 0, 0); +z1 = (-1.5, 0) * unit; +z2 = ( 1.5, 0) * unit; +z3 = ( 0, -1.5) * unit; +z4 = ( 0, 1.5) * unit; + +pickup pencircle scaled 1pt; +drawarrow (z1 shifted (-10,0))--(z2 shifted (10,0)); +drawarrow (z3 shifted (0,-10))--(z4 shifted (0,10)); +label.top(btex $x_1$ etex, z2 shifted (10,0)); +label.rt(btex $x_2$ etex, z4 shifted (0,10)); + +def dglField(expr x, y) = + (-y, x) +enddef; + +def dglFieldp(expr z) = + dglField(xpart z, ypart z) +enddef; + +def curve(expr z, l, s) = + path p; + p := z; + for t = 0 step 1 until l: + p := p--((point (length p) of p) shifted (s * dglFieldp(point (length p) of p))); + endfor; + draw p scaled unit withcolor red; +enddef; + +pair A; +A := (1, 0); +draw A scaled unit withpen pencircle scaled 8bp withcolor red; +curve(A, 3, 0.25); + +% Draw arrows for each grid point +pickup pencircle scaled 0.5pt; +for x = -1.5 step 0.1 until 1.55: + for y = -1.5 step 0.1 until 1.55: + drawarrow ((x, y) * unit) + --(((x,y) * unit) shifted (8 * dglField(x,y))) + withcolor blue; + endfor; +endfor; + +endfig; + +% +% Vektorfeld in der Ebene mit Lösungskurve +% Euler(4) +% +beginfig(5) + +numeric unit; +unit := 150; + +z0 = ( 0, 0); +z1 = (-1.5, 0) * unit; +z2 = ( 1.5, 0) * unit; +z3 = ( 0, -1.5) * unit; +z4 = ( 0, 1.5) * unit; + +pickup pencircle scaled 1pt; +drawarrow (z1 shifted (-10,0))--(z2 shifted (10,0)); +drawarrow (z3 shifted (0,-10))--(z4 shifted (0,10)); +label.top(btex $x_1$ etex, z2 shifted (10,0)); +label.rt(btex $x_2$ etex, z4 shifted (0,10)); + +def dglField(expr x, y) = + (-y, x) +enddef; + +def dglFieldp(expr z) = + dglField(xpart z, ypart z) +enddef; + +def curve(expr z, l, s) = + path p; + p := z; + for t = 0 step 1 until l: + p := p--((point (length p) of p) shifted (s * dglFieldp(point (length p) of p))); + endfor; + draw p scaled unit withcolor red; +enddef; + +pair A; +A := (1, 0); +draw A scaled unit withpen pencircle scaled 8bp withcolor red; +curve(A, 7, 0.125); + +% Draw arrows for each grid point +pickup pencircle scaled 0.5pt; +for x = -1.5 step 0.1 until 1.55: + for y = -1.5 step 0.1 until 1.55: + drawarrow ((x, y) * unit) + --(((x,y) * unit) shifted (8 * dglField(x,y))) + withcolor blue; + endfor; +endfor; + +endfig; + +% +% Vektorfeld in der Ebene mit Lösungskurve +% Euler(5) +% +beginfig(6) + +numeric unit; +unit := 150; + +z0 = ( 0, 0); +z1 = (-1.5, 0) * unit; +z2 = ( 1.5, 0) * unit; +z3 = ( 0, -1.5) * unit; +z4 = ( 0, 1.5) * unit; + +pickup pencircle scaled 1pt; +drawarrow (z1 shifted (-10,0))--(z2 shifted (10,0)); +drawarrow (z3 shifted (0,-10))--(z4 shifted (0,10)); +label.top(btex $x_1$ etex, z2 shifted (10,0)); +label.rt(btex $x_2$ etex, z4 shifted (0,10)); + +def dglField(expr x, y) = + (-y, x) +enddef; + +def dglFieldp(expr z) = + dglField(xpart z, ypart z) +enddef; + +def curve(expr z, l, s) = + path p; + p := z; + for t = 0 step 1 until l: + p := p--((point (length p) of p) shifted (s * dglFieldp(point (length p) of p))); + endfor; + draw p scaled unit withcolor red; +enddef; + +pair A; +A := (1, 0); +draw A scaled unit withpen pencircle scaled 8bp withcolor red; +curve(A, 99, 0.01); + +% Draw arrows for each grid point +pickup pencircle scaled 0.5pt; +for x = -1.5 step 0.1 until 1.55: + for y = -1.5 step 0.1 until 1.55: + drawarrow ((x, y) * unit) + --(((x,y) * unit) shifted (8 * dglField(x,y))) + withcolor blue; + endfor; +endfor; + +endfig; + + +end; diff --git a/vorlesungen/slides/10/vektorfelder.tex b/vorlesungen/slides/10/vektorfelder.tex new file mode 100644 index 0000000..3ba7cda --- /dev/null +++ b/vorlesungen/slides/10/vektorfelder.tex @@ -0,0 +1,82 @@ +% +% iterativ.tex -- Iterative Approximation in \dot x = J x +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% Erstellt durch Roy Seitz +% +% !TeX spellcheck = de_CH +\bgroup +\begin{frame}[t] + \setlength{\abovedisplayskip}{5pt} + \setlength{\belowdisplayskip}{5pt} + \frametitle{Als Strömungsfeld} + \vspace{-20pt} + \begin{columns}[t,onlytextwidth] + \begin{column}{0.48\textwidth} + \vfil + \only<1|handout:0>{ + \includegraphics[width=\linewidth,keepaspectratio] + {../slides/10/vektorfelder-1.pdf} + } + \only<2|handout:0>{ + \includegraphics[width=\linewidth,keepaspectratio] + {../slides/10/vektorfelder-2.pdf} + } + \only<3>{ + \includegraphics[width=\linewidth,keepaspectratio] + {../slides/10/vektorfelder-3.pdf} + } + \only<4|handout:0>{ + \includegraphics[width=\linewidth,keepaspectratio] + {../slides/10/vektorfelder-4.pdf} + } + \only<5|handout:0>{ + \includegraphics[width=\linewidth,keepaspectratio] + {../slides/10/vektorfelder-5.pdf} + } + \only<6-|handout:0>{ + \includegraphics[width=\linewidth,keepaspectratio] + {../slides/10/vektorfelder-6.pdf} + } + \vfil + \end{column} + \begin{column}{0.48\textwidth} + \begin{block}{Differentialgleichung} + \[ + \dot x(t) = J x(t) + \quad + J = \begin{pmatrix} 0 & -1 \\ 1 & \phantom-0 \end{pmatrix} + \quad + x_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix} + \] + \end{block} + + \only<2|handout:0>{ + Nach einem Schritt der Länge $t$: + \[ + x(t) = x_0 + \dot x t = x_0 + Jx_0t = (1 + Jt)x_0 + \] + } + + \only<3|handout:0>{ + Nach zwei Schritten der Länge $t/2$: + \[ + x(t) = \left(1 + \frac{Jt}{2}\right)^2x_0 + \] + } + + \only<4->{ + Nach n Schritten der Länge $t/n$: + \[ + x(t) = \left(1 + \frac{Jt}{n}\right)^nx_0 + \] + } + \only<6->{ + \[ + \lim_{n\to\infty}\left(1 + \frac{At}{n}\right)^n = \exp(At) + \] + } + \end{column} + \end{columns} +\end{frame} +\egroup diff --git a/vorlesungen/slides/5/potenzreihenmethode.tex b/vorlesungen/slides/5/potenzreihenmethode.tex index 0c3503d..12d3fa5 100644 --- a/vorlesungen/slides/5/potenzreihenmethode.tex +++ b/vorlesungen/slides/5/potenzreihenmethode.tex @@ -79,7 +79,7 @@ a_k=\frac1{k!}a^kC} \\ \uncover<4->{ \Rightarrow y(x) &= C}\uncover<8->{+Cax}\uncover<9->{ + C\frac12(ax)^2} -\uncover<10->{ + C \frac16(ac)^3} +\uncover<10->{ + C \frac16(ax)^3} \uncover<11->{ + \dots+C\frac{1}{k!}(ax)^k+\dots} \ifthenelse{\boolean{presentation}}{ \only<12>{ diff --git a/vorlesungen/slides/Makefile.inc b/vorlesungen/slides/Makefile.inc index e2271b8..0f5fa8c 100644 --- a/vorlesungen/slides/Makefile.inc +++ b/vorlesungen/slides/Makefile.inc @@ -12,7 +12,8 @@ include ../slides/5/Makefile.inc include ../slides/7/Makefile.inc include ../slides/8/Makefile.inc include ../slides/9/Makefile.inc +include ../slides/a/Makefile.inc slides = \ $(chapter0) $(chapter1) $(chapter2) $(chapter3) $(chapter4) \ - $(chapter5) $(chapter7) $(chapter8) $(chapter9) + $(chapter5) $(chapter7) $(chapter8) $(chapter9) $(chaptera) diff --git a/vorlesungen/slides/a/Makefile.inc b/vorlesungen/slides/a/Makefile.inc new file mode 100644 index 0000000..0c7ab0b --- /dev/null +++ b/vorlesungen/slides/a/Makefile.inc @@ -0,0 +1,25 @@ +# +# Makefile.inc -- additional depencencies +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +chaptera = \ + ../slides/a/dc/prinzip.tex \ + ../slides/a/dc/effizient.tex \ + ../slides/a/dc/beispiel.tex \ + \ + ../slides/a/ecc/gruppendh.tex \ + ../slides/a/ecc/kurve.tex \ + ../slides/a/ecc/inverse.tex \ + ../slides/a/ecc/operation.tex \ + ../slides/a/ecc/quadrieren.tex \ + ../slides/a/ecc/oakley.tex \ + \ + ../slides/a/aes/bytes.tex \ + ../slides/a/aes/sinverse.tex \ + ../slides/a/aes/blocks.tex \ + ../slides/a/aes/keys.tex \ + ../slides/a/aes/runden.tex \ + \ + ../slides/a/chapter.tex + diff --git a/vorlesungen/slides/a/aes/blocks.tex b/vorlesungen/slides/a/aes/blocks.tex new file mode 100644 index 0000000..9e95a86 --- /dev/null +++ b/vorlesungen/slides/a/aes/blocks.tex @@ -0,0 +1,193 @@ +% +% blocks.tex -- slide template +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\def\s{0.4} +\def\punkt#1#2{({#1*\s},{(3-#2)*\s})} +\def\feld#1#2#3{ + \fill[color=#3] \punkt{(#1-0.5)}{(#2+0.5)} + rectangle \punkt{(#1+0.5)}{(#2-0.5)}; +} +\definecolor{darkgreen}{rgb}{0,0.6,0} +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Blocks} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{block}{Blocks} +$4\times k$ Matrizen mit $k=4,\dots,8$ +\begin{center} +\begin{tikzpicture}[>=latex,thick] +\xdef\s{0.4} +\foreach \i in {0,...,31}{ + \pgfmathparse{mod(\i,4)} + \xdef\y{\pgfmathresult} + \pgfmathparse{int(\i/4)} + \xdef\x{\pgfmathresult} + \node at \punkt{\x}{\y} {\tiny $\i$}; +} +\foreach \x in {-0.5,0.5,...,7.5}{ + \draw \punkt{\x}{-0.5} -- \punkt{\x}{3.5}; +} +\foreach \y in {-0.5,0.5,...,3.5}{ + \draw \punkt{-0.5}{\y} -- \punkt{7.5}{\y}; +} +\end{tikzpicture} +\end{center} +\uncover<2->{% +Spalten sind $4$-dimensionale $\mathbb{F}_{2^8}$-Vektoren +} +\end{block} +\uncover<3->{% +\begin{block}{Zeilenshift} +\begin{center} +\begin{tikzpicture}[>=latex,thick] + +\xdef\s{0.35} + +\begin{scope} + \feld{0}{3}{red!20} + \feld{0}{2}{red!20} + \feld{0}{1}{red!20} + \feld{0}{0}{red!20} + + \feld{1}{3}{red!10} + \feld{1}{2}{red!10} + \feld{1}{1}{red!10} + \feld{1}{0}{red!10} + + \feld{2}{3}{yellow!20} + \feld{2}{2}{yellow!20} + \feld{2}{1}{yellow!20} + \feld{2}{0}{yellow!20} + + \feld{3}{3}{yellow!10} + \feld{3}{2}{yellow!10} + \feld{3}{1}{yellow!10} + \feld{3}{0}{yellow!10} + + \feld{4}{3}{darkgreen!20} + \feld{4}{2}{darkgreen!20} + \feld{4}{1}{darkgreen!20} + \feld{4}{0}{darkgreen!20} + + \feld{5}{3}{darkgreen!10} + \feld{5}{2}{darkgreen!10} + \feld{5}{1}{darkgreen!10} + \feld{5}{0}{darkgreen!10} + + \feld{6}{3}{blue!20} + \feld{6}{2}{blue!20} + \feld{6}{1}{blue!20} + \feld{6}{0}{blue!20} + + \feld{7}{3}{blue!10} + \feld{7}{2}{blue!10} + \feld{7}{1}{blue!10} + \feld{7}{0}{blue!10} + + \foreach \x in {-0.5,0.5,...,7.5}{ + \draw \punkt{\x}{-0.5} -- \punkt{\x}{3.5}; + } + \foreach \y in {-0.5,0.5,...,3.5}{ + \draw \punkt{-0.5}{\y} -- \punkt{7.5}{\y}; + } +\end{scope} + +\begin{scope}[xshift=3.5cm] + \feld{0}{0}{red!20} + \feld{1}{1}{red!20} + \feld{2}{2}{red!20} + \feld{3}{3}{red!20} + + \feld{1}{0}{red!10} + \feld{2}{1}{red!10} + \feld{3}{2}{red!10} + \feld{4}{3}{red!10} + + \feld{2}{0}{yellow!20} + \feld{3}{1}{yellow!20} + \feld{4}{2}{yellow!20} \feld{5}{3}{yellow!20} + + \feld{3}{0}{yellow!10} + \feld{4}{1}{yellow!10} + \feld{5}{2}{yellow!10} + \feld{6}{3}{yellow!10} + + \feld{4}{0}{darkgreen!20} + \feld{5}{1}{darkgreen!20} + \feld{6}{2}{darkgreen!20} + \feld{7}{3}{darkgreen!20} + + \feld{5}{0}{darkgreen!10} + \feld{6}{1}{darkgreen!10} + \feld{7}{2}{darkgreen!10} + \feld{0}{3}{darkgreen!10} + + \feld{6}{0}{blue!20} + \feld{7}{1}{blue!20} + \feld{0}{2}{blue!20} + \feld{1}{3}{blue!20} + + \feld{7}{0}{blue!10} + \feld{0}{1}{blue!10} + \feld{1}{2}{blue!10} + \feld{2}{3}{blue!10} + + \foreach \x in {-0.5,0.5,...,7.5}{ + \draw \punkt{\x}{-0.5} -- \punkt{\x}{3.5}; + } + \foreach \y in {-0.5,0.5,...,3.5}{ + \draw \punkt{-0.5}{\y} -- \punkt{7.5}{\y}; + } + + \node at \punkt{-1.5}{1.5} {$\rightarrow$}; +\end{scope} + +\end{tikzpicture} +\end{center} +\end{block}} +\end{column} +\begin{column}{0.50\textwidth} +\uncover<4->{% +\begin{block}{Spalten mischen} +Lineare Operation auf Spaltenvektoren mit Matrix +\begin{align*} +C&=\begin{pmatrix} +\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}\\ +\texttt{01}_{16}&\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}\\ +\texttt{01}_{16}&\texttt{01}_{16}&\texttt{02}_{16}&\texttt{03}_{16}\\ +\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}&\texttt{02}_{16} +\end{pmatrix} +\\ +\uncover<5->{ +\det C +&= +\texttt{0a}_{16} +} +\uncover<6->{ +\ne 0} +\uncover<7->{ +\quad\Rightarrow\quad \exists C^{-1} +} +\end{align*} +\end{block}} +\uncover<8->{% +\begin{block}{Als Polynommultiplikation} +Spalten = Polynome in $\mathbb{F}_{2^8}[Z]/(Z^4-1)$, +\\ +\uncover<9->{% +$C=\mathstrut$ Multiplikation mit +\[ +c(Z) = \texttt{03}_{16}Z^3 + Z^2 + Z + \texttt{02}_{16} +\] +} +\end{block}} +\end{column} +\end{columns} +\end{frame} +\egroup diff --git a/vorlesungen/slides/a/aes/bytes.tex b/vorlesungen/slides/a/aes/bytes.tex new file mode 100644 index 0000000..e873e9a --- /dev/null +++ b/vorlesungen/slides/a/aes/bytes.tex @@ -0,0 +1,96 @@ +% +% bytes.tex -- slide template +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Bytes} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{block}{Endlicher Körper} +1 Byte = 8 bits: $\mathbb{F}_{2^8}$ +mit Minimalpolynom: +\[ +m(X) = X^8+X^4+X^3+X+1 +\] +\end{block} +\vspace{-10pt} +\uncover<2->{% +\begin{block}{Inverse $a^{-1}$} +Mit dem euklidischen Algorithmus +\[ +\begin{aligned} +sa+tm&=1 +&&\Rightarrow& +\uncover<3->{ +a^{-1} &= s} +\\ +& +&&& +\uncover<4->{ +\overline{a} +&= +\begin{cases} +a^{-1}&\; a\ne 0\\ +0 &\; a = 0 +\end{cases}} +\end{aligned} +\] +\end{block}} +\vspace{-10pt} +\uncover<5->{% +\begin{block}{Vektorraum} +$\mathbb{R}_{2^8}$ +ist ein $8$-dimensionaler $\mathbb{F}_2$-Vektorraum +\end{block}} +\end{column} +\begin{column}{0.48\textwidth} +\uncover<6->{% +\begin{block}{S-Box} +$S\colon a\mapsto A\overline{a}+q$ mit +\begin{align*} +\only<1-7>{\phantom{\mathstrut^{-1}}A} +\ifthenelse{\boolean{presentation}}{}{\only<8>{A^{-1}}} +&=\only<1-7>{\begin{pmatrix} +1&0&0&0&1&1&1&1\\ +1&1&0&0&0&1&1&1\\ +1&1&1&0&0&0&1&1\\ +1&1&1&1&0&0&0&1\\ +1&1&1&1&1&0&0&0\\ +0&1&1&1&1&1&0&0\\ +0&0&1&1&1&1&1&0\\ +0&0&0&1&1&1&1&1 +\end{pmatrix}} +\ifthenelse{\boolean{presentation}}{}{ +\only<8->{ +\begin{pmatrix} +0&0&1&0&0&1&0&1\\ +1&0&0&1&0&0&1&0\\ +0&1&0&0&1&0&0&1\\ +1&0&1&0&0&1&0&0\\ +0&1&0&1&0&0&1&0\\ +0&0&1&0&1&0&0&1\\ +1&0&0&1&0&1&0&0\\ +0&1&0&0&1&0&1&0 +\end{pmatrix}} +} +\\ +q&=X^7+X^6+X+1 +\end{align*} +\end{block}} +\vspace{-10pt} +\uncover<7->{% +\begin{block}{Inverse $S$-Box} +\vspace{-10pt} +\[ +S^{-1}(b) = \overline{A^{-1}(b-q)} +\] +\end{block}} +\end{column} +\end{columns} +\end{frame} +\egroup diff --git a/vorlesungen/slides/a/aes/keys.tex b/vorlesungen/slides/a/aes/keys.tex new file mode 100644 index 0000000..d2ab712 --- /dev/null +++ b/vorlesungen/slides/a/aes/keys.tex @@ -0,0 +1,36 @@ +% +% keys.tex -- slide template +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Schlüsselerzeugung} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{center} +\includegraphics[width=\textwidth]{../../buch/chapters/90-crypto/images/keys.pdf} +\end{center} +\end{column} +\begin{column}{0.48\textwidth} +\begin{block}{Algorithmus} +\begin{enumerate} +\item<2-> +Startblock: begebener Schlüssel +\item<3-> +Zeilenpermutation: +$\pi=\mathstrut$ Multiplikation mit $Z^3=Z^{-1}$ +\item<4-> $S$-Box +\item<5-> $r_i$: Addition einer Konstanten +\[ +r_i = (\texttt{02}_{16})^{i-1} +\] +\end{enumerate} +\end{block} +\end{column} +\end{columns} +\end{frame} +\egroup diff --git a/vorlesungen/slides/a/aes/runden.tex b/vorlesungen/slides/a/aes/runden.tex new file mode 100644 index 0000000..570b577 --- /dev/null +++ b/vorlesungen/slides/a/aes/runden.tex @@ -0,0 +1,47 @@ +% +% runden.tex -- slide template +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{$n$ Runden} +\vspace{-23pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{block}{Verschlüsselung} +In Runde $i=0,\dots,n-1$ +\begin{enumerate} +\item<2-> Wende die $S$-Box auf alle Bytes des Blocks an +\item<3-> Führe den Zeilenschift durch +\item<4-> Mische die Spalten +\item<5-> Berechne den Schlüsselblock $i$ ($i=0$: ursprünglicher Schlüssel) +\item<6-> Addiere (XOR) den Rundenschlüssel +\end{enumerate} +\end{block} +\end{column} +\begin{column}{0.48\textwidth} +\uncover<7->{% +\begin{block}{Entschlüsselung} +In Runde $i=0,\dots,n-1$ +\begin{enumerate} +\item<8-> Addiere den Rundenschlüssel $n-1-i$ +\item<9-> Invertiere Spaltenmischung (mit $C^{-1}$) +\item<10-> Invertiere den Zeilenshift +\item<11-> Wende $S^{-1}$ an auf jedes Byte +\end{enumerate} +\end{block}} +\end{column} +\end{columns} +\uncover<12->{% +\begin{block}{Charakteristika} +\begin{itemize} +\item<13-> Invertierbar +\item<14-> Skalierbar: beliebig grosse Blöcke (Vielfache von 32\,bit) +\item<15-> Keine ``magischen'' Schritte +\end{itemize} +\end{block}} +\end{frame} +\egroup diff --git a/vorlesungen/slides/a/aes/sinverse.tex b/vorlesungen/slides/a/aes/sinverse.tex new file mode 100644 index 0000000..059100e --- /dev/null +++ b/vorlesungen/slides/a/aes/sinverse.tex @@ -0,0 +1,15 @@ +% +% sinverse.tex -- slide template +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Inverse $S$-Box} +\begin{center} +\includegraphics[width=\textwidth]{../../buch/chapters/90-crypto/images/sbox.pdf} +\end{center} +\end{frame} +\egroup diff --git a/vorlesungen/slides/a/chapter.tex b/vorlesungen/slides/a/chapter.tex new file mode 100644 index 0000000..78eec84 --- /dev/null +++ b/vorlesungen/slides/a/chapter.tex @@ -0,0 +1,23 @@ +% +% chapter.tex +% +% (c) 2021 Prof Dr Andreas Müller, Hochschule Rapperswi +% + +\folie{a/dc/prinzip.tex} +\folie{a/dc/effizient.tex} +\folie{a/dc/beispiel.tex} + +\folie{a/ecc/gruppendh.tex} +\folie{a/ecc/kurve.tex} +\folie{a/ecc/inverse.tex} +\folie{a/ecc/operation.tex} +\folie{a/ecc/quadrieren.tex} +\folie{a/ecc/oakley.tex} + +\folie{a/aes/bytes.tex} +\folie{a/aes/sinverse.tex} +\folie{a/aes/blocks.tex} +\folie{a/aes/keys.tex} +\folie{a/aes/runden.tex} + 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 diff --git a/vorlesungen/slides/a/ecc/gruppendh.tex b/vorlesungen/slides/a/ecc/gruppendh.tex new file mode 100644 index 0000000..13d85c8 --- /dev/null +++ b/vorlesungen/slides/a/ecc/gruppendh.tex @@ -0,0 +1,51 @@ +% +% template.tex -- slide template +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Diffie-Hellmann verallgemeinern} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{block}{Diffie-Hellman in $\mathbb{F}_p$\strut} +\begin{enumerate} +\item<2-> Parteien einigen sich auf $g\in \mathbb{F}_p$, $g\ne 0$, $g\ne 1$ +\item<3-> $A$ und $B$ wählen Exponenten $a,b\in \mathbb{N}$ +\item<4-> Parteien tauschen $u=g^a$ und $v=g^b$ aus +\item<5-> Parteien berechnen $v^a$ und $u^b$ +\[ +v^a = (g^b)^a = g^{ab} =(g^a)^b = u^b +\] +gemeinsamer privater Schlüssel +\end{enumerate} +\end{block} +\uncover<11->{% +{\usebeamercolor[fg]{title}Spezialfall:} $G=\mathbb{F}_p^*$ +} +\end{column} +\begin{column}{0.48\textwidth} +\uncover<6->{% +\begin{block}{Diffie-Hellmann in $G$\strut} +\begin{enumerate} +\item<7-> Parteien einigen sich auf $g\in G$, $g\ne e$ +\item<8-> $A$ und $B$ wählen Exponenten $a,b\in \mathbb{N}$ +\item<9-> Parteien tauschen $u=g^a$ und $v=g^b$ aus +\item<10-> Parteien berechnen $v^a$ und $u^b$ +\[ +v^a = (g^b)^a = g^{ab} =(g^a)^b = u^b +\] +gemeinsamer privater Schlüssel +\end{enumerate} +\end{block}} +\uncover<12->{% +{\usebeamercolor[fg]{title}Idee:} Wähle effizient zu berechnende, ``grosse'' +Gruppen, mit ``komplizierter'' Multiplikation +} +\end{column} +\end{columns} +\end{frame} +\egroup diff --git a/vorlesungen/slides/a/ecc/inverse.tex b/vorlesungen/slides/a/ecc/inverse.tex new file mode 100644 index 0000000..c50f698 --- /dev/null +++ b/vorlesungen/slides/a/ecc/inverse.tex @@ -0,0 +1,48 @@ +% +% inverse.tex -- slide template +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Involution/Inverse} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{center} +\includegraphics[width=\textwidth]{../../buch/chapters/90-crypto/images/elliptic.pdf} +\end{center} +\end{column} +\begin{column}{0.48\textwidth} +\begin{block}{In speziellen Koordinaten} +\vspace{-12pt} +\[ +v^2 = u^3+Au+B +\] +\uncover<2->{invariant unter $v\mapsto -v$}% +\\ +\uncover<3->{{\color{red}geht nicht in $\mathbb{F}_2$}} +\end{block} +\uncover<4->{% +\begin{block}{Allgemein} +\vspace{-12pt} +\begin{align*} +Y^2+XY &= X^3 + aX+b +\\ +\uncover<5->{% +Y(Y+X) &= X^3 + aX + b} +\end{align*} +\uncover<6->{invariant unter} +\begin{align*} +\uncover<7->{X&\mapsto X,& Y&\mapsto -X-Y} +\\ +\uncover<8->{&&\Rightarrow X+Y&\mapsto -Y} +\end{align*} +\uncover<9->{Spezialfall $\mathbb{F}_2$: $Y\leftrightarrow X+Y$} +\end{block}} +\end{column} +\end{columns} +\end{frame} +\egroup diff --git a/vorlesungen/slides/a/ecc/kurve.tex b/vorlesungen/slides/a/ecc/kurve.tex new file mode 100644 index 0000000..04d15f8 --- /dev/null +++ b/vorlesungen/slides/a/ecc/kurve.tex @@ -0,0 +1,56 @@ +% +% kurve.tex -- elliptische Kurven +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Elliptische Kurven} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{center} +\uncover<5->{% +\includegraphics[width=\textwidth]{../../buch/chapters/90-crypto/images/elliptic.pdf} +} +\end{center} +\end{column} +\begin{column}{0.48\textwidth} +\begin{block}{Allgemein} +mit $a,b\in\Bbbk$ +\[ +Y^2 + XY = X^3 + aX + b +\] +\end{block} +\vspace{-10pt} +\uncover<2->{% +\begin{block}{Spezielle Parametrisierung} +\vspace{-10pt} +\begin{align*} +Y^2 + XY + \frac14X^2 +&= +X^3 + \frac14X^2 + aX + b +\\ +\uncover<3->{ +(Y+\frac12X)^2 +&= +X^3 + \frac14X^2 + aX + b +}\\ +\uncover<4->{ +v^2 +&= +u^3+Au+B} +\end{align*} +\uncover<4->{mit +\[ +v=Y+{\textstyle\frac12}X, +\qquad +u=X-\frac1{12} +\]} +\end{block}} +\end{column} +\end{columns} +\end{frame} +\egroup diff --git a/vorlesungen/slides/a/ecc/oakley.tex b/vorlesungen/slides/a/ecc/oakley.tex new file mode 100644 index 0000000..6980c10 --- /dev/null +++ b/vorlesungen/slides/a/ecc/oakley.tex @@ -0,0 +1,85 @@ +% +% oakley.tex -- Oakley Gruppen +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Oakley-Gruppen} +\only<1>{% +\small +\verbatiminput{../slides/a/ecc/oakley1.txt} +$\approx 1.55252\cdot 10^{231}$ +} +\only<2>{% +\begin{block}{$\mathbb{F}_p$} +Endlicher Körper mit $p = $ +\verbatiminput{../slides/a/ecc/prime1.txt} +\end{block} +} +\only<3>{% +\small +\verbatiminput{../slides/a/ecc/oakley2.txt} +} +\only<4>{% +\begin{block}{$\mathbb{F}_p$} +Endlicher Körper mit $p = $ +\verbatiminput{../slides/a/ecc/prime2.txt} +$\approx 1.7977\cdot 10^{308}$ +\end{block} +} +\only<5>{% +\small +\verbatiminput{../slides/a/ecc/oakley3.txt} +} +\only<6>{% +\begin{block}{Oakley Gruppe 3} +\begin{align*} +m(x) &= x^{155} + x^{62} + 1 +\\ +a &= 0 +\\ +b &= \texttt{0x07338f} +\\ +g_x &= 0x7b = x^6 + x^5 + x^4 + x^3 + x + 1 +\\ +&= +x^{18}+x^{17}+x^{16} ++ +x^{13}+x^{12} ++ +x^{9}+x^{8}+x^{7} ++ +x^{3}+x^{1}+x^{1}+1 +\\ +|G|&=45671926166590716193865565914344635196769237316 = 4.5672\cdot 10^{46} +\\ +\log_2|G|&=155\,\text{bit} +\end{align*} +\end{block}} +\only<7>{% +\small +\verbatiminput{../slides/a/ecc/oakley4.txt} +} +\only<8>{% +\begin{block}{Oakley Gruppe 4} +\begin{align*} +m(x) &= x^{185} + x^{69} + 1 +\\ +a &= 0 +\\ +b &= \texttt{0x1ee9} = x^{12} + x^{11}+x^{10}+x^9 + x^7+x^6+x^5 + x^3+1 +\\ +g_x &= \texttt{0x18} = x^4+x^3 +\\ +|G| &= 49039857307708443467467104857652682248052385001045053116 +\\ +&= 4.9040\cdot 10^{55} +\\ +\log_2|G| &= 185 +\end{align*} +\end{block}} +\end{frame} +\egroup diff --git a/vorlesungen/slides/a/ecc/oakley1.txt b/vorlesungen/slides/a/ecc/oakley1.txt new file mode 100644 index 0000000..4cc31ae --- /dev/null +++ b/vorlesungen/slides/a/ecc/oakley1.txt @@ -0,0 +1,14 @@ +6.1 First Oakley Default Group + + Oakley implementations MUST support a MODP group with the following + prime and generator. This group is assigned id 1 (one). + + The prime is: 2^768 - 2 ^704 - 1 + 2^64 * { [2^638 pi] + 149686 } + Its hexadecimal value is + + FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1 + 29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD + EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245 + E485B576 625E7EC6 F44C42E9 A63A3620 FFFFFFFF FFFFFFFF + + The generator is: 2. diff --git a/vorlesungen/slides/a/ecc/oakley2.txt b/vorlesungen/slides/a/ecc/oakley2.txt new file mode 100644 index 0000000..ddb2d2a --- /dev/null +++ b/vorlesungen/slides/a/ecc/oakley2.txt @@ -0,0 +1,16 @@ +6.2 Second Oakley Group + + IKE implementations SHOULD support a MODP group with the following + prime and generator. This group is assigned id 2 (two). + + The prime is 2^1024 - 2^960 - 1 + 2^64 * { [2^894 pi] + 129093 }. + Its hexadecimal value is + + FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1 + 29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD + EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245 + E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED + EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE65381 + FFFFFFFF FFFFFFFF + + The generator is 2 (decimal) diff --git a/vorlesungen/slides/a/ecc/oakley3.txt b/vorlesungen/slides/a/ecc/oakley3.txt new file mode 100644 index 0000000..ab2c78f --- /dev/null +++ b/vorlesungen/slides/a/ecc/oakley3.txt @@ -0,0 +1,17 @@ +6.3 Third Oakley Group + + IKE implementations SHOULD support a EC2N group with the following + characteristics. This group is assigned id 3 (three). The curve is + based on the Galois Field GF[2^155]. The field size is 155. The + irreducible polynomial for the field is: + u^155 + u^62 + 1. + The equation for the elliptic curve is: + y^2 + xy = x^3 + ax^2 + b. + + Field Size: 155 + Group Prime/Irreducible Polynomial: + 0x0800000000000000000000004000000000000001 + Group Generator One: 0x7b + Group Curve A: 0x0 + Group Curve B: 0x07338f + Group Order: 0X0800000000000000000057db5698537193aef944 diff --git a/vorlesungen/slides/a/ecc/oakley4.txt b/vorlesungen/slides/a/ecc/oakley4.txt new file mode 100644 index 0000000..3ec20cc --- /dev/null +++ b/vorlesungen/slides/a/ecc/oakley4.txt @@ -0,0 +1,17 @@ +6.4 Fourth Oakley Group + + IKE implementations SHOULD support a EC2N group with the following + characteristics. This group is assigned id 4 (four). The curve is + based on the Galois Field GF[2^185]. The field size is 185. The + irreducible polynomial for the field is: + u^185 + u^69 + 1. The + equation for the elliptic curve is: + y^2 + xy = x^3 + ax^2 + b. + + Field Size: 185 + Group Prime/Irreducible Polynomial: + 0x020000000000000000000000000000200000000000000001 + Group Generator One: 0x18 + Group Curve A: 0x0 + Group Curve B: 0x1ee9 + Group Order: 0X01ffffffffffffffffffffffdbf2f889b73e484175f94ebc diff --git a/vorlesungen/slides/a/ecc/operation.tex b/vorlesungen/slides/a/ecc/operation.tex new file mode 100644 index 0000000..61ef95d --- /dev/null +++ b/vorlesungen/slides/a/ecc/operation.tex @@ -0,0 +1,68 @@ +% +% operation.tex -- Gruppen-Operation auf einer elliptischen Kurve +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Gruppenoperation} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.40\textwidth} +\begin{center} +\includegraphics[width=\textwidth]{../../buch/chapters/90-crypto/images/elliptic.pdf} +\end{center} +\vspace{-23pt} +\uncover<8->{% +\begin{block}{Verifizieren} +\begin{enumerate} +\item<9-> Assoziativ? +\item<10-> Neutrales Element $\mathstrut=\infty$ +\item<11-> Involution = Inverse? +\end{enumerate} +\end{block}} +\end{column} +\begin{column}{0.56\textwidth} +\begin{block}{Gerade} +$g_1,g_2\in G$, $t\in \Bbbk$ +\begin{align*} +g(t) +&= +tg_1+(1-t)g_2 +\\ +\uncover<2->{ +\begin{pmatrix}X(t)\\Y(t)\end{pmatrix} +&= +t\begin{pmatrix}x_1\\y_1\end{pmatrix} ++ +(1-t)\begin{pmatrix}x_2\\y_2\end{pmatrix} +\in\Bbbk^2 +} +\end{align*} +\end{block} +\vspace{-13pt} +\uncover<3->{% +\begin{block}{3. Schnittpunkt} +$g(t)$ einsetzen in die elliptische Kurve +\[ +p(t) += +Y(t)^2+X(t)Y(t)-X(t)^3-aX(t)-b=0 +\] +\vspace{-12pt} +\begin{enumerate} +\item<4-> +kubisches Polynom mit Nullstellen $t=0,1$ +\item<5-> +$p(t) $ ist durch $t(t-1)$ teilbar +\item<6-> +$p(t) = t(t-1)(Jt+K)=0 +\uncover<7->{\Rightarrow t=-K/J$} +\end{enumerate} +\end{block}} +\end{column} +\end{columns} +\end{frame} +\egroup diff --git a/vorlesungen/slides/a/ecc/prime1.txt b/vorlesungen/slides/a/ecc/prime1.txt new file mode 100644 index 0000000..eb4515d --- /dev/null +++ b/vorlesungen/slides/a/ecc/prime1.txt @@ -0,0 +1,5 @@ + 15 52518 09230 07089 35130 91813 12584 +81755 63133 40494 34514 31320 23511 94902 96623 99491 02107 +25866 94538 76591 64244 29100 07680 28886 42291 50803 71891 +80463 42632 72761 30312 82983 74438 08208 90196 28850 91706 +91316 59317 53674 69551 76311 98433 71637 22100 72105 77919 diff --git a/vorlesungen/slides/a/ecc/prime2.txt b/vorlesungen/slides/a/ecc/prime2.txt new file mode 100644 index 0000000..13458fb --- /dev/null +++ b/vorlesungen/slides/a/ecc/prime2.txt @@ -0,0 +1,8 @@ + 1797 69313 +48623 15907 70839 15679 37874 53197 86029 60487 56011 70644 +44236 84197 18021 61585 19368 94783 37958 64925 54150 21805 +65485 98050 36464 40548 19923 91000 50792 87700 33558 16639 +22955 31362 39076 50873 57599 14822 57486 25750 07425 30207 +74477 12589 55095 79377 78424 44242 66173 34727 62929 93876 +68709 20560 60502 70810 84290 76929 32019 12819 44676 27007 + diff --git a/vorlesungen/slides/a/ecc/primes b/vorlesungen/slides/a/ecc/primes new file mode 100644 index 0000000..3feea29 --- /dev/null +++ b/vorlesungen/slides/a/ecc/primes @@ -0,0 +1,13 @@ +#! /bin/bash +# +# primes +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +bc <<EOF +ibase=16 +FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A63A3620FFFFFFFFFFFFFFFF + +FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381FFFFFFFFFFFFFFFF + +EOF diff --git a/vorlesungen/slides/a/ecc/quadrieren.tex b/vorlesungen/slides/a/ecc/quadrieren.tex new file mode 100644 index 0000000..942c73b --- /dev/null +++ b/vorlesungen/slides/a/ecc/quadrieren.tex @@ -0,0 +1,59 @@ +% +% quadrieren.tex -- Quadrieren +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Quadrieren} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.40\textwidth} +\begin{block}{Problem} +\( g = g_1 = g_2 \) +$\Rightarrow$ +Tangente +\\ +\uncover<2->{{\color{red}ohne Analysis!}} +\end{block} +\begin{center} +\includegraphics[width=\textwidth]{../../buch/chapters/90-crypto/images/elliptic.pdf} +\end{center} +\end{column} +\begin{column}{0.56\textwidth} +\uncover<3->{% +\begin{block}{Lösung} +Finde $h\in G$ derart, dass +\begin{align*} +g(t) +&= +tg + (1-t)h +\\ +\uncover<4->{% +\begin{pmatrix}X(t)\\Y(t)\end{pmatrix} +&= +t\begin{pmatrix}x_g\\y_g\end{pmatrix} ++(1-t) \begin{pmatrix}x_h\\y_h\end{pmatrix} +} +\end{align*} +\uncover<5->{eingesetzt +\[ +p(t) += +Y(t)^2+X(t)Y(t)-X(t)^3-aX(t)-b += +0 +\]}% +\uncover<6->{% +Nullstellen $0$ (doppelt) und $1$ hat:} +\[ +\uncover<7->{p(t) = c(t^3-t)} +\] +\uncover<8->{Koeffizientenvergleich: einfachere Gleichungen für $x_h$ und $y_h$} +\end{block}} +\end{column} +\end{columns} +\end{frame} +\egroup diff --git a/vorlesungen/slides/test.tex b/vorlesungen/slides/test.tex index 4673f76..43da30a 100644 --- a/vorlesungen/slides/test.tex +++ b/vorlesungen/slides/test.tex @@ -4,36 +4,20 @@ % (c) 2021 Prof Dr Andreas Müller, Hochschule Rapperswil % -\section{Matrizen-Gruppen} -% Was sind Symmetrien -%\folie{7/symmetrien.tex} -% Algebraische Bedingungen für Matrixgruppen -%\folie{7/algebraisch.tex} -% Parametrisierung, Beispiel SO(3) -%\folie{7/parameter.tex} -% Mannigfaltigkeiten -%\folie{7/mannigfaltigkeit.tex} -% Weitere Beispiele -% SL_2(R) -%\folie{7/sl2.tex} -\folie{7/drehung.tex} -%\folie{7/drehanim.tex} -% Semidirekte Produkte SO(2) x R^2, R^+ x R -%\folie{7/semi.tex} +%\folie{a/dc/prinzip.tex} +%\folie{a/dc/effizient.tex} +%\folie{a/dc/beispiel.tex} -\section{Ableitungen} -% Kurven in einer Gruppe -%\folie{7/kurven.tex} -% Einparameter-Gruppen -%\folie{7/einparameter.tex} -% Ableitung einer Einparameter-Gruppe -%\folie{7/ableitung.tex} -% Lie-Algebra -%\folie{7/liealgebra.tex} -% Kommutator -%\folie{7/kommutator.tex} +%\folie{a/ecc/gruppendh.tex} +%\folie{a/ecc/kurve.tex} +%\folie{a/ecc/inverse.tex} +%\folie{a/ecc/operation.tex} +%\folie{a/ecc/quadrieren.tex} +%\folie{a/ecc/oakley.tex} -\section{Exponentialabbildung} -% Differentialgleichung für die Exponentialabbildung -%\folie{7/dg.tex} +%\folie{a/aes/bytes.tex} +%\folie{a/aes/sinverse.tex} +%\folie{a/aes/blocks.tex} +\folie{a/aes/keys.tex} +%\folie{a/aes/runden.tex} |