primes.tex

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

    Proths von Yves Gallot\index{Gallot, Yves} 
    ({\href{http://www.prothsearch.net/index.html}
           {\tt http://www.prothsearch.net/index.html}}).


% --------------------------------------------------------------------------
\vskip +10 pt
\subsubsection
    [Verallgemeinerte Mersennezahlen $ f(b,n) = b^n \pm 1$ / Cunningham-Projekt]
    {Verallgemeinerte Mersennezahlen
    $ f(b,n) = b^n \pm 1$ / Cunningham-Projekt}
    \hypertarget{generalizedMersennenumbers}{}

Dies ist eine 2. m"ogliche Verallgemeinerung der 
    Mersennezahlen\index{Mersenne!Mersennezahl!verallgemeinerte}.
    Im \index{Cunningham-Projekt} \textbf{Cunningham-Projekt} werden die
    Faktoren aller zusammengesetzten Zahlen bestimmt, die sich in folgender
    Weise bilden:
    $$ f(b,n) = b^n \pm 1  \quad {\rm f"ur~} b = 2, 3, 5, 6, 7, 10, 11, 12 $$
    ($b$ ist ungleich der Vielfachen von schon benutzten Basen wie $4, 8, 9$).

    Details hierzu finden sich unter:
\vspace{-10pt}
\begin{itemize}
  \item[] \href{http://www.cerias.purdue.edu/homes/ssw/cun}
               {\tt http://www.cerias.purdue.edu/homes/ssw/cun}
\end{itemize}


% --------------------------------------------------------------------------
\vskip +10 pt
\subsubsection[Fermatzahlen $f(n) = 2^{2^n} + 1$]
              {Fermatzahlen\footnotemark~$f(n) = 2^{2^n} + 1$}
    \footnotetext{%
       Die Fermatschen Primzahlen spielen unter
       anderem eine wichtige Rolle in der Kreisteilung. 
       Wie Gauss \index{Gauss, Carl Friedrich}
       bewiesen hat, ist das regul"are $p$-Eck f"ur eine Primzahl $p>2$ dann
       und nur dann mit Zirkel und Lineal konstruierbar, wenn $p$ eine 
       Fermatsche Primzahl ist.
    }
    \hypertarget{FermatNumbers02}{}
    \label{L-FermatNumbers02}
    \index{Zahlen!Fermatzahl}\index{Fermat!Fermatzahl}
    \index{Primzahl!Fermat} \index{Fermat!Fermat-Primzahl}
    Wie \hyperlink{FermatNumbers01}{oben} in Kapitel~\ref{FermatNumbers01}
    erw"ahnt, schrieb Fermat an 
    Mersenne, dass er vermutet, dass alle Zahlen dieser Form prim seien. 
    Diese Vermutung wurde jedoch von Euler (1732) widerlegt. Es gilt $641 | f(5)$\footnote{%
    Erstaunlicherweise kann man mit Hilfe des Satzes von Fermat diese Zahl leicht finden (siehe z.B. 
    \cite[S. 176]{Scheid1994})
    }. 
    
	       
%    Erstaunlicherweise w"are es f"ur ihn m"oglich gewesen, mit dem auf 
%    seinem kleinen Satz beruhenden negativen Primzahltest f"ur $n=5$ ein 
%    positives Ergebnis zu erhalten.
$$
\begin{array}{lll}
f(0) = 2^{2^0} + 1  = 2^1 + 1 & = 3 &   \mapsto {\rm ~prim}  \\
f(1) = 2^{2^1} + 1  = 2^2 + 1 & = 5 &   \mapsto {\rm ~prim}  \\
f(2) = 2^{2^2} + 1  = 2^4 + 1 & = 17 &  \mapsto {\rm ~prim}  \\
f(3) = 2^{2^3} + 1  = 2^8 + 1 & = 257 & \mapsto {\rm ~prim}  \\
f(4) = 2^{2^4} + 1  = 2^{16} + 1 &  = 65.537 &  \mapsto {\rm ~prim}  \\
f(5) = 2^{2^5} + 1  = 2^{32} + 1 &  = 4.294.967.297 = 641 \cdot
6.700.417 &  \mapsto {\rm ~NICHT~prim} !\\
f(6) = 2^{2^6} + 1  = 2^{64} + 1 &  = 18.446.744.073.709.551.617 \\
                                 &  = 274.177 \cdot 67.280.421.310.721  
																 & \mapsto {\rm ~NICHT~prim} ! \\
f(7) = 2^{2^7} + 1  = 2^{128} + 1 & = \mbox{(siehe Seite~\pageref{F7Morrison})}  
																 & \mapsto {\rm ~NICHT~prim} !
															
\end{array}
$$

    Innerhalb des Projektes ``Distributed Search for Fermat Number Dividers'',
    das von Leonid Durman angeboten wird, gibt es ebenfalls Fortschritte 
    beim Finden von neuen Primzahl-Riesen
    ({\href{http://www.fermatsearch.org/}
       {\tt http://www.fermatsearch.org/}}  --  diese Webseite hat 
    Verkn"upfungen zu Seiten in russisch, italienisch und deutsch).
    \begin{sloppypar}
    Die entdeckten Faktoren k"onnen sowohl zusammengesetzte nat"ur"-liche als
    auch prime nat"urliche Zahlen sein.
    \end{sloppypar}
     
    Am 22. Februar 2003 entdeckte John Cosgrave
    \begin{itemize} 
     \item die gr"o"ste bis dahin bekannte zusammengesetzte Fermatzahl und
     \item die gr"o"ste bis dahin bekannte prime nicht-einfache Mersennezahl
           mit 645.817 Dezimalstellen.
    \end{itemize}


    Die Fermatzahl
    $$ f(2.145.351) = 2^{(2^{2.145.351})} + 1 $$ 
    ist teilbar durch die Primzahl
    $$ p = 3*2^{2.145.353} + 1 $$ \\
    Diese Primzahl p war damals die gr"o"ste bis dahin bekannte prime 
    verallgemeinerte Mersennezahl\index{Mersenne!Mersennezahl!verallgemeinerte}
    und die 5.-gr"o"ste damals bekannte Primzahl "uberhaupt. 

    Zu diesem Erfolg trugen bei: NewPGen von Paul Jobling's, PRP von 
    George Woltman's, Proth von Yves Gallot's Programm\index{Gallot, Yves} und
    die Proth-Gallot-Gruppe am St. Patrick's College, Dublin.

    Weitere Details finden sich unter
    \vspace{-10pt}
    \begin{itemize}
      \item[] \href{http://www.fermatsearch.org/history/cosgrave_record.htm/}
          {\texttt{http://www.fermatsearch.org/history/cosgrave\_record.htm/}}
    \end{itemize}


%    ({\href{http://perso.wanadoo.fr/yves.gallot/primes/index.html}
%           {\tt http://perso.wanadoo.fr/yves.gallot/primes/index.html}}).
% M.E. ist die Zahl auf seiner Webseite zu gro"s, da M-39 "nur" 4 Mio. Stellen hat !
%    Heute kennt man alle Fermatschen Primzahlen mit bis zu 2.000.000.000 ???
%    Dezimalstellen. \\




% --------------------------------------------------------------------------
\vskip +10 pt
\subsubsection
    [Verallgemeinerte Fermatzahlen $f(b,n) = b^{2^n} + 1$]
    {Verallgemeinerte Fermatzahlen\footnotemark~$f(b,n) = b^{2^n} + 1$}
    \footnotetext{%
      Hier ist die Basis b nicht notwendigerweise 2 . \\
      Noch allgemeiner w"are:  $f(b,c,n) = b^{c^n} \pm 1$
    }
\hypertarget{generalizedFermatprimes}{}    %be_2005 Eigentlich sind es "Zahlen", nicht nur "Primes" !
\label{generalized-fermat}
\index{Fermat!Fermatzahl!verallgemeinerte}
    Verallgemeinerte Fermatzahlen kommen h"aufiger vor als Mersennezahlen
    gleicher Gr"o"se, so dass wahrscheinlich noch viele gefunden werden 
    k"onnen, die die gro"sen L"ucken zwischen den Mersenne-Primzahlen 
    verkleinern.
    Fortschritte in der Zahlentheorie haben es erm"og"-licht, dass Zahlen,
    deren Repr"asentation nicht auf eine Basis von 2 beschr"ankt ist, 
    nun mit fast der gleichen Geschwindigkeit wie Mersennezahlen getestet
    werden k"onnen.
    
    Yves Gallot\index{Gallot, Yves} schrieb das Programm Proth.exe zur 
    Untersuchung verallgemeinerter Fermatzahlen.
    
    Mit diesem Programm fand Michael Angel am 16. Februar 2003 eine
    prime verallgemeinerte Fermatzahl mit 628.808 Dezimalstellen, 
    die zum damaligen Zeitpunkt zur 5.-gr"o"sten bis dahin bekannten
    Primzahl wurde:
    $$ b^{2^{17}} + 1  =  62.722^{131.072} + 1. $$ 

    Weitere Details finden sich unter
    \vspace{-10pt}
    \begin{itemize}
      \item[] \href{http://primes.utm.edu/top20/page.php?id=12}
              {\texttt{http://primes.utm.edu/top20/page.php?id=12}} 
    \end{itemize}




% --------------------------------------------------------------------------
\vskip +10 pt
\subsubsection{Carmichaelzahlen\index{Zahlen!Carmichaelzahl}}
Wie \hyperlink{HT-Carmichael-number01}{oben} in
Kapitel~\ref{L-Carmichael-number01} erw"ahnt,
sind nicht alle Carmichaelzahlen prim.


% --------------------------------------------------------------------------
\vskip +10 pt
\subsubsection{Pseudoprimzahlen%
\index{Primzahl!Pseudoprimzahl}\index{Zahlen!Pseudoprimzahl}%
}
Siehe \hyperlink{HT-Pseudoprimenumber01}{oben} in
Kapitel~\ref{L-Pseudoprimenumber01}.


% --------------------------------------------------------------------------
\vskip +10 pt
\subsubsection{Starke Pseudoprimzahlen%
\index{Primzahl!starke Pseudoprimzahlen} \index{Zahlen!starke Pseudoprimzahl}%
}
Siehe \hyperlink{HT-Strongpseudoprimenumber01}{oben} in
Kapitel~\ref{L-Strongpseudoprimenumber01}.



% --------------------------------------------------------------------------
\vskip +10 pt
\subsubsection
    [Idee aufgrund von Euklids Beweis $p_1 \cdot p_2 \cdots p_n +1$]
    {Idee aufgrund von Euklids Beweis $p_1 \cdot p_2 \cdots p_n +1$}
Diese Idee entstammt \hyperlink{thm-pz-euklid}{Euklids Beweis}, dass es
unendlich viele Primzahlen gibt.
$$
\begin{array}{lll}
2{\cdot}3 +1 &      = 7 &          \mapsto {\rm ~prim} \\
2{\cdot}3{\cdot}5 +1 &      = 31    &      \mapsto {\rm ~prim} \\
2{\cdot}3{\cdot}5{\cdot}7 +1 &      = 211   &      \mapsto {\rm ~prim} \\
2{\cdot}3{\cdots}11 +1 &        = 2311  &      \mapsto {\rm ~prim} \\
2\cdot3 \cdots 13 +1 &  = 59 \cdot 509 &    \mapsto {\rm ~NICHT~prim} ! \\
2\cdot3 \cdots 17 +1 &  = 19 \cdot 97 \cdot 277 &   \mapsto {\rm ~NICHT~prim} ! \\
\end{array} 
$$


% --------------------------------------------------------------------------
\vskip +10 pt
\subsubsection{Wie zuvor, nur $-1$ statt $+1$: $p_1 \cdot p_2 \cdots p_n -1$}
$$
 \begin{array}{lll}
2\cdot 3 -1     &   = 5 &   \mapsto {\rm ~prim} \\
2\cdot 3 \cdot  5  -1   &   = 29 &  \mapsto {\rm ~prim} \\
2\cdot 3 \cdots 7  -1   &   = 11 \cdot 19 & \mapsto {\rm ~NICHT~prim} ! \\
2\cdot 3 \cdots 11 -1   &   = 2309 &    \mapsto {\rm ~prim} \\
2\cdot 3 \cdots 13 -1  &    = 30029 &   \mapsto {\rm ~prim} \\
2\cdot 3 \cdots 17 -1    &  = 61 \cdot 8369 &   \mapsto {\rm ~NICHT~prim!}
\end{array}
$$


% --------------------------------------------------------------------------
\vskip +10 pt
\subsubsection[Euklidzahlen $e_n = e_0 \cdot e_1 \cdots e_{n-1} + 1$]
              {Euklidzahlen $e_n = e_0 \cdot e_1 \cdots e_{n-1} + 1$  
	       mit $ n \geq 1 $ und $ e_0 := 1 $}
%	       mit $n$ gr"o"ser oder gleich $1$ und $e_0 := 1$}
    \index{Euklidzahlen}
    $e_{n-1}$ ist nicht die $(n-1)$-te Primzahl, sondern die zuvor hier 
    gefundene Zahl.
    Diese Formel ist leider nicht offen, sondern rekursiv.
    Die Folge startet mit
$$
\begin{array}{lll}
e_1 = 1 + 1 &   = 2 &   \mapsto {\rm ~prim} \\
e_2 = e_1 + 1   &   = 3 &   \mapsto {\rm ~prim} \\
e_3 = e_1 \cdot e_2 + 1 &   = 7 &   \mapsto {\rm ~prim} \\
e_4 = e_1 \cdot e_2 \cdot e_3 + 1 & = 43 &  \mapsto {\rm ~prim} \\
e_5 = e_1 \cdot e_2 \cdots e_4 + 1 &    = 13 \cdot 139 &    \mapsto {\rm ~NICHT~prim} ! \\
e_6 = e_1 \cdot e_2 \cdots e_5 + 1 &    = 3.263.443 &   \mapsto {\rm ~prim} \\
e_7 = e_1 \cdot e_2 \cdots e_6 + 1 &    = 547 \cdot 607 \cdot 1.033 \cdot 31.051 & \mapsto {\rm ~NICHT~prim} ! \\
e_8 = e_1 \cdot e_2 \cdots e_7 + 1 &    = 29.881\cdot 67.003 \cdot 9.119.521 \cdot 6.212.157.481 & \mapsto {\rm ~NICHT~prim} !
\end{array}
$$

Auch $e_9, \cdots, e_{17}$ sind zusammengesetzt, so dass dies auch
keine brauchbare Primzahlformel ist.

Bemerkung: Das Besondere an diesen Zahlen ist, dass sie jeweils paarweise
keinen gemeinsamen Teiler au"ser $1$ haben\footnote{%
Dies kann leicht mit Hilfe der {\em gr"o"ste gemeinsame Teiler} ($ggT$)-Rechenregel $ggT(a,b) = ggT(b-\lfloor b/a\rfloor,a)$ (siehe Seite \pageref{Appendix_A}) 
gezeigt werden: Es gilt f"ur $i<j$: \\
$ggT(e_i,e_j) \le ggT(e_1 \cdots e_i \cdots e_{j-1}, e_j) = ggT(e_j - e_1 \cdots e_i \cdots e_{j-1}, e_1 \cdots e_i \cdots e_{j-1}) 
= ggT(1, e_1 \cdots e_i \cdots e_{j-1}) = 1$.
}, sie sind also%
\index{Primzahl!relative}\index{relativ prim} {\em relativ zueinander prim}.


% --------------------------------------------------------------------------
% \pagebreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% be_24.503 raus in D
% f(40) hier und f(80) im folgenden Kapitel nach Hinweis von Erik Berger korr. (2005-05)
\vskip +10 pt
\subsubsection{$f(n) = n^2 + n + 41$}
\label{L-Polynomfunktion01-41}
   Diese Folge hat einen sehr {\em erfolgversprechenden} Anfang,
   aber das ist noch lange kein Beweis.
$$
\begin{array}{lll}