gistfile1.sty

\documentclass[a4paper]{book}
\usepackage{ngerman}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{tikz}
\usepackage{shortcuts}
\usepackage{times}
\usepackage{enumerate}

% uncomment for non-testing pdf production
\usepackage[pdftex]{thumbpdf, hyperref}

\title{Analysis f"ur Informatiker}
\author{Gregor Best}

\begin{document}
% Inhaltsverzeichnis
\maketitle
\tableofcontents

% Inhalt
\chapter{Gruppen} \label{1} % {{{
\begin{enumerate}[\bfseries A]
\item \ref{1A} Gruppen
\item \ref{1B} Gruppenhomomorphismen
\item Symmetrische Gruppen
\item Public-Key-Kryptographie
\end{enumerate}
\section{Gruppen} \label{1A} % {{{
\subsection{Definition: Gruppe} \label{1.1} % {{{
\begin{itemize}
\item Eine \emph{Gruppe} ist eine Menge \(G\) zusammen mit einer Verkn"upfung
    \begin{align*}
    G \times G \ra G; (g, h) \mt g \cdot h
    \end{align*}
    so da"s gilt:
    \begin{enumerate}[\bfseries G1]
    \item \(g_{1} \cdot (g_{2} \cdot g_{3}) = (g_{1} \cdot g_{2}) \cdot g_{3} \ \fa \ g_{1}, g_{2}, g_{3} \ \in \ G\)
    \item Es existiert genau ein Element \(e \in G\), so da"s \(e \cdot g = g \cdot e = g \ \fa \ g \in G\).
        (\(e\) hei"st \emph{neutrales Element})
    \item Zu jedem \(g \in G\) existiert genau ein Element \(g^{-1}\) in \(G\) mit \(g \cdot g^{-1} = g^{-1} \cdot g = e\).
        (\(g^{-1}\) hei"st \emph{Inverses von \(g\)})
    \end{enumerate}
\item Eine Gruppe \((G, \cdot)\) hei"st \emph{kommutativ} falls au"serdem gilt:
    \begin{align*}
    g_{1}g_{2} = g_{2}g_{1} \ \fa \ g_{1}, g_{2} \ \in \ G
    \end{align*}
\end{itemize}
% }}}
\subsection{Beispiele} \label{1.2} % {{{
\begin{enumerate}
\item Sei \(K\) ein K"orper (z.B. \(K = \mathR, \mathC, \mathQ\)). Setze \(K^{\times} := K \setminus \{ 0 \}\).
    Dann sind \((K, +)\) und \((K^{\times}, \cdot)\) Gruppen, die kommutativ sind.
\item \((\mathN, +)\) ist keine Gruppe (da kein Inverses f"ur Elemente aus \(\mathN\) in \(\mathN\) existiert).
\item \((\mathZ, +)\) ist eine Gruppe.
\item Sei \(M\) eine Menge. Definiere
    \begin{align*}
    S_{M} := \{ \pi: M \ra M | \pi \ \tn{bijektiv}\}
    \end{align*}
    Definiere eine Verkn"upfung auf \(S_{M}\) durch Komposition:
    \begin{align*}
    \pi_{1} \cdot \pi_{2} :&= \pi_{1} \circ \pi_{2} \\
    \pi_{1} \circ \pi_{2} :& M \ra M; x \mt \pi_{1}(\pi_{2}(x))
    \end{align*}
    Dann ist \(S_{M}\) mit Komposition \((S_{M}, \circ)\) eine Gruppe mit neutralem Element \(\tn{id}_{M}\).
\item Sei \(K\) ein K"orper, so da"s \(1 \not= -1\).
    \begin{align*}
    E' &:= \{ (x, y) \in K^{2} | y^{2} = x^{3} - x \} \\
    E  &:= E' \cup \{ \infty \}
    \end{align*}
    \(E\) ist dann eine \emph{elliptische Kurve}. \\
    \textbf{Beispiel}: \(K = \mathR\): \\
    \begin{tikzpicture}
        \clip (-3, -1.5) rectangle (6, 2.5);
        \begin{scope}[->, gray, thin]
            \draw (-4, 0) -- (6, 0);
            \draw (0, -2.5) -- (0, 2.5);
        \end{scope}
        \draw (-2, -1pt) -- (-2, 1pt) node[anchor=south]{$1$};
        \draw (-1, 0) ellipse(0.75 and 1);
        \draw (6, 2.5) .. controls (2.5, 0.5) and (2.5, -0.5) .. (6, -2.5);
        \filldraw (-1, 0) ++(135:0.75 and 1) circle(1pt) node[anchor=south]{$P$};
        \filldraw (-1, 0) ++(55:0.75 and 1) circle(1pt) node[anchor=south]{$Q$};
        \draw (-1, 0) +(135:0.75 and 1) -- +(55:0.75 and 1);
        \filldraw (-1, 0) +(55:0.75 and 1) -- +(14:5.35) circle(1pt) node[anchor=south]{$R$};
        \draw (2, 1) node[anchor=south]{$L$};
    \end{tikzpicture} \\
    Definiere eine Verkn"upfung auf \(E'\):
    \begin{align*}
    \infty + P = P + \infty := P \ \fa \quad P \in E
    \end{align*}
    Seien \(P, Q \in E'\). Dann sei \(L\) die Gerade durch \(P\) und \(Q\). Dann existiert genau ein dritter Schnittpunkt
    \(R\) mit \(E'\). Setze \(P + Q =\) Spiegelung von \(R\) an der \(x-\)Achse. Dann ist \((E, +)\) eine kommutative
    Gruppe.
\end{enumerate}
% }}}
\subsection{Bemerkung} \label{1.3} % {{{
Sei \(G\) eine Gruppe, \(g_{1}, g_{2} \in G\). Dann:
\begin{align*}
(g_{1}g_{2})^{-1} = g_{2}^{-1}g_{1}^{-1}
\end{align*}
\subsubsection{Beweis}
Zu zeigen:
\begin{align*}
(g_{1}g_{2})(g_{1}g_{2})^{-1} =& e = (g_{2}^{-1}g_{1}^{-1})(g_{1}g_{2})
\end{align*}
\begin{align*}
  (g_{1}g_{2}) \cdot (g_{2}^{-1}g_{1}^{-1}) &\us{\tn{G1}}{=} g_{1}(g_{2}g_{2}^{-1})g_{1}^{-1} \\
= g_{1} \cdot e \cdot g_{1}^{-1} &\us{\tn{G2}}{=} g_{1} \cdot g_{1}^{-1} = e
\end{align*}
\qed
% }}}
\subsection{Bezeichnung} \label{1.4} % {{{
Sei \(G\) eine Gruppe, \(g \in G, n \in \mathZ\). Setze:
\begin{align*}
g^{n} = \begin{cases}
g \cdot g \cdot \ldots \cdot g \quad n\tn{-mal} & n \geq 1 \\
e                                          & n = 0 \\
(g^{-n})^{-1}                              & n \leq -1
\end{cases}
\end{align*}
% }}}
\subsection{Definition: Untergruppe} \label{1.5} % {{{
Sei \(G\) eine Gruppe. Eine Teilmenge \(H \sse G\) hei"st \emph{Untergruppe}, falls:
\begin{enumerate}[\bfseries a)]
\item \(h_{1}, h_{2} \in H \ \Ra \ h_{1}h_{2} \in H\)
\item \(e \in H\)
\item \(h \in H \ \Ra \ h^{-1} \in H\)
\end{enumerate}
Klar: \((H, \cdot)\) ist eine Gruppe.
% }}}
\subsection{Beispiele} \label{1.6} % {{{
\begin{itemize}
\item \(\mathZ \subset (\mathQ, +)\) ist eine Untergruppe
\item \(G\) Gruppe \(\Ra \begin{cases}
    G \sse G & \tn{Untergruppe} \\
    \{e\} \sse G & \tn{Untergruppe}
    \end{cases}\)
\item Der Durchschnitt von Untergruppen ist eine Untergruppe.
\end{itemize}
% }}}
\subsection{Bemerkung und Definition: erzeugte Untergruppe} \label{1.7} % {{{
Sei \(G\) eine Gruppe und \(M \sse G\) Teilmenge. Dann ist
\begin{align*}
\langle M \rangle := \us{\stackrel{H \sse G}{M \sse H}}{\bigcap}H
\end{align*}
die kleinste Untergruppe von \(G\), die \(M\) enth"alt. \(\langle M \rangle\) hei"st \emph{von \(M\) erzeugte Untergruppe}.
Es gilt:
\begin{align*}
\langle M \rangle = \{ g_{1}^{\epsilon_{1}}, g_{2}^{\epsilon_{2}}, \ldots, g_{r}^{\epsilon_{r}} | r \geq 0, g_{1} \in M, \epsilon_{1} \in \{ \pm 1 \}\}
\end{align*}
Falls \(M = \{ m_{1}, \ldots, m_{s} \}\), schreibe \(\langle m_{1}, \ldots, m_{s} \rangle\) statt \(\langle \{ m_{1}, \ldots, m_{s} \} \rangle\).
% }}}
% }}}
\section{Gruppenhomomorphismen} \label{1B} % {{{
\subsection{Definition: Gruppenhomomorphismus} \label{1.8} % {{{
Seien \(G, G'\) Gruppen. Eine Abbildung \(\varphi: G \ra G'\) hei"st \emph{Gruppenhomomorphismus}, falls gilt:
\begin{enumerate}[\bfseries a)]
\item \(\varphi(g_{1}g_{2}) = \varphi(g_{1})\varphi(g_{2}) \quad \fa \ g_{1}, g_{2} \in G\)
\item \(\varphi(e_{G}) = e_{G'}\)
\item \(\varphi(g^{-1}) = \varphi(g)^{-1} \quad \fa \ g \in G\)
\end{enumerate}
% }}}
\subsection{Bemerkung} \label{1.9} % {{{
Sei \(\varphi: G \ra G'\) eine Abbildung, so da"s \(\varphi(g_{1}g_{2}) = \varphi(g_{1})\varphi(g_{2}) \ \fa \ g_{1}, g_{2} \in G\).
Dann ist \(\varphi\) ein Gruppenhomomorphismus.
\subsubsection{Beweis}
\begin{align*}
\varphi(e_{G}) &= \varphi(e_{G}e_{G}) = \varphi(e_{G}) \cdot \varphi(e_{G}) \us{\varphi(e_{G})^{-1}}{\Ra} e_{G'} = \varphi(e_{G}) \\
\varphi(g^{-1})\varphi(g) &= \varphi(g^{-1}g) = \varphi(e_{G}) = e_{G'} \Ra \varphi(g^{-1}) = \varphi(g)^{-1}
\end{align*}
\qed
% }}}
\subsection{Bemerkung und Definition: Kern, Bild} \label{1.10} % {{{
Sei \(\varphi: G \ra G'\) Gruppenhomomorphismus.
\begin{enumerate}[\bfseries 1)]
\item Sei \(H' \sse G'\) Untergruppe. Dann ist
    \begin{align*}
    \varphi^{-1}(H') = \{ g \in G | \varphi(g) \in H' \}
    \end{align*}
    eine Untergruppe von \(G\). Insbesondere ist der \emph{Kern von \(\varphi\)}
    \begin{align*}
    \ker(\varphi) := \varphi^{-1}(\{e_{G'}\}) = \{ g \in G | \varphi(g) = e_{G'} \}
    \end{align*}
    eine Untergruppe von \(G\).
\end{enumerate}
% }}}
% }}}
% }}}
\end{document}