primes.tex

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

\end{center}
\end{table} 
\footnotetext{%
$ 1.372.930^{131.072} + 1 = 1.372.930^{(2^{17})}+1 $ 
} 
%be_2005: footnetmark und footnotetext statt nur footnote (sonst sieht man nur die
%         Fussnoten-Nr., aber nicht den Text!
%be_2005: Erzwingen, dass die Abb. noch in diesem Kapitel !

Die gr"o"ste bekannte Primzahl ist eine Mersenne-Primzahl.
Diese wurde vom \hyperlink{GIMPS-project}{GIMPS-Projekt} gefunden.

Unter den gr"o"sten bekannten Primzahlen befinden sich au"serdem Zahlen
vom Typ \hyperlink{generalizedMersennenumbers}{verallgemeinerte Mersennezahl} 
(Kapitel~\ref{generalized-mersenne-no1})
und 
vom Typ \hyperlink{generalizedFermatprimes}{verallgemeinerte Fermatzahl} 
(Kapitel~\ref{generalized-fermat}).


% --------------------------------------------------------------------------
\subsubsection{Spezielle Zahlentypen -- Mersennezahlen und Mersenne-Primzahlen} 
\hypertarget{MersenneNumbers01}{}
\label{zahlentyp_mersenne}
\index{Mersenne!Mersennezahl}

Nahezu alle bekannten riesig gro"sen Primzahlen sind spezielle 
Kandidaten, sogenannte \index{Mersenne Marin}{\em Mersennezahlen}\footnote{%
Marin Mersenne, franz"osischer Priester und Mathematiker,
08.09.1588$-$01.09.1648.
\index{Mersenne, Marin}
}
der Form $2^p -1,$ wobei $p$ eine Primzahl ist.
Nicht alle Mersennezahlen sind prim:
$$
\begin{array}{cl}
2^2 - 1 = 3 & \Rightarrow {\rm prim} \\
2^3 - 1 = 7 & \Rightarrow {\rm prim} \\
2^5 - 1 = 31    & \Rightarrow {\rm prim} \\
2^7 - 1 = 127    & \Rightarrow {\rm prim} \\
2^{11} - 1 = 2.047 = 23 \cdot 89    & \Rightarrow  {\rm NICHT~prim} !
\end{array}
$$

\index{Zahlen!Mersennezahl}
\index{Mersenne!Mersennezahl} 
\index{Mersenne!Satz} 

Dass Mersennezahlen nicht immer Primzahlen (Mersenne-Primzahlen) sind, 
wusste auch schon Mersenne (siehe Exponent $p = 11$).
Eine Mersennezahl, die prim ist, wird Mersenne-Primzahl
\index{Mersenne!Mersenne-Primzahl} genannt.  \\

Dennoch ist ihm der interessante Zusammenhang zu verdanken, dass eine 
Zahl der Form $2^n-1$ keine Primzahl sein kann, wenn $n$ eine 
zusammengesetzte Zahl ist:

\begin{satz}[Mersenne]\label{thm-pz-mersenne}
  Wenn $2^n - 1$ eine Primzahl ist, dann folgt, $n$ ist ebenfalls eine 
  Primzahl (oder anders formuliert: $2^n - 1$ ist nur dann prim, 
  wenn $n$ prim ist).
\end{satz}

\begin{Beweis}{}
Der Beweis des Satzes von Mersenne kann durch Widerspruch
\index{Widerspruchsbeweis}
durchgef"uhrt werden. Wir nehmen also an, dass es eine
zusammengesetzte nat"urliche Zahl $ n $ mit echter Zerlegung
$\; n=n_1 \cdot n_2 $
gibt, mit der Eigenschaft, dass $ 2^n -1 $ eine
Primzahl ist.

Wegen
\begin{eqnarray*}
(x^r-1)((x^r)^{s-1} + (x^r)^{s-2} + \cdots + x^r +1) & = &  ((x^r)^s + (x^r)^{s-1} + (x^r)^{s-2} + \cdots + x^r) \\
&  & -((x^r)^{s-1} + (x^r)^{s-2} + \cdots + x^r +1)  \\
& = & (x^r)^s -1 = x^{rs } -1,
\end{eqnarray*}
folgt
\[ 2^{n_1 n_2} - 1 = (2^{n_1} -1)((2^{n_1})^{n_2 -1} + (2^{n_1})^{n_2 -2} + \cdots + 2^{n_1} + 1). \]
Da $ 2^n - 1 $ eine Primzahl ist, muss einer der obigen beiden
Faktoren auf der rechte Seite gleich 1 sein. Dies kann nur dann
der Fall sein, wenn $ n_1 =1 $ oder $ n_2 =1$ ist. Dies ist aber
ein Widerspruch zu unserer Annahme. Deshalb ist unsere Annahme
falsch. Also gibt es keine zusammengesetzte Zahl $ n, $ so dass $
2^n -1 $ eine Primzahl ist.
\end{Beweis} 

\vskip + 5pt
\hypertarget{Mer-nums-not-always-prim}{}
Leider gilt dieser Satz nur in einer Richtung (die Umkehrung gilt
nicht, keine "Aquivalenz): das hei"st, dass es prime Exponenten gibt,
f"ur die die zugeh"orige Mersennezahl {\bf nicht} prim ist (siehe das obige 
Beispiel $2^{11}-1, $ wo $11$ prim ist, aber $2^{11}-1$ nicht).

Mersenne behauptete, dass $2^{67}-1$ eine Primzahl ist. Auch zu
dieser Behauptung gibt es eine interessante mathematische Historie:
Zuerst dauerte es "uber 200 Jahre, bis \index{Lucas, Edouard}
Edouard Lucas (1842-1891) bewies, dass diese Zahl zusammengesetzt
ist. Er argumentierte aber indirekt und kannte keinen der
Faktoren. Dann zeigte Frank Nelson Cole\index{Cole, Frank Nelson}\footnote{%
Frank Nelson Cole, amerikanischer Mathematiker, 20.09.1861$-$26.05.1926.} 1903,
aus welchen Faktoren diese Primzahl besteht:
$$ 2^{67} -1 =147. 573. 952. 589. 676. 412. 927 = 193. 707. 721 \cdot 761. 838. 257. 287. $$
Er gestand, 20 Jahre an der Faktorisierung \index{Faktorisierung} (Zerlegung in Faktoren)%
\footnote{%
  Mit CrypTool\index{CrypTool} k"onnen Sie Zahlen auf folgende Weise 
  faktorisieren: Men"u {\bf Einzelverfahren \textbackslash{} RSA-Kryptosystem 
  \textbackslash{} Faktorisieren einer Zahl}. \\
  In sinnvoller Zeit zerlegt CrypTool Zahlen bis 250 Bit L"ange.
  Zahlen gr"o"ser als 1024 Bit werden zur Zeit von CrypTool nicht angenommen. \\
  Die aktuellen Faktorisierungsrekorde finden Sie in Kapitel \ref{NoteFactorisation}.
  \index{Faktorisierung!Faktorisierungsrekorde}
}
dieser 21-stelligen Dezimalzahl gearbeitet zu haben!

Dadurch, dass man bei den Exponenten der Mersennezahlen nicht alle 
nat"urlichen Zahlen verwendet, sondern nur die Primzahlen, engt man
den {\em Versuchsraum} deutlich ein. Die derzeit bekannten 
Mersenne-Primzahlen \index{Mersenne!Mersenne-Primzahl} gibt es 
f"ur die Exponenten\footnote{%
Auf der folgenden Seite von Landon Curt Noll\index{Noll, Landon Curt} 
werden in einer Tabelle alle Mersenne-Primzahlen samt Entdeckungsdatum und 
Wert in Zahlen- und Wortform aufgelistet:
      \href{http://www.isthe.com/chongo/tech/math/prime/mersenne.html}
   {\texttt{http://www.isthe.com/chongo/tech/math/prime/mersenne.html}}. \\
Siehe auch:
      \href{http://www.utm.edu/}
   {\texttt{http://www.utm.edu/}}.
                             }
$$
\begin{array}{c}
2, ~ 3, ~ 5, ~ 7, ~ 13, ~ 17, ~ 19, ~ 31, ~ 61, ~ 89, ~ 107, ~ 127, ~ 521, ~ 607, ~ 1.279, ~ 2.203, ~ 2.281, ~ 3.217, ~ 4.253, \\
4.423, ~9.689, ~ 9.941, ~ 11.213, ~ 19.937, ~ 21.701, ~ 23.207, ~ 44.497, ~ 86.243, ~ 110.503, ~ 132.049,\\
216.091, ~ 756.839, ~ 859.433, ~ 1.257.787, ~ 1.398.269, ~ 2.976.221, ~ 3.021.377, ~ 6.972.593,\\
 ~ 13.466.917,  ~ 20.996.011,  ~ 24.036.583 , ~ 25.964.951.
% be_2005_UPDATEN_if-new-mersenne-prime-appears          ~ xxx.xxx.xxx.
\end{array}
$$
Damit sind heute
$42$                  % be_2005_UPDATEN_if-new-mersenne-prime-appears
Mersenne-Primzahlen\index{Primzahl!Mersenne}\index{Mersenne!Mersenne-Primzahl} 
bekannt. F"ur die ersten 39              % be_2005_UPDATEN_if-new-mersenne-prime-appears
Mersenne-Primzahlen wei"s man inzwischen, dass diese Liste vollst"andig ist. 
Die Exponenten bis zur 40.  % be_2005_UPDATEN_if-new-mersenne-prime-appears
bekannten Mersenne-Primzahl sind noch nicht vollst"andig gepr"uft\footnote{%
Den aktuellen Status der Pr"ufung findet man auf der Seite:
      \href{http://www.mersenne.org/status.htm}
   {\texttt{http://www.mersenne.org/status.htm}}.\\
Hinweise, wie man Zahlen auf ihre Primalit"at pr"ufen kann, finden sich
in Kapitel \ref{primality_tests}, Primzahltests\index{Primzahltest}.
                                                                          }. 

Die $19$. Zahl
mit dem Exponenten $4.253$ war die erste mit mindestens $1.000$
Stellen im Zehnersystem (der Mathematiker Samual \index{Yates,
Samual} Yates pr"agte daf"ur den Ausdruck {\em titanische}
\index{Primzahl!titanische} Primzahl; sie wurde 1961 von Hurwitz
gefunden); die $27$. Zahl mit dem Exponenten $44.497$ war die
erste mit mindestens $10.000$ Stellen im Zehnersystem (Yates
pr"agte daf"ur den Ausdruck \index{Primzahl!gigantische}  {\em
gigantische} Primzahl. Diese Bezeichnungen sind heute l"angst
veraltet).

% \vskip - 4pt \noindent
% \begin{quote}
% (Der Supercomputerhersteller SGI Cray Research besch"aftigte nicht
% nur hervorragende Mathematiker, sondern benutzte die Primzahltests
% auch als Benchmarks f"ur seine Maschinen.)
% \end{quote}

% \vspace{-10pt}
% \begin{itemize}
%  \item[] \href{http://reality.sgi.com/chongo/prime/prime_press.html}
%               {\texttt{http://reality.sgi.com/chongo/prime/prime\_press.html}}
% \end{itemize}


\vskip +25 pt
\paragraph{M-37 -- Januar 1998} \index{Mersenne!Mersenne-Primzahl!M-37}\mbox{}

Die 37. Zahl Mersenne-Primzahl, $$2^{3.021.377} - 1 $$
wurde im Januar 1998 gefunden und hat
909.526 Stellen im Zehnersystem, was 33 Seiten in der FAZ entspricht!


\vskip +25 pt
\paragraph{M-38 -- Juni 1999}\index{Mersenne!Mersenne-Primzahl!M-38}\mbox{}

Die 38. Mersenne-Primzahl, genannt M-38, $$ 2^{6.972.593} - 1 $$
wurde im Juni 1999 gefunden und hat $2.098.960$ Stellen im
Zehnersystem (das entspricht rund 77 Seiten in der FAZ).


\vskip +25 pt
\paragraph{M-39 -- Dezember 2001}\index{Mersenne!Mersenne-Primzahl!M-39}\mbox{}

Die 39. Mersenne-Primzahl, genannt M-39, $$2^{13.466.917}-1$$ 
wurde am 6.12.2001 bekanntgegeben: genau genommen war am 6.12.2001 
die Verifikation der am 14.11.2001 von dem kanadischen Studenten 
Michael Cameron gefundenen Primzahl abgeschlossen.
Diese Zahl hat rund 4 Millionen Stellen (genau 4.053.946 Stellen). 
Allein zu ihrer Darstellung
$$
924947738006701322247758 \; \cdots  \; 1130073855470256259071
$$
br"auchte man in der FAZ knapp 200 Seiten.

Inzwischen (Stand Mai 2005) wurden alle primen Exponenten kleiner als
$ 13.466.917 $ getestet und nochmal gepr"uft (siehe die Homepage des 
GIMPS-Projekts: {\href{http://www.mersenne.org} {\tt http://www.mersenne.org}}):
somit k"onnen wir sicher sein, dass dies wirklich 
die 39. Mersenne-Primzahl ist und dass keine kleineren unentdeckten
Mersenne-Primzahlen existieren.

%\vskip +25 pt
%\paragraph{Mxxxxxxxxx -- Juni 2003 -- M-40 ?}
%\index{Mersenne!Mersenne-Primzahl!M-40}\mbox{}

%Als 40. Mersenne-Primzahl wurde die folgende Zahl gefunden (und schon als M-40
%bezeichnet, obwohl noch nicht sicher ist, ob es zwischen M-39 und
%Mxxxxxxxxxx nicht noch weitere Mersenne-Primzahlen gibt), $$2^{xx.xxx.xxx}-1$$ 
%Bekanntgegeben wurde sie am xx.06.2003: genau genommen war am xx.06.2003 
%die Verifikation der am 02.06.2003 von xxxxxxxxxxxxxxxx 
%gefundenen Primzahl abgeschlossen. 
%Initiator und Projektleiter George Woltman gibt eine gefundene Mersenne-Zahl
%erst bekannt, wenn eine Kontrollrechnung best"atigt, dass sie prim ist.
%Diese Zahl hat rund xxx Millionen Stellen (genau xx.xxx.xxx Dezimalstellen).
%Die erste Meldung in Deutsch dazu erschien 
%m.W. im Heise-Ticker\index{Heise-Ticker}:
%{\href{http://www.heise.de/newsticker/data/as-02.06.03-000/} 
%  {\tt http://www.heise.de/newsticker/data/as-02.06.03-000/} }.

Inzwischen (Stand Mai 2005) wurde schon die 42. bekannte Mersenne-Primzahl gefunden.




\vskip +25 pt
\paragraph{GIMPS}\index{GIMPS}\mbox{}
\hypertarget{GIMPS-project}{}

Das GIMPS-Projekt\index{GIMPS} (Great Internet Mer"-senne-Prime Search)
wurde 1996 von George Woltman\index{Woltman, George} gegr"undet, um neue 
gr"o"ste Mersenne-Primzahlen zu finden 
({\href{http://www.mersenne.org} {\tt http://www.mersenne.org}}).
Genauere Erl"auterungen zu diesem Zahlentyp finden sich unter
\hyperlink{MersenneNumbers02}{Mersennezahlen} und 
\hyperlink{MersenneNumbers01}{Mersenne-Primzahlen}.

Bisher hat das GIMPS-Projekt acht
            % be_2005_UPDATEN_if-new-mersenne-prime-appears
gr"o"ste Mersenne-Primzahlen entdeckt, inclusive der gr"o"sten bekannten
Primzahl "uberhaupt. 

Die folgende Tabelle enth"alt diese Mersenne Rekord-Primzahlen\footnote{%
Eine up-to-date gehaltene Version dieser Tabelle steht im Internet unter
     \href{http://www.mersenne.org/history.htm}
  {\texttt{http://www.mersenne.org/history.htm}}.
}:

            % be_2005_UPDATEN_if-new-mersenne-prime-appears
\begin{table}[h]
\begin{center}
\begin{tabular}{|cccc|}
\hline
	{\bf Definition} & {\bf Dezimalstellen} & {\bf Wann} & {\bf Wer} \\
\hline
	$2^{25.964.951}-1$ & 7.816.230 & 18. Februar 2005  & Dr. Martin Nowak \\
	$2^{24.036.583}-1$ & 7.235.733 & 15. Mai 2004      & Josh Findley     \\
	$2^{20.996.011}-1$ & 6.320.430 & 17. November 2003 & Michael Shafer   \\