aboutsummaryrefslogtreecommitdiffstats
path: root/buch
diff options
context:
space:
mode:
Diffstat (limited to 'buch')
-rw-r--r--buch/chapters/10-vektorenmatrizen/linear.tex9
-rw-r--r--buch/chapters/50-permutationen/determinante.tex102
-rw-r--r--buch/chapters/50-permutationen/matrizen.tex5
-rw-r--r--buch/chapters/60-gruppen/symmetrien.tex4
-rw-r--r--buch/chapters/70-graphen/wavelets.tex2
-rw-r--r--buch/chapters/90-crypto/arith.tex1
-rw-r--r--buch/chapters/90-crypto/ff.tex53
-rw-r--r--buch/chapters/references.bib7
8 files changed, 172 insertions, 11 deletions
diff --git a/buch/chapters/10-vektorenmatrizen/linear.tex b/buch/chapters/10-vektorenmatrizen/linear.tex
index 10b5a7e..e368364 100644
--- a/buch/chapters/10-vektorenmatrizen/linear.tex
+++ b/buch/chapters/10-vektorenmatrizen/linear.tex
@@ -1088,6 +1088,15 @@ für die Inverse einer Matrix der Form
\eqref{buch:vektoren-und-matrizen:abeispiel:eqn1}.
\end{beispiel}
+\subsubsection{Produktregel für die Determinante}
+Aus der Charakterisierung der Determinanten kann man auch ableiten,
+dass die Produktregel
+\[
+\det (AB) = \det(A) \cdot \det(B)
+\]
+gilt.
+Daraus folgt auch, dass $\det(A^{-1})=\det(A)^{-1}$.
+
%
% Lineare Abbildungen
%
diff --git a/buch/chapters/50-permutationen/determinante.tex b/buch/chapters/50-permutationen/determinante.tex
index c440caf..805235d 100644
--- a/buch/chapters/50-permutationen/determinante.tex
+++ b/buch/chapters/50-permutationen/determinante.tex
@@ -7,3 +7,105 @@
\section{Determinante
\label{buch:section:determinante}}
\rhead{Determinante}
+Das Signum einer Permutationsmatrizen lässt sich
+gemäss~\eqref{buch:permutationen:determinante}
+mit der Determinanten berechnen.
+Umgekehrt sollte es auch möglich sein, eine Formel
+für die Determinante zu finden.
+Die Basis dafür ist der
+Entwicklungssatz
+\begin{equation}
+\det(A)
+=
+\sum_{i=1}^n (-1)^{i+j} a_{ij} \cdot \det(A_{ij})
+\label{buch:permutationen:entwicklungssatz}
+\end{equation}
+von Laplace für die Determinante.
+In den Produkten $a_{ij}\cdot\det(A_{ij})$ enthält
+die Untermatrix $A_{ij}$ weder Elemente der Zeile $i$ noch der
+Zeile $j$.
+Die Summanden auf der rechten Seite von
+\eqref{buch:permutationen:entwicklungssatz}
+sind daher Produkte der Form
+\[
+a_{1i_1}
+a_{2i_2}
+a_{3i_3}
+\dots
+a_{ni_n},
+\]
+in denen nur Faktoren aus verschiedenen Spalten der Matrix $A$
+vorkommen.
+Das ist gleichbedeutend damit, dass unter den Spaltenindizes
+$i_1,i_2,i_3,\dots,i_n$ keine zwei gleich sind, dass also
+\[
+\sigma
+=
+\begin{pmatrix}
+1&2&3&\dots&n\\
+i_1&i_2&i_3&\dots&i_n
+\end{pmatrix}
+\]
+eine Permutation ist.
+
+Die Determinante muss sich daher als Summe über alle Permutationen
+in der Form
+\begin{equation}
+\det(A)
+=
+\sum_{\sigma\in S_n}
+c(\sigma)
+a_{1\sigma(1)}
+a_{2\sigma(2)}
+\dots
+a_{n\sigma(n)}
+\label{buch:permutationen:cformel}
+\end{equation}
+schreiben lassen, wobei die Koeffizienten $c(\sigma)$ noch zu bestimmen
+sind.
+Setzt man in
+\eqref{buch:permutationen:cformel}
+eine Permutationsmatrix $P_\tau$ ein, dann verschwinden alle
+Terme auf der rechten Seite ausser dem zur Permutation $\tau$,
+also
+\[
+\det(P_\tau)
+=
+\sum_{\sigma \in S_n}
+c(\sigma)
+(P_\tau)_{1\sigma(1)}
+(P_\tau)_{2\sigma(2)}
+\dots
+(P_\tau)_{n\sigma(n)}
+=
+c(\tau)
+1\cdot 1\cdot\dots\cdot 1
+=
+c(\tau).
+\]
+Der Koeffizientn $c(\tau)$ ist also genau das Vorzeichen
+der Permutation $\tau$.
+Damit erhalten wir den folgenden Satz:
+
+\begin{satz}
+Die Determinante einer $n\times n$-Matrix $A$ kann berechnet werden als
+\[
+\det(A)
+=
+\sum_{\sigma\in S_n}
+\operatorname{sgn}(\sigma)
+a_{1\sigma(1)}
+a_{2\sigma(2)}
+\dots
+a_{n\sigma(n)}
+=
+\sum_{\tau\in S_n}
+\operatorname{sgn}(\tau)
+a_{\tau(1)1}
+a_{\tau(2)2}
+\dots
+a_{\tau(n)n}.
+\]
+Insbesondere folgt auch $\det(A)=\det(A^t)$.
+\end{satz}
+
diff --git a/buch/chapters/50-permutationen/matrizen.tex b/buch/chapters/50-permutationen/matrizen.tex
index 7e55364..f7e9e31 100644
--- a/buch/chapters/50-permutationen/matrizen.tex
+++ b/buch/chapters/50-permutationen/matrizen.tex
@@ -181,7 +181,7 @@ Die Determinante einer solchen Permutationsmatrix ist
Nach der Produktregel für die Determinante folgt für eine Darstellung
der Permutation $\sigma=\tau_1\dots\tau_l$ als Produkt von Transpositionen,
dass
-\[
+\begin{equation}
\det P_{\sigma}
=
\det P_{\tau_1} \dots \det P_{\tau_l}
@@ -189,7 +189,8 @@ dass
(-1)^l
=
\operatorname{sgn}(\sigma).
-\]
+\label{buch:permutationen:determinante}
+\end{equation}
Das Vorzeichen einer Permutation ist also identisch mit der Determinante
der zugehörigen Permutationsmatrix.
diff --git a/buch/chapters/60-gruppen/symmetrien.tex b/buch/chapters/60-gruppen/symmetrien.tex
index 7364c85..aee3b41 100644
--- a/buch/chapters/60-gruppen/symmetrien.tex
+++ b/buch/chapters/60-gruppen/symmetrien.tex
@@ -714,8 +714,8 @@ Kurve so zu definieren, dass dabei Längen und Winkel erhalten bleiben.
Dieser Ansatz ist die Basis der Theorie der Krümmung sogenannter
Riemannscher Mannigfaltigkeiten.
-\subsection{Der Satz von Noether
-\label{buch:subsection:noether}}
+%\subsection{Der Satz von Noether
+%\label{buch:subsection:noether}}
diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex
index ef1520e..8baa88c 100644
--- a/buch/chapters/70-graphen/wavelets.tex
+++ b/buch/chapters/70-graphen/wavelets.tex
@@ -10,7 +10,7 @@ In Abschnitt~\ref{buch:subsection:standardbasis-und-eigenbasis} wurde
gezeigt dass die Standardbasis den Zusammenhang zwischen den einzelnen
Teilen des Graphen völlig ignoriert, während die Eigenbasis Wellen
beschreibt, die mit vergleichbarer Amplitude sich über den ganzen
-Graphen entsprechen.
+Graphen erstrecken.
Die Eigenbasis unterdrückt also die ``Individualität'' der einzelnen
Knoten fast vollständig.
diff --git a/buch/chapters/90-crypto/arith.tex b/buch/chapters/90-crypto/arith.tex
index dcc31b8..b05110f 100644
--- a/buch/chapters/90-crypto/arith.tex
+++ b/buch/chapters/90-crypto/arith.tex
@@ -91,6 +91,7 @@ Die Berechnung der Quadratwurzel lässt sich in Hardware effizient
implementieren.
\begin{algorithmus}
+\label{buch:crypto:teile-und-hersche}
Der folgende Algorithmus berechnet $a^k$ in $O(\log_2(k))$
Multiplikationen
\begin{enumerate}
diff --git a/buch/chapters/90-crypto/ff.tex b/buch/chapters/90-crypto/ff.tex
index 535b359..a1cb747 100644
--- a/buch/chapters/90-crypto/ff.tex
+++ b/buch/chapters/90-crypto/ff.tex
@@ -7,6 +7,15 @@
\section{Kryptographie und endliche Körper
\label{buch:section:kryptographie-und-endliche-koerper}}
\rhead{Kryptographie und endliche Körper}
+In diesem Abschnitt soll illustriert werden, wie die Arithmetik in
+endlichen Körpern Algorithmen zu konstruieren erlaubt, mit denen sich
+zum Beispiel sehr effizient kryptographische Schlüssel aushandeln
+lassen.
+Der klassische Diffie-Hellmann-Algorithmus in einem Galois-Körper
+$\mathbb{F}_p$ wird in Abschnitt~\ref{buch:subsection:elliptische-kurven}
+verallgemeinert auf eine sogenannte elliptische Kurve.
+Diese Version des Algorithmus ist sehr effizient was die Bitlänge der
+Schlüssel betrifft.
\subsection{Potenzen in $\mathbb{F}_p$ und diskreter Logarithmus
\label{buch:subsection:potenzen-diskreter-logarithmus}}
@@ -439,6 +448,7 @@ Das Polynom ist
\[
p(t)
=
+XXX
\]
Nach Division durch $t(t-1)$ erhält man als den Quotienten
\begin{align*}
@@ -652,13 +662,44 @@ Diese Operationen machen $E_{a,b}(\mathbb{F}_{p^l})$ zu einer endlichen
abelschen Gruppe.
\end{satz}
-\subsubsection{Beispiele}
-% XXX
-TODO: elliptische Kurven in IPsec: Oakley Gruppen
-
\subsubsection{Diffie-Hellman in einer elliptischen Kurve}
-% XXX
-TODO: $g^x$ in einer elliptischen Kurve
+Der klassische Diffie-Hellmann-Schlüsselalgorithmus in einem Körper
+$\mathbb{F}_p$ basiert darauf, dass man beliebige Potenzen eines
+Elementes berechnen kann, und dass es schwierig ist, diese Operation
+umzukehren.
+Die Addition in $\mathbb{F}_p$ wird für diesen Algorithmus überhaupt
+nicht benötigt.
+
+In einer elliptischen Kurve gibt es ebenfalls eine Multiplikation,
+aus der sich mit dem
+Algorithmus~\ref{buch:crypto:teile-und-hersche} eine effizienter
+Potenzieralgorithmus konstruieren lässt.
+
+Die im Internet Key Exchange Protokol
+in RFC 2409
+\cite{buch:rfc2409}
+definierte Oakley-Gruppe 4
+zum Beispiel verwendet einen Galois-Körper $\mathbb{F}_{2^{185}}$
+mit dem Minimalpolynom $m(x)=x^{185}+x^{69}+1\in \mathbb{F}_2[x]$
+und den Koeffizienten
+\begin{align*}
+a&=0\\
+b&=x^{12}+x^{11} + x^{10} + x^9 + x^7 + x^6 + x^5 + x^3 +1,
+\end{align*}
+die die elliptische Kurve definieren.
+
+Als Elemente $g$ für den Diffie-Hellmann-Algorithmus wird ein Punkt
+der elliptischen Kurve verwendet, dessen $X$-Koordinaten durch das
+Polynom $g_x = x^4+x^3$ gegeben ist.
+Der Standard spezifiziert die $Y$-Koordinate nicht, diese kann aus
+den gegebenen Daten abgeleitet werden.
+Die entstehende Gruppe hat etwa $4.9040\cdot10^{55}$ Elemente, die
+für einen brute-force-Angriff durchprobiert werden müssten.
+
+
+
+
+
diff --git a/buch/chapters/references.bib b/buch/chapters/references.bib
index 59a8376..977bf81 100644
--- a/buch/chapters/references.bib
+++ b/buch/chapters/references.bib
@@ -39,6 +39,13 @@ abstract = "In this paper, we present Google, a prototype of a large-scale searc
year = {2016},
}
+@online{buch:rfc2409,
+ title = {The Internet Key Exchange (IKE)},
+ author = { D. Harkins and D. Carrel},
+ url = {https://datatracker.ietf.org/doc/html/rfc2409},
+ year = {1998}
+}
+
@online{buch:fftw,
title = {Fastest Fourier Transform in the West},
url = {http://www.fftw.org/},