primes.tex

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

f(0) = 41 & &  \mapsto {\rm ~prim} \\
f(1) = 43 & &  \mapsto {\rm ~prim} \\
f(2) = 47 & &  \mapsto {\rm ~prim} \\
f(3) = 53 & &  \mapsto {\rm ~prim} \\
f(4) = 61 & &  \mapsto {\rm ~prim} \\
f(5) = 71 & &  \mapsto {\rm ~prim} \\
f(6) = 83 & &  \mapsto {\rm ~prim} \\
f(7) = 97 & &  \mapsto {\rm ~prim} \\
\vdots \\
f(33) = 1.163 & & \mapsto {\rm ~prim} \\
f(34) = 1.231 & & \mapsto {\rm ~prim} \\
f(35) = 1.301 & & \mapsto {\rm ~prim} \\
f(36) = 1.373 & & \mapsto {\rm ~prim} \\
f(37) = 1.447 & & \mapsto {\rm ~prim} \\
f(38) = 1.523 & & \mapsto {\rm ~prim} \\
f(39) = 1.601 & & \mapsto {\rm ~prim} \\
f(40) = 1681 & = 41 \cdot 41 &  \mapsto {\rm ~NICHT~prim}! \\
f(41) = 1763 & = 41 \cdot 43 &   \mapsto {\rm ~NICHT~prim}! \\
\end{array}
$$
        Die ersten $40$ Werte sind Primzahlen (diese haben die auffallende
        Regelm"a"sigkeit, dass ihr Abstand beginnend mit dem Abstand $2$ 
        jeweils um $2$ w"achst), aber der $41$. und der $42$. Wert
        sind keine Primzahlen.
        Dass $f(41)$ keine Primzahl sein kann, l"asst sich leicht "uberlegen:
        $f(41) = 41^2 + 41 + 41 = 41 (41 + 1 + 1) = 41 \cdot 43$.



% --------------------------------------------------------------------------
% \pagebreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   be_2005
\vskip +10 pt
\subsubsection{$f(n) = n^2 - 79 \cdot n + 1.601$}
\label{L-Polynomfunktion02-1601}
   Diese Funktion liefert f"ur die Werte $n=0$ bis $n=79$ stets Primzahlwerte.
   Leider ergibt $f(80) = 1.681 = 11 \cdot 151$ keine Primzahl. Bis heute
   kennt man keine Funktion, die mehr aufeinanderfolgende Primzahlen annimmt.
   Andererseits kommt jede Primzahl doppelt vor (erst in der absteigenden,
   dann in der aufsteigenden Folge), so dass sie insgesamt genau 40 
   verschiedene Primzahlwerte liefert (dieselben wie die, die die Funktion
   aus Kapitel~\ref{L-Polynomfunktion01-41} liefert).
$$
\begin{array}{|ll||ll|}
\hline
f(0) = 1.601    & \mapsto {\rm ~prim} &  f(28) = 173    & \mapsto {\rm ~prim} \\
f(1) = 1.523    & \mapsto {\rm ~prim} &  f(29) = 151    & \mapsto {\rm ~prim} \\
f(2) = 1.447    & \mapsto {\rm ~prim} &  f(30) = 131 & \mapsto {\rm ~prim} \\
f(3) = 1.373    & \mapsto {\rm ~prim} &  f(31) = 113 & \mapsto {\rm ~prim} \\
f(4) = 1.301    & \mapsto {\rm ~prim} &  f(32) = 97 & \mapsto {\rm ~prim} \\
f(5) = 1.231    & \mapsto {\rm ~prim} &  f(33) = 83 & \mapsto {\rm ~prim} \\
f(6) = 1.163    & \mapsto {\rm ~prim} &  f(34) = 71 & \mapsto {\rm ~prim} \\
f(7) = 1.097    & \mapsto {\rm ~prim} &  f(35) = 61 & \mapsto {\rm ~prim} \\
f(8) = 1.033    & \mapsto {\rm ~prim} &  f(36) = 53 & \mapsto {\rm ~prim} \\
f(9) = 971  & \mapsto {\rm ~prim} &  f(37) = 47 & \mapsto {\rm ~prim} \\
f(10) = 911 & \mapsto {\rm ~prim} &  f(38) = 43 & \mapsto {\rm ~prim} \\
f(11) = 853 & \mapsto {\rm ~prim} &  f(39) = 41 & \mapsto {\rm ~prim} \\
f(12) = 797 & \mapsto {\rm ~prim} &  f(40) = 41 & \mapsto {\rm ~prim} \\                 
f(13) = 743 & \mapsto {\rm ~prim} &  f(41) = 43 & \mapsto {\rm ~prim} \\                 
f(14) = 691 & \mapsto {\rm ~prim} &  f(42) = 47 & \mapsto {\rm ~prim} \\                 
f(15) = 641 & \mapsto {\rm ~prim} &  f(43) = 53 & \mapsto {\rm ~prim} \\                 
f(16) = 593 & \mapsto {\rm ~prim} &  \cdots  &  \\                                       
f(17) = 547 & \mapsto {\rm ~prim} &  f(77) = 1.447  & \mapsto {\rm ~prim} \\             
f(18) = 503 & \mapsto {\rm ~prim} &  f(78) = 1.523  & \mapsto {\rm ~prim} \\             
f(19) = 461 & \mapsto {\rm ~prim} &  f(79) = 1.601  & \mapsto {\rm ~prim} \\             
f(20) = 421 & \mapsto {\rm ~prim} &  f(80) = 41 \cdot 41 & \mapsto {\rm ~NICHT~prim!} \\
f(21) = 383 & \mapsto {\rm ~prim} &  f(81) = 41 \cdot 43 & \mapsto {\rm ~NICHT~prim!} \\ 
f(22) = 347 & \mapsto {\rm ~prim} &  f(82) = 1.847  & \mapsto {\rm ~prim} \\             
f(21) = 383 & \mapsto {\rm ~prim} &  f(83) = 1.933  & \mapsto {\rm ~prim} \\             
f(22) = 347 & \mapsto {\rm ~prim} &  f(84) = 43 \cdot 47 &  \mapsto {\rm ~NICHT~prim!} \\
f(23) = 313 & \mapsto {\rm ~prim} & & \\ 
f(24) = 281 & \mapsto {\rm ~prim} & & \\
f(25) = 251 & \mapsto {\rm ~prim} & & \\
f(26) = 223 & \mapsto {\rm ~prim} & & \\
f(27) = 197 & \mapsto {\rm ~prim} & & \\
\hline
\end{array}
$$



% --------------------------------------------------------------------------
\vskip +10 pt
\subsubsection[Polynomfunktionen
    $f(x) = a_n x^n + a_{n-1}x^{n-1} + \cdots + a_1 x^1 + a_0$]
    {Polynomfunktionen
    $f(x) = a_n x^n + a_{n-1}x^{n-1} + \cdots + a_1 x^1 + a_0$  
    ($a_i$ aus ${\mathbb Z}$, $n \geq 1$)}\index{Polynom}
%\item Polynomfunktionen} $f(x) = a_n x^n + a_{n-1}x^{n-1} + 
%\cdots + a_1 x^1 + a_0$  ($a_i$ aus ${\mathbb Z}$, $n \geq 1$):

    Es existiert kein solches Polynom, das f"ur alle $x$ aus ${\mathbb Z}$ 
    ausschlie"slich Primzahlwerte annimmt.
    Zum Beweis sei auf \cite[S. 83 f.]{Padberg1996}, verwiesen, wo sich auch
    weitere Details zu Primzahlformeln finden.

    Damit ist es hoffnungslos, weiter nach Formeln (Funktionen) wie in
    Kapitel~\ref{L-Polynomfunktion01-41} oder 
    Kapitel~\ref{L-Polynomfunktion02-1601} zu suchen.

    

% --------------------------------------------------------------------------
\vskip +10 pt
\subsubsection[Vermutung von Catalan]{Vermutung von Catalan\footnotemark}
    \footnotetext{%
Eugene Charles Catalan, belgischer Mathematiker, 30.5.1814$-$14.2.1894.\\
Nach ihm sind auch die sogenannten {\em Catalanzahlen}
$A(n) = (1 / (n+1) ) * (2n)! / (n!)^2$ \\
$=  1, 2, 5, 14, 42, 132, 429, 1.430, 
4.862, 16.796, 58.786, 208.012, 742.900, 2.674.440, 9.694.845, ... $
benannt.
    }
Catalan\index{Catalan, Eugene}\index{Zahlen!Catalanzahl}
"au"serte die Vermutung, dass $ C_4 \;$ eine Primzahl ist:
$$
\begin{array}{l}
C_0 = 2, \\
C_1 = 2^{C_0} - 1,  \\
C_2 = 2^{C_1} - 1,  \\
C_3 = 2^{C_2} - 1, \\
C_4 = 2^{C_3} - 1, \cdots \\
\end{array}
$$
\begin{sloppypar}
    (siehe
        {\href{http://www.utm.edu/research/primes/mersenne.shtml}{\tt http://www.utm.edu/research/primes/mersenne.shtml}}
        unter Conjectures and Unsolved Problems).
\end{sloppypar}

    Diese Folge ist ebenfalls rekursiv definiert und w"achst sehr schnell. 
    Besteht sie nur aus Primzahlen?
$$
\begin{array}{lll}
C(0) = 2 & & \mapsto {\rm ~prim}\\
C(1) = 2^2 - 1 &    = 3 & \mapsto {\rm ~prim}\\
C(2) = 2^3 - 1 &    = 7 & \mapsto {\rm ~prim} \\
C(3) = 2^7 - 1 &    = 127& \mapsto {\rm ~prim} \\
C(4) = 2^{127} - 1 &      = 170. 141. 183. 460. 469. 231. 731. 687. 303. 715. 884. 105. 727 & \mapsto {\rm ~prim} \\
\end{array}
$$
Ob $C_5$ bzw.\ alle h"oheren Elemente prim sind, ist (noch) nicht bekannt,
aber auch nicht wahrscheinlich.
Bewiesen ist jedenfalls nicht, dass diese Formel nur Primzahlen liefert.




% --------------------------------------------------------------------------
\vskip +10 pt
\subsection{Dichte und Verteilung der Primzahlen}

Wie Euklid herausfand, gibt es unendlich viele Primzahlen. Einige unendliche Mengen sind aber
{\em dichter} \index{Primzahl!Dichte} als andere. Innerhalb der nat"urlichen Zahlen gibt es unendlich viele gerade, ungerade und
quadratische Zahlen.

Nach folgenden Gesichtspunkten gibt es mehr gerade Zahlen als quadratische:
\begin{itemize}
  \item die Gr"o"se des $n$-ten Elements: \\
    Das $n$-te Element der geraden Zahlen ist $2n$; das $n$-te Element der Quadratzahlen ist $n^2$. Weil f"ur
    alle $n>2$ gilt: $2n < n^2$, kommt die $n$-te gerade Zahl viel fr"uher als die $n$-te quadratische Zahl.
    Daher sind die geraden Zahlen dichter verteilt, und wir k"onnen sagen, es gibt mehr gerade als
    quadratische Zahlen.
  \item die Anzahl der Werte, die kleiner oder gleich einem bestimmten {\em Dachwert} $x$ aus ${\mathbb R}$ ist: \\
    Es gibt $[x/2]$ solcher gerader Zahlen und $[\sqrt{x}]$ Quadratzahlen. Da f"ur gro"se $x$ der
    Wert $x/2$ viel gr"o"ser ist als die Quadratwurzel aus $2$, k"onnen wir wiederum sagen, es gibt mehr
    gerade Zahlen.
\end{itemize}


\vskip +15 pt
\paragraph{Der Wert der $n$-ten Primzahl $P(n)$}%
\index{P(n)}%
\mbox{}
\vskip +10 pt
\begin{satz}\label{thm-pz-density}
F"ur gro"se $n$ gilt: Der Wert der $n$-ten Primzahl $P(n)$ ist
asymptotisch zu $n \cdot ln(n)$, d.h. der Grenzwert des
Verh"altnisses  $P(n)/(n\cdot \ln n)$ ist gleich $1$, wenn $n$
gegen unendlich geht.
\end{satz}

Es gilt f"ur $n \ge 5$, dass  $P(n)$  zwischen  $2n$  und  $n^2$  liegt.
Es gibt also weniger Primzahlen als gerade nat"urliche Zahlen, aber es gibt mehr Primzahlen als Quadratzahlen\footnote{%
Vergleiche auch \hyperlink{ntePrimzahl}{Tabelle \ref{s:ntePrimzahl}}.
}.


\vskip +15 pt
\paragraph{Die Anzahl der Primzahlen $PI(x)$}%
\index{PI(x)}%
\mbox{}
\vskip +10 pt
"Ahnlich wird die Anzahl der Primzahlen $PI(x)$ definiert, die den
Dachwert $x$ nicht "ubersteigen:

\begin{satz}\label{thm-pz-pi-x}
$PI(x)$  ist asymptotisch zu  $x / ln(x)$.
\end{satz}


Dies ist der \index{Primzahlsatz} \textbf{Primzahlsatz} (prime
number theorem). Er wurde von Legendre\footnote{%
  Adrien-Marie Legendre\index{Legendre, Adrien-Marie}, 
  franz"osischer Mathematiker, 18.9.1752$-$10.1.1833.
}
und Gauss\footnote{%
  Carl Friedrich Gauss\index{Gauss, Carl Friedrich}, 
  deutscher Mathematiker und Astronom, 30.4.1777$-$23.2.1855.
}
aufgestellt und erst "uber 100 Jahre sp"ater bewiesen.

\hyperlink{primhfk}{Die "Ubersicht unter \ref{s:primhfk} zeigt die
Anzahl von Primzahlen in verschiedenen Intervallen.}


Diese Formeln, die nur f"ur $n$ gegen unendlich gelten, k"onnen durch 
pr"azisere Formeln ersetzt werden.
F"ur $x \geq 67$ gilt:
$$ ln(x) - 1,5 < x / PI(x) < ln(x) - 0,5 $$
Im Bewusstsein, dass $PI(x)  =  x / \ln x$ nur f"ur sehr gro"se $x$ ($x$ gegen unendlich) gilt, kann man
folgende "Ubersicht erstellen:
$$
\begin{array}{ccccc}
x     &  ln(x)  &  x / ln(x) & PI(x)(gez"ahlt) &       PI(x) / (x/ln(x)) \\
10^3  &  6,908  &   144      &  168        &       1,160 \\
10^6  &  13,816 &   72.386    &  78.498          &       1,085 \\
10^9  & 20,723  &   48.254.942 &  50.847.534       &       1,054
\end{array}
$$

F"ur eine Bin"arzahl\footnote{%
Eine Zahl im Zweiersystem besteht nur aus den Ziffern 0 und 1.
} 
$ x $ der L"ange $250$ Bit 
($2^{250}$ ist ungef"ahr = $1,809 251 * 10^{75}$)  
gilt:
$$ PI(x) = 2^{250} / (250 \cdot \ln 2) \; \;  {\rm ist~ungef"ahr} 
\; = 2^{250} / 173,28677 = 1,045 810 \cdot 10^{73}. $$
Es ist also zu erwarten, dass sich innerhalb der Zahlen der
Bitl"ange kleiner als 250 ungef"ahr $10^{73}$ Primzahlen
befinden (ein beruhigendes Ergebnis?!).

Man kann das auch so formulieren: Betrachtet man eine {\em zuf"allige} nat"urliche Zahl $n$, so sind die
Chancen, dass diese Zahl prim ist, circa $1 / \ln(n)$. Nehmen wir zum Beispiel Zahlen in der Gegend von
$10^{16}$, so m"ussen wir ungef"ahr (durchschnittlich) $ 16 \cdot \ln 10 = 36,8 $
Zahlen betrachten, bis wir eine Primzahl finden.
Ein genaue Untersuchung zeigt: Zwischen $10^{16}-370$ und $10^{16}-1$ gibt es $10$
Primzahlen.

Unter der "Uberschrift {\em How Many Primes Are There} finden sich unter
\vspace{-10pt}
\begin{itemize}
  \item[] \href{http://www.utm.edu/research/primes/howmany.shtml}
               {\tt http://www.utm.edu/research/primes/howmany.shtml}
\end{itemize}
\vspace{-10pt}
viele weitere Details.

$PI(x)$ l"asst sich leicht per 
\vspace{-10pt}
\begin{itemize}
  \item[] \href{http://www.math.Princeton.EDU/~arbooker/nthprime.html}
               {\tt http://www.math.Princeton.EDU/\~{}arbooker/nthprime.html}
\end{itemize}
\vspace{-10pt}
bestimmen.


Die \textbf{Verteilung} der Primzahlen weist viele
Unregelm"a"sigkeiten auf, f"ur die bis heute kein