\documentclass[dvips]{foils}
\usepackage{amsmath,amssymb}
\parindent0em
\begin{document}
\rotatefoilhead{Zertifikate f\"ur Primzahlen (\textsc{Pratt})}

Der (kleine) Satz von {\sc Fermat}:
\[
n ~ \mbox{Primzahl} ~ ~~\Rightarrow~~~ \forall x\,
(\,\hbox{ggT} (x,n) = 1
~\Rightarrow~ x ^{n-1} \equiv 1 ~ \pmod{n}\,) 
\]
Daher:\\
F\"ur {\em zusammengesetzten} Zahlen $n$ gibt es sehr einfache Beweise f\"ur
diese Eigenschaft: jeder {\sc Fermat}-Zeuge $b$, also jede Zahl $b$
mit
\[
\hbox{ggT}(b,n) \not= 1 ~\wedge~ b^{n-1} 
\not\equiv 1 ~ \pmod{n}
\]
ist Zeuge f\"ur die Zusammengesetztheit von $n$, und dies ist leicht zu
{\em \"uberpr\"ufen}. \\
NB: \textsc{Miller-Rabin}-Zeugen f\"ur die Zusammengesetztheit sind h\"aufig!

\rotatefoilhead{}

Was ist mit dem komplement\"aren Problem : 
\begin{quote}
Gibt es leicht zu \"uberpr\"ufende Zeugen f\"ur die {\em Primheit} einer
Primzahl? 
\end{quote}

Die Umkehrung des Satzes von {\sc Fermat} ist
nicht korrekt ({\sc Carmichael}-Zahlen !), 
und w\"urde wegen der $\forall$-Quantifizierung 
kaum eine vern\"unftige Basis f\"ur eine effiziente \"Uberpr\"ufung
sein.

NB: \"Uberpr\"ufung der Primheit durch Probedivision ist hoffnungslos.

Dass man dennoch die Primheit einer Primzahl effizient \"uberpr\"ufen kann,
zeigt ein Verfahren von {\sc V. Pratt} (1975)
\footnote{
``Every prime has a succinct certificate'',
SIAM Journal on Computing, 4 (1975), 214-220.}, das auf einer versch\"arften
Version des Satzes von {\sc Fermat} beruht.

\rotatefoilhead{}

\[
n ~ \text{Primzahl} 
~~\Longleftrightarrow~~ \exists x \in U_n :
\text{ord}_n \, x = n-1
\]

Dabei ist $U_n$ die {\em Einheitengruppe modulo} $n$,\\
$U_n = \{\,x\,;\, 1 \leq x < n, \text{ggT}(x,n) = 1 \,\}$

$\text{ord}_n \, x = \min\{\,e \geq 1\,;\,x^e \equiv 1 \pmod{n}\,\}$

Die Richtung ``$\Leftarrow$'' ist klar, da die Existenz eines Elements
mit Ordnung $n-1$ in $U_n$ zur Folge hat, dass $\# U_n = n-1$ ist, und dies gilt nur f\"ur Primzahlen.

Die Richtung ``$\Rightarrow$'' besagt, dass es zu jeder Primzahl ein
{\em primitives Element} gibt. Das ist nicht ganz trivial.

\rotatefoilhead{}

Um eine Zahl $n$ als Primzahl zu erkennen, gen\"ugt es, ein Element $x$ mit
$\text{ord}_n x = n-1$ vorzuweisen. Die Eigenschaft ``$\text{ord}_n x = n-1$'' besagt:
\[
x^{n-1} \equiv 1 ~ \pmod{n} ~~~\wedge~~~ 
x^t \not\equiv 1 ~ \pmod{n} ~ \text{f\"ur} ~ 1 \leq t < n-1
\]
aber tats\"achlich ist dies \"aquivalent zu
\[
x^{n-1} \equiv 1 ~ \pmod{n} ~~~\wedge~~~ 
x^d \not\equiv 1 ~ \pmod{n} ~ \text{f\"ur} ~
d\,|\,n-1, d\not= n-1
\]

\rotatefoilhead{}

Auch dies l\"asst sich noch weiter reduzieren und f\"uhrt zu der Aussage:

{\em Satz} :
Eine nat\"urliche Zahl $n>1$ ist genau dann eine Primzahl, wenn es eine
ganze Zahl $x$ gibt mit:
\begin{itemize}
\item
$x^{n-1} \equiv 1 ~ \text{mod} ~ n$
\item
$x^{(n-1)/p} \not\equiv 1 ~ \text{mod} ~ n$ f\"ur jeden Primteiler
$p$ von $n-1$
\end{itemize}

\rotatefoilhead{}

Der Nachweis der Primheit einer Primzahl $n$ kann also mit Hilfe von ``Zeugen''
oder ``Zertifikaten'' folgendermassen gef\"uhrt werden:

ein Zertifikat $C(n)$ f\"ur die Primheit von $n$ besteht aus 
\begin{itemize}
\item
der Angabe einer Faktorisierung
$
n - 1 = p_1^{\alpha_1} \cdot p_2^{\alpha_2}
\cdot \ldots \cdot
p_r^{\alpha_r}
$\\
wobei die $p_i$ ganze Zahlen $\geq 2$ und die $\alpha_i$ ganze Zahlen
$\geq 1$ sind
\item
dem Nachweis, dass die Zahlen $p_1, \ldots, p_r$ {\em Primzahlen} sind,
durch Angabe von Zertifikaten $C(p_i)$ f\"ur die $p_i > 2$
\item
der Angabe einer positiven Zahl $x < n$ mit
\[
x^{n-1} \equiv 1 ~ \pmod{n}
~~\text{und}~~
x^{(n-1)/p_i} \not\equiv 1 ~ \pmod{n} ~(1 \leq i \leq r)
\]
 \end{itemize}

\rotatefoilhead{}

Eine leichte Induktion zeigt: zur \"Uberpr\"ufung eines Zertifikats
$C(n)$ ben\"otigt man maximal $4 \log_2 n$ \"Uberpr\"ufungen von
Produkten und von Exponentiationen modulo $m$ (wobei $m \leq n$).

Da alle Operationen zur \"Uberpr\"ufung von $C(n)$ auf $\log_2 n$-bit-Zahlen
ausgef\"uhrt werden, hat man tats\"achlich einen Rechenaufwand, der 
{\em polynomial} in $\log n$, der input-Gr\"osse, ist:
\[
\framebox[8cm]{\textsc{Primes}$ ~\in ~ NP$}
\]

 
 
\end{document}