numbertheory.tex

a very popular packet of cryptography tools,it encloses the most common used algorithm and protocols

% $Id: numbertheory.tex 1205 2005-07-04 13:58:13Z koy $
%\def\QM {{,\kern -0.9 pt ,}}
\setcounter{satz}{0}
\setcounter{definition}{0}

% ..........................................................................
% --------------------------------------------------------------------------
% ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
%              E l e m e n t a r e  Z a h l e n t h e o r i e
% /~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

\newpage
\hypertarget{Chapter_ElementaryNT}{}

\section{Einf"uhrung in die elementare Zahlentheorie mit Beispielen}
\label{Chapter_ElementaryNT}
(Bernhard Esslinger, Juli 2001, Updates: Nov. 2001, Juni 2002, Mai 2003, Mai 2005) \\

Diese \glqq Einf"uhrung\grqq~ bietet einen Einstieg f"ur mathematisch Interessierte.
Erforderlich sind nicht mehr Vorkenntnisse als die, die im Grundkurs Mathematik am Gymnasium vermittelt werden.\par
Wir haben uns bewusst an \glqq Einsteigern\grqq~ und \glqq Interessenten\grqq~ orientiert, und nicht an den
Gepflogenheiten mathematischer Lehrb"ucher, die auch dann \glqq Einf"uhrung\grqq~ genannt werden,
wenn sie schon auf der 5. Seite nicht mehr auf Anhieb zu verstehen sind und sie eigentlich den Zweck haben, dass
man danach auch spezielle Monographien zu dem Thema lesen k"onnen soll.



% ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\subsection{Mathematik und Kryptographie}
Ein gro"ser Teil der modernen, asymmetrischen Kryptographie beruht auf 
mathematischen Erkenntnissen -- auf den Eigenschaften (\glqq Gesetzen'')
ganzer Zahlen, die in der elementaren \index{Zahlentheorie!elementare}
Zahlentheorie untersucht werden. \glqq Elementar\grqq\ bedeutet hier, 
dass die zahlentheoretischen Fragestellungen im wesentlichen
in der Menge der nat"urlichen und der ganzen Zahlen durchgef"uhrt werden.

Weitere mathematische Disziplinen, die heute in der Kryptographie 
Verwendung finden, sind 
(vgl. \cite[S. 2]{Bauer1995}, \cite[Seite 3]{Bauer2000}) :
\begin{itemize}
    \item Gruppentheorie
    \item Kombinatorik
    \item Komplexit"atstheorie
    \item Ergodentheorie
    \item Informationstheorie.
\end{itemize}

Die Zahlentheorie oder Arithmetik (hier wird mehr der Aspekt des Rechnens
mit Zahlen betont) wurde von Carl Friedrich Gauss\footnote{%
  Carl Friedrich Gauss, deutscher Mathematiker und Astronom,
  30.4.1777$-$23.2.1855.
}
\index{Gauss, Carl Friedrich}
als besondere mathematische Disziplin begr"undet. Zu ihren elementaren
Gegenst"anden geh"oren: gr"o"ster gemeinsamer Teiler\footnote{%
Auf ggT\index{ggT}, englisch gcd (greatest common divisor), geht dieser
Artikel im \hyperlink{Appendix_A}{Anhang A zu diesem Kapitel} ein.
} (ggT), Kongruenzen (Restklassen), Faktorisierung, Satz von Euler-Fermat und
primitive Wurzeln. Kernbegriff sind jedoch die Primzahlen und ihre
multiplikative Verkn"upfung.

Lange Zeit galt gerade die Zahlentheorie als Forschung pur, als
Paradebeispiel f"ur die Forschung im Elfenbeinturm. Sie erforschte die
\glqq geheimnisvollen Gesetze im Reich der Zahlen'' und gab Anlass zu
philosophischen Er"orterungen, ob sie beschreibt, was "uberall in der Natur
schon da ist, oder ob sie ihre Elemente (Zahlen, Operatoren, Eigenschaften)
nicht k"unstlich konstruiert.

Inzwischen wei"s man, dass sich zahlentheoretische Muster "uberall in der Natur
finden. Zum Beispiel verhalten sich die Anzahl der links- und der
rechtsdrehenden Spiralen einer Sonnenblume zueinander wie zwei
aufeinanderfolgende\index{Fibonacci} Fibonacci-Zahlen\footnote{%
Die Folge der Fibonacci-Zahlen $(a_i)_{i \in \mathbb{N}}$ ist definiert durch die \glqq rekursive'' 
Vorschrift $a_1 := a_2 := 1$ und f"ur alle Zahlen  $n=1,2,3,\cdots$ definiert man 
$a_{n+2} := a_{n+1}+a_n$.  Zu dieser historischen Folge gibt es viele interessante 
Anwendungen in der Natur (siehe z.B. \cite[S. 290 ff]{Graham1994}\index{Graham 1994} oder die Web-Seite 
von \hyperlink{knott}{Ron Knott:} \index{Knott, Ron} hier dreht sich alles um Fibonacci-Zahlen). 
Die Fibonacci-Folge\index{Fibonacci} ist gut verstanden und wird heute als wichtiges Werkzeug in der 
Mathematik benutzt.
}, also z.B.  wie  $21 : 34$.

Au"serdem wurde sp"atestens mit den zahlentheoretischen Anwendungen der
modernen Kryptographie klar, dass eine jahrhundertelang als theoretisch
geltende Disziplin praktische Anwendung findet, nach deren Experten heute
eine hohe Nachfrage auf dem Arbeitsmarkt besteht.

Anwendungen der (Computer-)Sicherheit bedienen sich heute der Kryptographie,
weil Kryptographie als mathematische Disziplin einfach besser und
beweisbarer ist als alle im Laufe der Jahrhunderte erfundenen \glqq kreativen''
Verfahren der Substitution und besser als alle ausgefeilten physischen
Techniken wie beispielsweise beim Banknotendruck \cite[S. 4]{Beutelspacher1996}.

In diesem Artikel werden in einer leicht verst"andlichen Art die
grundlegenden Erkenntnisse der elementaren Zahlentheorie anhand vieler
Beispiele vorgestellt -- auf Beweise wird (fast) vollst"andig verzichtet
(diese finden sich in den mathematischen Lehrb"uchern).

Ziel ist nicht die umfassende Darstellung der zahlentheoretischen Erkenntnisse,
sondern das Aufzeigen der wesentlichen Vorgehensweisen. Der Umfang des Stoffes
orientiert sich daran, das RSA-Verfahren\index{RSA} verstehen und anwenden
zu k"onnen.

Dazu wird sowohl an Beispielen als auch in der Theorie erkl"art, wie man in
endlichen Mengen rechnet und wie dies in der Kryptographie Anwendung findet.
Insbesondere wird auf die klassischen Public Key-Verfahren Diffie-Hellman
\index{Diffie-Hellman} (DH) und RSA\index{RSA} eingegangen.

Au"serdem war es mir wichtig, fundierte Aussagen zur Sicherheit des RSA-Verfahrens zu machen.

\vskip +40 pt

\begin{center}
\fbox{\parbox{15cm}{{\em Carl Friedrich Gauss:\index{Gauss, Carl Friedrich}}\\
Die Mathematik ist die K"onigin der Wissenschaften, die Zahlentheorie aber
ist die K"onigin der Mathematik.}}
\end{center}


% ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\subsection{Einf"uhrung in die Zahlentheorie}
\index{Zahlentheorie!Einf""uhrung} 

Die Zahlentheorie entstand aus Interesse an den positiven ganzen Zahlen $1,
2, 3, 4, \cdots ,$ die auch als die Menge der \index{Zahlen!nat""urliche}
{\em nat"urlichen Zahlen} $\mathbb{N}$ bezeichnet
werden. Sie sind die ersten mathematischen Konstrukte der menschlichen
Zivilisation. Nach Kronecker\footnote{%
Leopold Kronecker, deutscher Mathematiker, 7.12.1823$-$29.12.1891.
}
\index{Kronecker, Leopold} hat sie der liebe Gott geschaffen, 
nach Dedekind\footnote{Julius Wilhelm Richard Dedekind,
deutscher Mathematiker, 06.10.1831$-$12.02.1916.
}
\index{Dedekind, Julius} der menschliche Geist.
Das ist je nach Weltanschauung ein unl"osbarer Widerspruch oder
ein und dasselbe.

Im Altertum gab es keinen Unterschied zwischen Zahlentheorie und
Numerologie, die einzelnen Zahlen mystische Bedeutung zuma"s. So wie sich
w"ahrend der Renaissance (ab dem 14. Jahrhundert) die Astronomie allm"ahlich
von der Astrologie und die Chemie von der Alchemie l"oste, so lie"s auch die
Zahlentheorie die Numerologie hinter sich.

Die Zahlentheorie faszinierte schon immer Amateure wie auch professionelle
Mathematiker. Im Unterschied zu anderen Teilgebieten der Mathematik k"onnen
viele der Probleme und S"atze auch von Laien verstanden werden, andererseits
widersetzten sich die L"osungen zu den Problemen und die Beweise zu den S"atzen
oft sehr lange den Mathematikern. Es ist also leicht, gute Fragen zu stellen,
aber es ist ganz etwas anderes, die Antwort zu finden. Ein Beispiel daf"ur ist
der sogenannte letzte (oder gro"se) Satz von Fermat\footnote{Thema der
	Schul-Mathematik ist der Satz von Pythagoras\index{Pythagoras!Satz von},
	wo gelehrt wird, dass in einem
	rechtwinkligen Dreieck gilt: $a^2 + b^2 = c^2$, wobei $a, b$ die
	Schenkell"angen sind und c die L"ange der Hypothenuse ist. Fermats ber"uhmte
	Behauptung war, dass f"ur ganzzahlige Exponenten $n > 2$ immer die
	Ungleichheit $a^n + b^n \not= c^n$ gilt. Leider fand \index{Fermat!letzter
	Satz} Fermat auf dem Brief, wo er die Behauptung aufstellte, nicht gen"ugend
	Platz, um den Satz zu beweisen. Der Satz konnte erst "uber 300 Jahre sp"ater
	bewiesen werden \cite[S.  433-551]{Wiles1994}. \index{Wiles, Andrew}
}.

Bis zur Mitte des 20. Jahrhunderts wurde die Zahlentheorie als das reinste
Teilgebiet der Mathematik angesehen -- ohne Verwendung in der wirklichen Welt.
Mit dem Aufkommen der Computer und der digitalen Kommunikation "anderte sich
das: die Zahlentheorie konnte einige unerwartete Antworten f"ur reale
Aufgabenstellungen liefern. Gleichzeitig halfen die Fortschritte in der EDV,
dass die Zahlentheoretiker gro"se Fortschritte machten im Faktorisieren gro"ser
Zahlen, in der Bestimmung neuer Primzahlen, im Testen von (alten)
Vermutungen und beim L"osen bisher unl"osbarer numerischer Probleme.

Die moderne Zahlentheorie \index{Zahlentheorie!moderne} besteht aus Teilgebieten wie
\begin{itemize}
    \item Elementare Zahlentheorie
    \item Algebraische Zahlentheorie
    \item Analytische Zahlentheorie
    \item Geometrische Zahlentheorie
    \item Kombinatorische Zahlentheorie
    \item Numerische Zahlentheorie und
    \item Wahrscheinlichkeitstheorie.
\end{itemize}

Die verschiedenen Teilgebiete besch"aftigen sich alle mit Fragestellungen zu
den ganzen Zahlen (positive und negative ganze Zahlen und die Null), gehen
diese jedoch mit verschiedenen Methoden an.

Dieser Artikel besch"aftigt sich nur mit dem Teilgebiet der elementaren
Zahlentheorie.
\newpage


% --------------------------------------------------------------------------
\subsubsection{Konvention}
Wird nichts anderes gesagt, gilt: 
\begin{itemize}
\item Die Buchstaben $a, b, c, d, e, k, n, m, p, q$ stehen f"ur ganze Zahlen.
\item Die Buchstaben $i$ ~\mbox{und} ~$j$ stehen f"ur nat"urliche Zahlen. 
\item Der Buchstabe $p$ steht stets f"ur eine Primzahl.
\item Die Mengen $\mathbb{N} = \{ 1, 2, 3, \cdots \}$ und $\mathbb{Z} =\{ \cdots, -3, -2, -1, 0, 1, 2, 3, \cdots \}$ 
sind die {\em nat"urlichen} und die {\em ganzen} Zahlen.
\end{itemize}



%\vskip +40 pt
\newpage

\begin{center}
\fbox{\parbox{15cm}{{\em Joanne K. Rowling\index{Rowling, Joanne}\footnotemark:}\newline Das ist nicht Zauberei, das ist Logik, ein R"atsel.
Viele von den gr"o"sten Zauberern haben keine Unze Logik im Kopf.}}
\end{center}
\addtocounter{footnote}{0}\footnotetext{Joanne K. Rowling,~\glqq Harry Potter und der Stein der Weisen'', Carlsen, (c)
1997, Kapitel ~\glqq Durch die Fallt"ur'', S. 310, Hermine.}


% ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\subsection{Primzahlen und der erste Hauptsatz der elementaren Zahlentheorie}
\index{Zahlentheorie!elementare} Viele der Probleme in der elementaren Zahlentheorie besch"aftigen sich mit
Primzahlen.

Jede ganze Zahl hat Teiler oder Faktoren. Die Zahl 1 hat nur einen, n"amlich
sich selbst. Die Zahl 12 hat die sechs Teiler 1, 2, 3, 4, 6 und 12\footnote{%
Aufgrund der gro"sen Teilerzahl von 12 findet sich diese Zahl -- und Vielfache dieser Zahl -- oft im allt"aglichen wieder:
Die 12 Stunden-Skala der Uhr, die 60 Minuten einer Stunde, die 360 Grad-Skala der Winkelmessung, usw. Teilt man 
diese Skalen in Bruchteile auf, so ergeben sich in vielen F"allen die Br"uche als ganze Zahlen. Mit diesen kann 
man im Kopf einfacher rechnen als mit gebrochenen Zahlen.
}. Viele Zahlen sind nur teilbar durch sich selbst und durch 1. Bez"uglich der
Multiplikation sind dies die \glqq Atome'' im Bereich der Zahlen.

\index{Primzahl}
\begin{definition}\label{def-zth-prime} 
{\bf Primzahlen} sind nat"urliche Zahlen gr"o"ser als $1$, die nur durch $1$ und sich
selbst teilbar sind.
\end{definition}

Per Definition ist $1$ keine Primzahl.

Schreibt man die Primzahlen in aufsteigender Folge (Primzahlenfolge), so
ergibt sich
$$2,~ 3,~ 5,~ 7,~ 11, ~13,~ 17,~ 19, ~23, ~29, ~31, ~37,~ 41,~ 43,~ 47,~ 53, ~59, ~61, ~67, ~71,
~73, ~79, ~83, ~89, ~97, \cdots.$$

Unter den ersten $100$ Zahlen gibt es genau $25$ Primzahlen. Danach nimmt ihr
prozentualer Anteil ab, wird aber nie Null.

Primzahlen treten als ganze Zahlen nicht selten auf. Allein im letzten
Jahrzehnt waren drei Jahre prim: $1993, 1997$ und $1999$. W"aren sie selten,
k"onnte die Kryptographie auch nicht so mit ihnen arbeiten, wie sie es tut.

Primzahlen k"onnen nur auf eine einzige (\glqq triviale'') Weise zerlegt werden:
\begin{eqnarray*}
5 & = & 1 * 5 \nonumber \\
17 & =  & 1 * 17 \nonumber \\
1.013 &  = & 1 * 1.013 \nonumber \\
1.296.409 & = & 1 * 1.296.409. \nonumber
\end{eqnarray*}

\index{Zahlen!zusammengesetzte}
\begin{definition}\label{def-zth-composite} 
Nat"urliche Zahlen gr"o"ser $1$, die keine Primzahlen sind, hei"sen
{\bf zusammengesetzte Zahlen}: diese haben mindestens zwei von $1$ verschiedene
Faktoren.
\end{definition}


Beispiele f"ur die Primfaktorzerlegung\index{Primfaktor!Zerlegung} solcher
Zahlen: