primes.tex

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

	$2^{13.466.917}-1$ & 4.053.946 & 14. November 2001 & Michael Cameron  \\
	$2^{ 6.972.593}-1$ & 2.098.960 & 1. Juni 1999      & Nayan Hajratwala \\
	$2^{ 3.021.377}-1$ &   909.526 & 27. Januar 1998   & Roland Clarkson  \\
	$2^{ 2.976.221}-1$ &   895.932 & 24. August 1997   & Gordon Spence    \\
	$2^{ 1.398.269}-1$ &   420.921 & November 1996     & Joel Armengaud   \\
\hline
\end{tabular}
\caption{Die gr"o"sten vom GIMPS-Projekt gefundenen Primzahlen (Stand Mai 2005)}
\end{center}
\end{table} 

%be_2005: Erzwingen, dass die Abb. noch in diesem Kapitel !

Dr. Richard Crandall\index{Crandall, Richard} erfand den Transformations-Algorithmus,
der im GIMPS-Programm benutzt wird. George Woltman implementierte 
Crandall's Algorithmus in Maschinensprache, wodurch das Primzahlenprogramm 
eine vorher nicht da gewesene Effizienz erhielt. 
Diese Arbeit f"uhrte zum GIMPS-Projekt.

Am 1. Juni 2003 wurde dem GIMPS-Server eine Zahl gemeldet, die evtl. die 40. 
Mersenne-Primzahl sein konnte. Diese wurde dann wie "ublich "uberpr"uft,
bevor sie ver"offentlich werden sollte. 
Leider musste der Initiator und GIMPS-Projektleiter George Woltman Mitte Juni
melden, dass diese Zahl zusammengesetzt war (dies war die erste falsche
positive R"uckmeldung eines Clients an den Server in 7 Jahren).

Am GIMPS-Projekt beteiligen sich z.Zt. rund 130.000 
freiwillige Amateure und Experten, die ihre Rechner in das von der 
Firma entropia organisierte \glqq primenet\grqq~ einbinden.






% --------------------------------------------------------------------------
\vskip +25 pt
\subsubsection{Wettbewerb der Electronic Frontier Foundation (EFF)}\index{EFF}
Angefacht wird diese Suche noch zus"atzlich durch einen Wettbewerb, den die
Non\-profit-Orga"-nisa"-tion EFF (Electronic Frontier Foundation) mit den
Mitteln eines unbekannten Spenders gestartet hat. Den Teilnehmern winken 
Gewinne im Gesamtwert von 500.000 USD, wenn sie die l"angste Primzahl
finden. Dabei sucht der unbekannte Spender nicht nach dem schnellsten Rechner,
sondern er will auf die M"oglichkeiten des {\em cooperative networking} 
aufmerksam machen: \\
{\href{http://www.eff.org/coopawards/prime-release1.html}{\tt http://www.eff.org/coopawards/prime-release1.html}}

Der Entdecker von M-38 erhielt f"ur die Entdeckung der ersten Primzahl
mit "uber 1 Million Dezimalstellen von der EFF eine Pr"amie von 50.000 USD. 

% be_2005_UPDATEN_if-new-mersenne-prime-appears
Die n"achste Pr"amie von 100.000 USD gibt es von der EFF f"ur eine Primzahl
mit mehr als 10 Millionen Dezimalstellen.

Nach den Preisregeln der EFF sind dann als n"achste Stufe 150.000 US-Dollar
f"ur eine Primzahl mit mehr als 100 Millionen Stellen ausgelobt.                         


Edouard Lucas\index{Lucas, Edouard} (1842-1891) hielt "uber 70 Jahre den 
Rekord der gr"o"sten bekannten Primzahl, indem er nachwies, dass 
$2^{127}-1$ prim ist. Solange wird wohl kein neuer Rekord mehr Bestand haben.


% --------------------------------------------------------------------------
\subsection{Primzahltests}
\label{primality_tests}   % chap. 3.5
\index{Primzahltest}

F"ur die Anwendung sicherer Verschl"usselungsverfahren braucht man sehr gro"se
Primzahlen (im Bereich von $2^{2.048}$, das sind Zahlen im Zehnersystem mit
"uber $600$ Stellen!).

Sucht man nach den Primfaktoren, um zu entscheiden, ob eine Zahl prim ist,
dauert die Suche zu lange, wenn auch der kleinste Primfaktor riesig ist.
Die Zerlegung in Faktoren mittels rechnerischer systematischer Teilung oder
mit dem \hyperlink{SieveEratosthenes01}{Sieb des Eratosthenes} 
\index{Eratosthenes!Sieb} ist mit heutigen Computern anwendbar 
f"ur Zahlen mit bis zu circa $20$ Stellen im Zehnersystem.
Die gr"o"ste Zahl, die bisher in ihre beiden ann"ahernd gleich gro"sen
Primfaktoren zerlegt werden konnte, hatte 200 Stellen 
(vgl. \hyperlink{RSA-200-chap3}{RSA-200} in Kapitel~\ref{NoteFactorisation}).
% be_2005 Das ist eine gute Art zu referenzieren !!!!!!!!!!!!!!!

% be_2005_UPDATEN_if-new-factorization-record-appears

Ist aber etwas "uber die {\em Bauart} (spezielle Struktur) der fraglichen 
Zahl bekannt, gibt es sehr hochentwickelte Verfahren, die deutlich schneller
sind. Diese Verfahren beantworten nur die Primalit"atseigenschaft einer Zahl,
k"onnen aber nicht die Primfaktoren sehr gro"ser zusammengesetzter Zahlen
bestimmen.

\hypertarget{FermatNumbers01}{}\label{FermatNumbers01}%
Fermat\footnote{%
Pierre de Fermat, franz"osischer Mathematiker, 17.8.1601 -- 12.1.1665.
\index{Fermat, Pierre}
}
\index{Fermat, Pierre} hatte im 17. Jahrhundert an Mersenne
\index{Mersenne, Marin} geschrieben, dass er vermute, 
dass alle Zahlen der Form $$ f(n) = 2^{2^n} + 1 $$ 
f"ur alle ganzen Zahlen $ n \geq 0 $ prim seien 
(\hyperlink{FermatNumbers02}{siehe unten}, Kapitel~\ref{L-FermatNumbers02}).
\index{Zahlen!Fermatzahl}\index{Fermat!Fermatzahl}

Schon im 19. Jahrhundert wusste man, dass die $29$-stellige Zahl
$$ f(7) = 2^{2^7} + 1 $$
keine Primzahl ist. Aber erst 1970 fanden Morrison/Billhart ihre Zerlegung.
\begin{eqnarray*}\label{F7Morrison}
f(7) & = & 340.282.366.920.938.463.463.374.607.431.768.211.457 \\
& = & 59. 649. 589. 127. 497. 217 \cdot  5.704.689.200.685.129.054.721
\end{eqnarray*}

Auch wenn sich Fermat bei seiner Vermutung irrte, so stammt in diesem
Zusammenhang von ihm doch ein sehr wichtiger Satz: Der (kleine)
Fermatsche Satz, den Fermat im Jahr 1640 aufstellte, ist der 
Ausgangspunkt vieler schneller Primzahltests 
(\hyperlink{KleinerSatzFermat-chap3}{siehe Kap.
\ref{Label_KleinerSatzFermat-chap3}}).

\hypertarget{KleinerSatzFermat-chap2}{}
\index{Fermat!kleiner Satz}
\begin{satz}[\glqq kleiner\grqq\ Fermat]\label{thm-pz-fermat1}
Sei $p$ eine Primzahl und $a$ eine beliebige ganze Zahl, dann gilt f"ur alle $a$
$$a^p \equiv a \; {\rm mod} \; p.$$
Eine alternative Formulierung lautet: \\
Sei $p$ eine Primzahl und $a$ eine beliebige ganze Zahl, die kein
Vielfaches von $p$ ist (also $a \not\equiv 0 \; {\rm mod} \; p$),
dann gilt $a^{p-1} \equiv 1 \; {\rm mod} \; p$.
\end{satz}

Wer mit dem Rechnen mit Resten (Modulo-Rechnung) nicht so vertraut ist, 
m"oge den Satz einfach so hinnehmen oder erst \hyperlink{Kapitel_3}
{Kapitel \ref{Kapitel_3} \glqq Einf"uhrung in die elementare Zahlentheorie mit 
Beispielen\grqq} lesen.   Wichtig ist, dass aus diesem Satz folgt, dass wenn
diese Gleichheit f"ur irgendein ganzes $a$ nicht erf"ullt ist, dann ist
$p$ keine Primzahl! Die Tests lassen sich (zum Beispiel f"ur die erste
Formulierung) leicht mit der {\em Testbasis} $a = 2$ durchf"uhren.

Damit hat man ein Kriterium f"ur Nicht-Primzahlen, also einen negativen Test, aber noch keinen
Beweis, dass eine Zahl $a$ prim ist.
Leider gilt die Umkehrung zum Fermatschen Satz nicht, sonst h"atten wir einen einfachen Beweis f"ur
die Primzahleigenschaft (man sagt auch, man h"atte dann ein einfaches Primzahlkriterium).


\vskip +25 pt
\paragraph{Pseudoprimzahlen}%
\index{Primzahl!Pseudoprimzahl}\index{Zahlen!Pseudoprimzahl}%
\hypertarget{HT--Pseudoprimenumber01}{}\label{L-Pseudoprimenumber01}%
\mbox{}
\vskip +10 pt
Zahlen n, die die Eigenschaft
$$ 2^n \equiv 2 \;{\rm mod}\; n $$
erf"ullen, aber nicht prim sind, bezeichnet man als {\em Pseudoprimzahlen} 
(der Exponent n ist also keine Primzahl).
Die erste Pseudoprimzahl ist $$ 341 = 11 \cdot 31 .$$

\vskip +25 pt
\paragraph{Carmichaelzahlen}%
\index{Zahlen!Carmichaelzahl}%
\hypertarget{HT-Carmichael-number01}{}\label{L-Carmichael-number01}%
\mbox{}
\vskip +10 pt
Es gibt Zahlen, die den Fermat-Test mit allen Basen bestehen und doch nicht
prim sind: diese Zahlen hei"sen {\em Carmichaelzahlen}. Die erste ist
$$ 561 = 3 \cdot 11 \cdot 17 .$$

\vskip +25 pt
\paragraph{Starke Pseudoprimzahlen}%
\index{Primzahl!starke Pseudoprimzahlen} \index{Zahlen!starke Pseudoprimzahl}%
\hypertarget{HT-Strongpseudoprimenumber01}{}\label{L-Strongpseudoprimenumber01}%
\mbox{}
\vskip +10 pt
Ein st"arkerer Test stammt von\index{Miller Gary L.}\index{Rabin, Michael O.}
Miller/Rabin\footnote{
1976 ver"offentlichte Prof. Rabin einen effizienten probabilistischen
Primzahltest, der auf einem zahlentheoretischen Ergebnis von Prof. Miller aus
der Jahr davor basierte. \\
Prof. Miller arbeitete an der Carnegie-Mellon Universit"at, School of Computer
Science. Prof. Rabin, geboren 1931, arbeitete an der Harvard und Hebrew
Universit"at.
}%
: er wird nur von sogenannten {\em starken Pseudoprimzahlen} bestanden. 
Wiederum gibt es starke Pseudoprimzahlen, die keine Primzahlen sind, aber
das passiert deutlich seltener als bei den (einfachen) Pseudoprimzahlen oder
bei den Carmichaelzahlen. Die kleinste starke Pseudoprimzahl zur Basis $2$ ist
$$ 15.841 = 7 \cdot 31 \cdot 73. $$
Testet man alle 4 Basen $2, 3, 5$ und $7$, so findet man bis $25 \cdot 10^9$
nur eine starke Pseudoprimzahl, also eine Zahl, die den Test besteht und doch keine Primzahl ist.

Weiterf"uhrende Mathematik hinter dem Rabin-Test gibt dann die Wahrscheinlichkeit an, mit der die
untersuchte Zahl prim ist (solche Wahrscheinlichkeiten liegen heutzutage bei circa  $10^{-60}$).

Ausf"uhrliche Beschreibungen zu Tests, um herauszufinden, ob eine Zahl
prim ist, finden sich zum Beispiel unter:
\vspace{-10pt}
\begin{itemize}
  \item[] \href{http://www.utm.edu/research/primes/mersenne.shtml}
               {\texttt{http://www.utm.edu/research/primes/mersenne.shtml}} \\
          \href{http://www.utm.edu/research/primes/prove/index.html}
               {\texttt{http://www.utm.edu/research/primes/prove/index.html}} 
\end{itemize}



% --------------------------------------------------------------------------
\vskip +30 pt
\subsection{"Ubersicht Spezial-Zahlentypen und die Suche nach einer Formel f"ur
Primzahlen}\label{spezialzahlentypen} % chap. 3.6.
\index{Primzahl!Formel}
Derzeit sind keine brauchbaren, offenen (also nicht rekursiven) Formeln bekannt, 
die nur Primzahlen liefern (rekursiv bedeutet, dass zur Berechnung der Funktion
auf dieselbe Funktion in Abh"angigkeit einer kleineren Variablen zugegriffen wird).
Die Mathematiker w"aren schon zufrieden, wenn sie eine Formel f"anden, die wohl 
L"ucken l"asst (also nicht alle Primzahlen liefert), aber sonst keine
zusammengesetzten Zahlen (Nicht-Primzahlen) liefert.

Optimal w"are, man w"urde f"ur das Argument $n$ sofort die $n$-te Primzahl 
bekommen, also f"ur
$f(8) = 19\,$ oder f"ur  $f(52) = 239$.

Ideen dazu finden sich in
\vspace{-10pt}
\begin{itemize}
  \item[] {\href{http://www.utm.edu/research/primes/notes/faq/p_n.html}
          {\tt http://www.utm.edu/research/primes/notes/faq/p\_n.html}}.
\end{itemize}


\hyperlink{ntePrimzahl}{Die Tabelle unter \ref{s:ntePrimzahl}} enth"alt 
die exakten Werte f"ur die $n$-ten Primzahlen f"ur ausgew"ahlte $ n.$
\\

%  \glqq Primzahlformeln''
%  \glqq Primzahlformeln \grqq  (das Blank vor UND nach dem Text ist n鰐ig!
%        be_20050527: Aber dann war das Blank innerhalb der Hochkommata -> auch nicht gut
%  Fehlt es danach, wird der folgende Text direkt ohne Blank dahintergestellt!
F"ur \glqq Primzahlformeln'' werden meist ganz spezielle Zahlentypen
benutzt. Die folgende Aufz"ahlung enth"alt die verbreitetsten Ans"atze 
f"ur \glqq Primzahlformeln'', und welche Kenntnisse wir "uber
sehr gro"se Folgeglieder haben: Konnte die Primalit"at bewiesen werden?
Wenn es zusammengesetzte Zahlen sind, konnten die Primfaktoren bestimmt werden?


% --------------------------------------------------------------------------
\vskip +10 pt
\subsubsection{Mersennezahlen $f(n) = 2^n - 1$ f"ur $ n $ prim}
    \hypertarget{MersenneNumbers02}{}
    \index{Primzahl!Mersenne} \index{Mersenne!Mersenne-Primzahl}
    Wie \hyperlink{MersenneNumbers01}{oben} gesehen, liefert diese 
    Formel wohl relativ viele gro"se Primzahlen, aber es kommt -- wie 
    f"ur $n=11$ [$f(n)=2.047$] -- immer wieder vor, dass das Ergebnis 
    auch bei primen Exponenten \hyperlink{Mer-nums-not-always-prim}{nicht}
    prim ist. \\
    Heute kennt man alle Mersenne-Primzahlen mit bis zu ca. 4.000.000 
    Dezimalstellen (M-39\index{Mersenne!Mersenne-Primzahl!M-39}) \\
    ({\href{http://perso.wanadoo.fr/yves.gallot/primes/index.html}
           {\tt http://perso.wanadoo.fr/yves.gallot/primes/index.html}}).
            % be_2005_UPDATEN_if-new-mersenne-prime-appears

% --------------------------------------------------------------------------
\vskip +10 pt
\subsubsection
    [Verallgemeinerte Mersennezahlen $f(k,n) = k \cdot 2^n \pm 1$]
    {Verallgemeinerte Mersennezahlen 
    $f(k,n) = k \cdot 2^n \pm 1 $ f"ur $ n $ prim und $ k $ kleine Primzahlen}
% \quad f"ur
    \label{generalized-mersenne-no1}
    F"ur diese 1. Verallgemeinerung der 
    Mersennezahlen\index{Mersenne!Mersennezahl!verallgemeinerte} 
    gibt es (f"ur kleine $k$) 
    ebenfalls sehr schnelle Primzahltests (vgl. \cite{Knuth1981}).
    Praktisch ausf"uhren l"asst sich das zum Beispiel mit der Software