primes.tex

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

% $Id: primes.tex 1205 2005-07-04 13:58:13Z koy $
% ...........................................................................
%       K A P I T E L  3 :     P R I M Z A H L E N
% /~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

\newpage
\section{Primzahlen}
\hypertarget{Kapitel_2}{}
\label{Label_Kapitel_2}
(Bernhard Esslinger, Mai 1999, Updates: Nov. 2000, Dez. 2001, Juni 2003, Mai 2005)

\begin{center}
\fbox{\parbox{15cm}{
    \emph{Albert Einstein\footnotemark:}\\
    Der Fortschritt lebt vom Austausch des Wissens.
}}
\end{center}
\addtocounter{footnote}{0}\footnotetext{%
  Albert Einstein, deutscher Physiker und Nobelpreistr"ager, 
  14.03.1879$-$14.04.1955.
}

% --------------------------------------------------------------------------
\subsection{Was sind Primzahlen?}
\index{Primzahl} \index{Zahlen!Primzahl} Primzahlen sind ganze,
positive Zahlen gr"o"ser gleich $2$, die man nur durch 1 und durch
sich selbst teilen kann. Alle anderen nat"urlichen Zahlen gr"o"ser
gleich $2$ lassen sich durch Multiplikation von Primzahlen
bilden.

Somit bestehen die {\em nat"urlichen} \index{Zahlen} Zahlen $ \mathbb{N} = \{1, 2,
3, 4,\cdots \} $ aus
\begin{itemize}
   \item der Zahl $1$ (dem Einheitswert)
   \item den Primzahlen (primes) und
   \item den zusammengesetzten Zahlen (composite numbers).
\end{itemize}

Primzahlen haben aus 3 Gr"unden besondere Bedeutung erlangt:
\begin{itemize}
  \item Sie werden in der Zahlentheorie als die Grundbausteine der nat"urlichen Zahlen betrachtet,
        anhand derer eine Menge genialer mathematischer "Uberlegungen gef"uhrt wurden.
  \item Sie haben in der modernen \index{Kryptographie!moderne} Kryptographie
        (Public Key \index{Kryptographie!Public Key} Kryptographie) gro"se praktische
        Bedeutung erlangt. Das verbreitetste Public Key Verfahren ist die Ende der siebziger Jahre
        erfundene \index{RSA} RSA-Verschl"usselung. Nur die Verwendung (gro"ser) Primzahlen f"ur bestimmte
        Parameter garantiert die Sicherheit des Algorithmus sowohl beim RSA-Verfahren als auch bei
        noch moderneren Verfahren (digitale \index{Signatur!digitale} Signatur, Elliptische Kurven).
  \item Die Suche nach den gr"o"sten bekannten Primzahlen hat wohl bisher keine praktische
        Verwendung, erfordert aber die besten Rechner, gilt als hervorragender Benchmark (M"oglichkeit
        zur Leistungsbestimmung von Computern) und f"uhrt zu neuen Formen der Berechnungen auf
        mehreren Computern \\
        (siehe auch: \href{http://www.mersenne.org/prime.htm}{\tt http://www.mersenne.org/prime.htm}).
\end{itemize}
Von Primzahlen lie"sen sich im Laufe der letzten zwei Jahrtausende sehr viele Menschen faszinieren.
Der Ehrgeiz, zu neuen Erkenntnissen "uber Primzahlen zu gelangen, f"uhrte dabei oft zu genialen Ideen
und Schlussfolgerungen.
Im folgenden wird in einer leicht verst"andlichen Art in die mathematischen Grundlagen der Primzahlen
eingef"uhrt. Dabei kl"aren wir auch, was "uber die Verteilung (Dichte, Anzahl von Primzahl in einem
bestimmten Intervall) der Primzahlen bekannt ist oder wie Primzahltests funktionieren.


% --------------------------------------------------------------------------
\subsection{Primzahlen in der Mathematik}\label{primesinmath}

Jede ganze Zahl hat Teiler. Die Zahl 1 hat nur einen, n"amlich
sich selbst. Die Zahl $12$ hat die sechs Teiler $1, 2, 3, 4, 6,
12$. Viele Zahlen sind nur durch sich selbst und durch $1$ teilbar. 
Bez"uglich der Multiplikation sind dies die \glqq Atome\grqq
~ im Bereich der Zahlen. Diese Zahlen nennt man Primzahlen.

In der Mathematik ist eine etwas andere (aber "aquivalente) Definition "ublich.

\begin{definition}\label{def-pz-prime}
Eine ganze Zahl $p \in {\bf N}$ hei"st Primzahl \index{Zahlen!Primzahl}, wenn $p > 1$ und $p$ nur die trivialen
Teiler $\pm 1$ und $\pm p$ besitzt.
\end{definition}


Per definitionem ist die Zahl $1$ keine Primzahl. Im weiteren bezeichnet der Buchstabe $p$ stets eine Primzahl.

Die Primzahlenfolge startet mit
$$ 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 stets
ab. Primzahlen k"onnen nur auf eine einzige {\em triviale} Weise zerlegt werden:
$$5 = 1 \cdot 5,\quad  17 = 1 \cdot 17, \quad 1013 = 1 \cdot 1.013,  \quad 1.296.409 = 1 \cdot 1.296.409.$$
Alle Zahlen, die $2$ und mehr von 1 verschiedene Faktoren haben, nennt man \index{Zahlen!zusammengesetzte} {\em zusammengesetzte} Zahlen. Dazu geh"oren
$$ 4 = 2 \cdot 2, \quad 6 = 2\cdot 3 $$
aber auch Zahlen, die {\em wie Primzahlen aussehen}, aber doch keine sind:
$$ 91 = 7 \cdot 13, \quad 161=7 \cdot 23, \quad 767 =13 \cdot 59. $$

\begin{satz}\label{thm-pz-sqr}
Jede ganze Zahl $m$ gr"o"ser als $1$ besitzt einen kleinsten Teiler gr"o"ser als $1$.
Dieser ist eine Primzahl $p$. Sofern $m$ nicht selbst eine Primzahl ist, gilt:
$p$ ist kleiner oder gleich der Quadratwurzel aus $m$.
\end{satz}

Aus den Primzahlen lassen sich alle ganzen Zahlen gr"o"ser als $1$ zusammensetzen --- und das sogar in
einer eindeutigen Weise. Dies besagt der 1. Hauptsatz der Zahlentheorie (= Hauptsatz der elementaren Zahlentheorie =
fundamental theorem of arithmetic = fundamental building block of all positive integers).\index{Zahlentheorie!Hauptsatz}

\begin{satz}\label{thm-pz-prod}
Jedes Element $n$ gr"o"ser als $1$ der nat"urlichen Zahlen l"asst sich als Produkt
$n = p_1 \cdot p_2 \cdot \dots \cdot p_m$ von Primzahlen schreiben.
Sind zwei solche Zerlegungen
$$n =  p_1 \cdot p_2 \cdots p_m = p'_1 \cdot p'_2 \cdots p'_{m'}$$
gegeben, dann gilt nach eventuellem Umsortieren $\;m = m'\;$ und  f"ur alle $i$:  $\;p_i = p'_i$. \\
($p_1, p_2, \dots, p_m$ nennt man die Primfaktoren\index{Primfaktor} von n).
\end{satz}

In anderen Worten: Jede nat"urliche Zahl au"ser der $1$ l"asst sich auf genau eine Weise als Produkt von
Primzahlen schreiben, wenn man von der Reihenfolge der Faktoren absieht. Die Faktoren sind also
eindeutig (die {\em Expansion in Faktoren} ist eindeutig)!
Zum Beispiel ist
$$ 60 = 2 \cdot 2 \cdot 3 \cdot 5 = 2^2\cdot 3^1 \cdot 5^1 $$
Und das ist --- bis auf eine ver"anderte Reihenfolge der Faktoren
--- die einzige M"oglichkeit, die Zahl $60$ in Primfaktoren zu
zerlegen. Wenn man nicht nur Primzahlen als Faktoren zul"asst,
gibt es mehrere M"oglichkeiten der Zerlegung in Faktoren und die
Eindeutigkeit (\hypertarget{uniqueness}{uniqueness}) geht verloren:
$$ 60 = 1 \cdot 60 = 2 \cdot 30 = 4 \cdot 15 = 5 \cdot 12 =6 \cdot 10 = 2 \cdot 3 \cdot 10 =
        2 \cdot 5 \cdot 6 = 3 \cdot 4 \cdot 5 = \cdots . $$

Der folgende Absatz wendet sich eher an die mit der mathematischen Logik vertrauteren Menschen:
Der 1. Hauptsatz ist nur scheinbar selbstverst"andlich\label{remFundTheoOfArithm}. Man kann viele andere Zahlenmengen
(ungleich der positiven ganzen Zahlen gr"o"ser als 1) konstruieren, bei denen selbst eine Zerlegung in
die Primfaktoren dieser Mengen nicht eindeutig ist:
In der Menge $M = \{1, 5, 10, 15, 20, \cdots\}$ gibt es unter der Multiplikation kein Analogon zum Hauptsatz.
Die ersten f"unf Primzahlen dieser Folge sind $5, 10, 15, 20, 30$ (beachte: $10$ ist prim, da innerhalb
dieser Menge $5$ kein Teiler von $10$ ist --- das Ergebnis $2$ ist kein Element der gegebenen Grundmenge
$M$). Da in $M$ gilt:
$$ 100 = 5 \cdot 20 = 10 \cdot 10 $$
und sowohl $5, 10, 20$ Primzahlen dieser Menge sind, ist hier die Zerlegung in Primfaktoren nicht
eindeutig.

% --------------------------------------------------------------------------
\subsection{Wie viele Primzahlen gibt es?}

F"ur die nat"urlichen Zahlen sind die Primzahlen vergleichbar mit den 
Elementen in der Chemie oder den Elementarteilchen in der Physik 
(vgl. \cite[S. 22]{Blum1999}).

W"ahrend es nur $92$ nat"urliche chemische Elemente gibt, ist die Anzahl 
der Primzahlen unbegrenzt.
Das wusste schon der Grieche \index{Euklid} Euklid\footnote{%
Euklid, griechischer Mathematiker des 4./3. Jahrhunderts vor Christus.
Wirkte an der Akademie in Alexandria und verfasste mit den
\glqq Elementen\grqq~ das bekannteste systematische Lehrbuch
der griechischen Mathematik.}
im dritten vorchristlichen Jahrhundert.
\begin{satz}[Euklid\footnote{Die "ublich gewordene Benennung bedeutet nicht
unbedingt, dass Euklid der Entdecker des Satzes ist, da dieser
nicht bekannt ist. Der Satz wird bereits in Euklids \glqq Elementen\grqq ~(Buch IX, Satz 20) 
formuliert und bewiesen. Die dortige Formulierung ist insofern bemerkenswert,
als sie das Wort \glqq unendlich\grqq~ nicht verwendet; sie lautet
$$
O\acute{\iota}~\pi\varrho\tilde{\omega}\tau o \iota~\grave{\alpha}\varrho\iota\vartheta\mu o\grave{\iota}~
\pi\lambda\varepsilon\acute{\iota}o \upsilon\varsigma~\varepsilon\grave{\iota}\sigma\grave{\iota}~
\pi\alpha\nu\tau\grave{o}\varsigma~\tau o \tilde{\upsilon}~
\pi\varrho o \tau\varepsilon\vartheta\acute{\varepsilon}\nu\tau o \varsigma~
\pi\lambda\acute{\eta}\vartheta\ o \upsilon\varsigma~
\pi\varrho\acute{\omega}\tau\omega\nu~
\grave{\alpha}\varrho\iota\vartheta\mu\tilde{\omega}\nu,
$$
zu deutsch: Die Primzahlen sind mehr als jede vorgegebene Menge von Primzahlen.
}]\label{thm-pz-euklid}\hypertarget{thm-pz-euklid}{} % Ende der Fu"snote
Die Folge der Primzahlen bricht nicht ab, es gibt also unendlich 
viele Primzahlen.
\end{satz}

Sein Beweis, dass es unendlich viele Primzahlen gibt, gilt bis heute als 
ein Glanzst"uck mathematischer "Uberlegung und Schlussfolgerung 
(Widerspruchsbeweis\index{Widerspruchsbeweis}). 
Er nahm an, es gebe nur endlich viele Primzahlen und damit eine gr"o"ste
Primzahl. Daraus zog er solange logische Schl"usse, bis er auf einen
offensichtlichen Widerspruch stie"s. Damit musste etwas falsch sein. Da 
sich in die Schlusskette kein Lapsus eingeschlichen hatte, konnte es nur 
die Annahme sein. Demnach musste es unendlich viele Primzahlen geben!

\hypertarget{euklid}{}
\paragraph{Euklid's Widerspruchsbeweis}
\index{Euklid's Widerspruchsbeweis}\index{Widerspruchsbeweis}
f"uhrt die Argumentation wie folgt:

\begin{Beweis}{}
{\bf Annahme:} \quad Es gibt {\em endlich} viele Primzahlen.
\\*[4pt] {\bf Schluss:} \quad Dann lassen sie sich auflisten $p_1
< p_2 < p_3 < \dots < p_n$, wobei $n$ f"ur die (endliche) Anzahl
der Primzahlen steht. $p_n$ w"are also die gr"o"ste Primzahl. Nun
betrachtet Euklid die Zahl $a = p_1 \cdot p_2 \cdots p_n +1$.
Diese Zahl kann keine Primzahl sein, da sie in unserer
Primzahlenliste nicht auftaucht. Also muss sie durch eine Primzahl
teilbar sein. D.h. es gibt eine nat"urliche Zahl $i$ zwischen $1$
und $n$, so dass $p_i$ die Zahl $a$ teilt. Nat"urlich teilt $p_i$
auch das Produkt $a-1 = p_1 \cdot p_2 \cdots p_n$, da $p_i$ ja ein
Faktor von $a-1$ ist. Da $ p_i $ die Zahlen $ a $ und $ a-1 $
teilt, teilt sie auch die Differenz dieser Zahlen. Daraus folgt:
$p_i$ teilt  $a - (a-1) = 1$. $p_i$ m"usste also $1$ teilen und
das ist unm"oglich.\\*[4pt] 
{\bf Widerspruch}: \quad Unsere Annahme war falsch.\par
Also gibt es {\em unendlich} viele Primzahlen
(siehe \hyperlink{primhfk}{"Ubersicht unter \ref{s:primhfk}} "uber die
Anzahl von Primzahlen in verschiedenen Intervallen).
\end{Beweis} 

\par \vskip + 10pt

Wir erw"ahnen hier auch noch eine andere, auf den ersten Blick 
"uberraschende Tatsache, dass n"amlich in der Folge aller 
Primzahlen $p_1, p_2, \cdots $ L"ucken von beliebig gro"ser 
L"ange $n$ auftreten. Unter den $n$ aufeinanderfolgenden 
nat"urlichen Zahlen
$$ 
    (n+1)!+2, \cdots, (n+1)!+(n+1),
$$
ist keine eine Primzahl, da ja in ihnen der Reihe nach die 
Zahlen $2,\cdots, n+1$ als echte Teiler enthalten sind
(Dabei bedeutet $n!$ das Produkt der ersten $n$ nat"urlichen 
Zahlen, also $n!=n*(n-1)* \cdots *3*2*1$). 


% --------------------------------------------------------------------------
% --------------------------------------------------------------------------
\vskip + 20pt
\subsection{Die Suche nach sehr gro"sen Primzahlen}
\label{search_for_very_big_primes}   % chap. 3.4

Die gr"o"sten heute bekannten Primzahlen haben mehrere
Millionen Stellen. Das ist unvorstellbar gro"s. Die Anzahl
der Elementarteilchen im Universum wird auf eine \glqq nur\grqq\
$80$-stellige Zahl gesch"atzt \hyperlink{grosord}{(siehe
"Ubersicht unter \ref{s:grosord} "uber verschiedene Gr"o"senordnungen /
Dimensionen)}.


% --------------------------------------------------------------------------
\hypertarget{RecordPrimes}{}
\subsubsection{Die 10 gr"o"sten bekannten Primzahlen (Stand Mai 2005)} 
\index{Primzahlrekorde}
\label{RecordPrimes}

In der folgenden Tabelle sind die 10 gr"o"sten bekanntesten Primzahlen und
eine Beschreibung des jeweiligen Zahlentyps aufgef"uhrt\footnote{%
Eine jeweils aktuelle Fassung findet sich im Internet unter 
     \href{http://primes.utm.edu/largest.html}
  {\texttt{http://primes.utm.edu/largest.html}}.
}:


%	10 & $1.372.930^{131.072}+1$ &   804.474 & 2003 & Verallg. Fermat\footnote{%
% $ 1.372.930^{131.072} + 1 = 1.372.930^{(2^{17})}+1 $ } \\

\begin{table}[h]
\begin{center}
\begin{tabular}{|c|cccc|}
\hline
 	& {\bf Definition} & {\bf Dezimalstellen} & {\bf Wann} & {\bf Beschreibung} \\
\hline
	1  & $2^{25.964.951}-1$ & 7.816.230 & 2005 & Mersenne, 42. bekannte \\
	2  & $2^{24.036.583}-1$ & 7.235.733 & 2004 & Mersenne, 41. bekannte \\
	3  & $2^{20.996.011}-1$ & 6.320.430 & 2003 & Mersenne, 40. bekannte \\
	4  & $2^{13.466.917}-1$ & 4.053.946 & 2001 & Mersenne, M-39 \\
	5  & $28.433 \cdot 2^{7.830.457}+1$ & 2.357.207 & 2004 & Verallg. Mersenne \\
	6  & $2^{ 6.972.593}-1$ & 2.098.960 & 1999 & Mersenne, M-38 \\
	7  & $5.359 \cdot 2^{5.054.502}+1$ & 1.521.561 & 2003 & Verallg. Mersenne \\
	8  & $2^{ 3.021.377}-1$ &   909.526 & 2001 & Mersenne, M-37 \\
	9  & $2^{ 2.976.221}-1$ &   895.932 & 2001 & Mersenne, M-36 \\
	10 & $1.372.930^{131.072}+1$ &   804.474 & 2003 & Verallg. Fermat\footnotemark \\
\hline
\end{tabular}
\caption{Die 10 gr"o"sten Primzahlen und ihr jeweiliger Zahlentyp (Stand Mai 2005)}