\documentstyle[12pt,A4,german]{article}
\begin{document}
\begin{center}
\Large
{Zertifikate f"ur Primzahlen}
\end{center}
Die Aussage des Satzes von {\sc Fermat}:
\[
n ~ \mbox{Primzahl} ~ ~~\Rightarrow~~~ \forall x
(\hbox{ggT} (x,n) = 1
~\Rightarrow~ x ^{n-1} \equiv 1 ~ \mbox{mod} ~ n) 
\]
erlaubt es, bei {\em zusammengesetzten} Zahlen $n$ sehr einfache Beweise f"ur
diese Eigenschaft anzugeben: jeder {\sc Fermat}-Zeuge $b$, also jede Zahl $b$
mit
\[
\hbox{ggT}(b,n) \not= 1 ~\wedge~ b^{n-1} 
\not\equiv 1 ~ \mbox{mod} ~ n
\]
ist Zeuge f"ur die Zusammengesetztheit von $n$, und dies ist leicht zu
{\em "uberpr"ufen}.\footnote{
Nat"urlich ist bereits jeder Teiler einer 
zusammengesetzten Zahl ein einfach zu "uberpr"ufender Zeuge f"ur diese
Tatsache.} 
(Ob es leicht ist, solche Zeugen zu {\em finden}, ist eine
andere Frage. Der {\sc Miller-Rabin}-Test jedenfalls zeigt, da"s die entsprechenden Zeugen f"ur die Zusammengesetztheit jedenfalls sehr h"aufig sind,
so da"s eine Zufallssuche bei zusammengesetztem $n$ mit extrem gro"ser 
Wahrscheinlichkeit sehr schnell einen {\sc Miller-Rabin}-Zeugen zu Tage
f"ordern wird).

Keineswegs klar ist, ob eine solche Feststellung auch f"ur das komplement"are
Problem gilt: 
\begin{quote}
gibt es leicht zu "uberpr"ufende Zeugen f"ur die Primheit einer
Primzahl? 
\end{quote}
Abgesehen davon, da"s die Umkehrung des Satzes von {\sc Fermat}
nicht korrekt ist ({\sc Carmichael}-Zahlen), w"urde sie auch wegen der All-
Quantifizierung kaum eine vern"unftige Basis f"ur eine effiziente "Uberpr"ufung
sein.\footnote{
Noch ineffizienter w"are die Aufgabe, die Nicht-Existenz von Zeugen
f"ur die Teilbarkeit nachzuweisen. Man mache anhand einer
Absch"atzung des Rechenaufwandes klar!} 
Da"s 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.

Zun"achst zeigen wir:
\[
n ~ \mbox{Primzahl} 
~~\Longleftrightarrow~~ \exists x \in U_n :
\hbox{ord}_n x = n-1
\]
Dabei ist die Richtung ``$\Leftarrow$'' klar, da die Existenz eines Elements
mit Ordnung $n-1$ in $U_n$ zur Folge hat, da"s $\# U_n = n-1$ ist, und dies gilt
nur f"ur Primzahlen.

Umgekehrt ist nun eine schon fr"uher zitierte Tatsache zu beweisen, da"s die 
Einheitengruppe $U_n$ zyklisch ist, falls $n$ Primzahl ist.

Definieren wir, in Analogie zu der Situation bei den komplexen Einheitswurzeln
f"ur Teiler $d$ von $n$:
\begin{eqnarray*}
{\cal R}_d(n)
& :=
& \{ x \in U_n ; \hbox{ord}_n (x) ~|~ d \} \\
{\cal P}_d(n)
& :=
& \{ x \in U_n ; \hbox{ord}_n (x) = d \}
\end{eqnarray*}
so lautet die zu beweisende Behauptung:
\[
n ~ \mbox{Primzahl} ~~~ \Rightarrow~~~
 {\cal P}_{n-1} (n) \not= \emptyset
\]
Wir werden (weiter in Analogie zur Situation bei den komplexen Einheitswurzeln)
zeigen:
\[
n ~ \mbox{Primzahl} ~~,~~ d | n-1 ~~~\Rightarrow~~~
 \# {\cal P}_d (n) = \phi (d)
\]
was die gew"unschte Aussage impliziert.

Sei nun also $n$ eine Primzahl $(> 2)$ und $n-1 = d \cdot e$ eine Zerlegung.
Die Tatsache, da"s ${\bf Z}_n$ ein K"orper ist, hat verschiedene Konsequenzen:

\begin{itemize}
\item
$\# {\cal R}_{n-1}(n) = \# U_n = n-1~$ ({\sc Fermat}!)
\item
$\#{\cal R}_d(n) \leq d$, denn alle Elemente von ${\cal R}_d(n)$ sind
Nullstellen des Polynoms $X^d - 1$
\item
unter der Abbildung $x \mapsto x^e$ hat jedes Element $y$ von ${\cal R}_d(n)$
h"ochstens $e$ Urbilder
in ${\cal R}_{n-1}(n)$, die Nullstellen des Polynoms $X^e-y$ n"amlich 
\end{itemize}
aus denen sich
\[
d \cdot e = n - 1 = \#U_n =
\#{\cal R}_{n-1}(n) \leq
\# {\cal R}_d(n) \cdot e \leq
d \cdot e
\]
ergibt, und somit
\[
\#{\cal R}_d (n) = d ~ \mbox{f"ur jeden Teiler } ~ d ~ \mbox{von} ~ n-1 .
\]
Die Behauptung
\[
\# {\cal P}_d (n) = \phi (d) ~ \mbox{f"ur jeden Teiler} ~ d ~ \mbox{von} ~ n-1 
\]
ergibt sich nun per Induktion. F"ur $d = 1$ ist die Aussage trivial. Sei dann 
$d > 1$ ein Teiler von $n-1$. Da ${\cal R}_d(n)$ die disjunkte Vereinigung der 
Mengen ${\cal P}_f(n)$ mit $f | d$ ist, gilt
\[
d = \# {\cal R}_d (n) =
\sum\limits_{f|d} \#{\cal P}_f(n) \; .
\] 
Nun kann
\[
\# {\cal P}_f(n) = \phi (f)~~~ 
\hbox{f"ur {\em echte} Teiler $f$ von $d$ und $f = 1$}
\] 
als bereits bewiesen gelten.
Daher:
\begin{eqnarray*}
d 
&=& 
\# {\cal P}_d(n) + \sum\limits_{f|d, f\not= d} 
\# {\cal P}_f(n) \\
\\
&=&
\# {\cal P}_d(n) + \sum\limits_{f|d, f\not= d} \phi (f)
\end{eqnarray*}
und wegen
\[
d = \sum\limits_{f | d} \phi(f)
\]
hat das die Behauptung zur Folge.

Um eine Zahl $n$ als Primzahl zu erkennen, gen"ugt es, ein Element $x$ mit
$\hbox{ord}_n x = n-1$ vorzuweisen. Die Eigenschaft ``$\hbox{ord}_n x = n-1$'' besagt:
\[
x^{n-1} \equiv 1 ~ \mbox{mod} ~ n ~~~,~~~ 
x^t \not\equiv 1 ~ \mbox{mod} ~ n ~ \mbox{f"ur} ~ 1 \leq t < n-1
\]
aber tats"achlich (und gl"ucklicherweise f"ur unsere Absichten!) ist dies 
"aquivalent zu
\[
x^{n-1} \equiv 1 ~ \mbox{mod} ~ n ~~~,~~~ 
x^d \not\equiv 1 ~ \mbox{mod} ~ n ~ \mbox{f"ur} ~
d\,|\,n-1, d\not= n-1
\]
\newpage
Aber auch dies l"a"st sich noch weiter reduzieren und f"uhrt zu der Aussage:
\newline

{\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 ~ \mbox{mod} ~ n$
\item
$x^{(n-1)/p} \not\equiv 1 ~ \mbox{mod} ~ n$ f"ur jeden Primteiler
$p$ von $n-1$
\end{itemize}

Der Nachweis der Primheit einer Primzahl $n$ kann also mit Hilfe von ``Zeugen''
oder ``Zertifikaten'' folgenderma"sen 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, da"s 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$ mit
\begin{itemize}
\item
$x^{n-1} \equiv 1 ~ \mbox{mod} ~ n$

\item
$x^{(n-1)/p_i} \not\equiv 1 ~ \mbox{mod} ~ n ~ \mbox{f"ur} ~ 1 \leq i \leq r$
\end{itemize}
\end{itemize}

Nun zur {\em Aufwandsabsch"atzung} f"ur das 
"Uberpr"ufen eines Zertifikats $C(n)$: \\
sei $T(n)$ die Anzahl der Verifikationen von Produkten
\[
m \stackrel{?}{=} q_1^{\beta_1} q_2^{\beta_2} \cdot \ldots
\]
und der mod-$q$-Berechnungen

\[
x \stackrel{?}{\equiv} 1 ~ \mbox{mod} ~ q
\]
die f"ur das "Uberpr"ufen von $C(n)$ ben"otigt werden. Dann gilt

\[
T(n) = 1 +
\sum\limits^r_{i=2}
T(p_i) + r + 1
\]
falls $n = p_1^{\alpha_1} \cdot \ldots \cdot p_r^{\alpha_r}$.
Dabei ist $p_1 = 2$, und $2$ ist ``kostenlos''. Mit

\begin{eqnarray*}
S(n)
&:=& 
1 + T(n) \qquad \qquad \mbox{gilt also} \\
\\
S(n)
&=&
\sum\limits^r_{i=2} S(p_i) + 4
\end{eqnarray*}
und hierf"ur kann man per Induktion verifizieren:

\[
S(n) \leq 4 \cdot \log_2 n
\]
f"ur alle Primzahlen von $n$. F"ur $n = 2$ ist nichts zu zeigen.
F"ur Primzahlen $n > 2$ mit
\[
n - 1 \;=\; p_1^{\alpha_1} p_2^{\alpha_2} 
\ldots p_r^{\alpha_r}  \quad (p_1 = 2)
\]
gilt dann:
\begin{eqnarray*}
S(n)
&\leq&
\sum\limits^r_{i=2}(4 \cdot \log_2 p_i) + 4 \\
\\
&=&
4 \cdot \sum\limits^r_{i=1} \log_2 p_i \\
\\
&=&
4 \cdot \log \prod\limits^r_{i=1} p_i \\
\\
&\leq&
4 \cdot \log n
\end{eqnarray*}

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

Im Vorgriff auf Sp"ateres sei bereits erw"ahnt: mit NP 
(f"ur {\em nondeterministic polynomial time})\footnote{
diese Bezeichnung spielt auf ein spezielles nicht-deterministisches
Berechnungsmodell an, das man aber auch in ein (deterministisches)
Verifikationsmodell "ubersetzen kann.}
bezeichnet man die Klasse aller Probleme, f"ur die es effiziente
{\em Verifikationsverfahren} gibt, d.h. zu jeder positiven Instanz
eines solchen Entscheidungsproblems (also z.B zu jeder Primzahl,
wenn die Frage der Primheit von nat"urlichen Zahlen zu entscheiden ist)
gibt es Zusatzinformation (``Zeugen'', ``Zertifikate''), mit deren Hilfe
das Vorhandensein der Eigenschaft (``prim'' zu sein) effizient
nachgewiesen werden kann. (``Effizient'' = polynomiale Laufzeit in
der input-Gr"o"se). Dabei ist es irrelevant, ob das Herbeibringen solcher
Zeugen oder Konstruieren solcher Zertifikate selbst mit polynomialem
Aufwand m"oglich ist. Allein die Verifikation z"ahlt!

Probleme, bei denen man die Zugeh"origkeit zu den positiven oder
negativen Instanzen eines Entscheidungsproblemes effizient testen kann
(ohne Zusatzinformation), z"ahlt man zu der Problemklasse P 
(f"ur `{\em polynomial time}) der
{\em polynomialen Entscheidungsprobleme}. Es ist klar, da"s 
\[
P \subseteq NP
\]
gilt. Das Problem, ob hierbei ``$=$'' oder ``$\neq$'' gilt, ist eine
zentrale Frage der Komplexit"atstheorie. Es geht also darum:
\begin{quote}
Besitzt jedes Problem, zu dem es ein effizientes 
{\em Verifikationsverfahren} gibt, auch ein effizientes
{\em Entscheidungsverfahren} ?
\end{quote}
Eine Konseqenz einer positiven Antwort w"are, da"s wenn es zu einem
Problem leicht verwertbare Zeugen oder Zertifikate
gibt (f"ur das Erf"ulltsein einer
Eigenschaft), es dann auch leicht verwertbare Zeugen f"ur das 
Nicht-Erf"ulltsein eben dieser Eigenschaft geben m"usste ---
man spiele diesen Gedanken am Beispiel der Zeugen f"ur Zusammengesetztheit
und Zertifikate f"ur Primheit durch.

\vskip1cm
Hier zun"achst ein kleines Beispiel f"ur die {\sc Pratt}sche Verifikationsmethode, ein etwas umfangreicheres folgt dann:

\begin{itemize}
\item
$79$ ist Primzahl, denn es gilt 
\begin{itemize}
\item
$79-1 = 78 = 2 \cdot 3\cdot 13$ 
\item
$2,3$ und $13$ sind Primzahlen
\item
$3^{78} \equiv 1 ~,~3^{78/2} \equiv 78~,~3^{78/3} \equiv 23~,~
3^{78/13} \equiv 18 ~~\hbox{mod}~79$
\end{itemize}
d.h. $C(79) = [~2\cdot 3 \cdot 13~;~C(3),C(13)~;~3~]$ ist ein
Prim-Zertifikat f"ur $79$.
\item
$13$ ist eine Primzahl, denn es gilt
\begin{itemize}
\item
$13-1 = 12 = 2^2 \cdot 3$
\item
2 und 3 sind Primzahlen
\item
$2^{12} \equiv 1~,~2^6 \equiv 12 ~,~2^4 \equiv 3~~\hbox{mod}~13$
\end{itemize}
d.h. $C(13) = [~2^2 \cdot 3~;~C(3)~;~2~]$  ist ein
Prim-Zertifikat f"ur $13$.
\item
$3$ ist Primzahl, denn es gilt
\begin{itemize}
\item
$3-1 = 2 = 2$
\item
2 ist Primzahl
\item
$2^2 \equiv 1 ~,~2^1 \equiv 2~~\hbox{mod} 3$
\end{itemize}
d.h. $C(3) = [~2~;~-~;~2~]$ ist ein
Prim-Zertifikat f"ur $3$.
\end{itemize}

\vskip0.4cm

{\em Beispiel}:

Bei dem Versuch, die Zahl  
\[
2^{214} + 1 = (2^{107} - 2^{54} + 1) \cdot (2^{107} + 2^{54} + 1)
\]
zu faktorisieren, findet man
\[
2^{107} - 2^{54} + 1 = 5 \cdot 857 \cdot M ~ ,
\]
wobei $M$ eine 29-stellige Zahl ist:
\[
M = 37866809061660057264219253397
\]
die keine ``kleinen'' Primfaktoren enth"alt.
{\sc Fermat}-Tests, wie z.B.
\[
3^{M-1} \equiv 1 ~ \mbox{mod} ~ M
\]
suggerieren, da"s $M$ Primzahl ist. 
Der {\em Beweis}, da"s dies tats"achlich
gilt, enth"alt folgenden Teilbeweis:

\begin{itemize}
\item
$N = 1653701519$ ist Primzahl, denn:
\[
N-1 = 2 \cdot 7 \cdot 19 \cdot 23 \cdot 137 \cdot 1973
~~,~~7^{N-1} \equiv 1 ~\hbox{mod}~N~\hbox{und}
\]
\[
\begin{array}{@{\Diamond~~~}r@{\hbox{~ist Primzahl und~}}l@{~\equiv~}l}
2 & 7^{(N-1)/2} & 1653701518 ~ \mbox{mod} ~ N \\
7 & 7^{(N-1)/7} & 356579618 ~ \mbox{mod} ~ N \\
19 & 7^{(N-1)/19} & 120777631  ~ \mbox{mod} ~ N \\
23 & 7^{(N-1)/23} & 1080868740 ~ \mbox{mod} ~ N \\
137 & 7^{(N-1)/137} & 101758286 ~ \mbox{mod} ~ N \\
1973 & 7^{(N-1)/1973} & 1287679432 ~ \mbox{mod} ~ N
\end{array}
\]
\item
$1973$ ist Primzahl, denn:
\[
1972 = 2 \cdot 2 \cdot 17 \cdot 29 , 3^{1972} \equiv 1  ~ \mbox{mod} ~ 1973
~\hbox{und}
\]
\[
\begin{array}{@{\Diamond~~~}r@{\hbox{~ist Primzahl und~}}l@{~\equiv~}l}
2 & 3^{1972/2} & 1972  ~ \mbox{mod} ~ 1973 \\
17 & 3^{1972/17} & 273  ~ \mbox{mod} ~ 1973 \\
29 & 3^{1972/29} & 934  ~ \mbox{mod} ~ 1973
\end{array}
\]
\item
$137$ ist Primzahl, denn:
\[
136 = 2 \cdot 2 \cdot 2 \cdot 17 ~,~ 3^{136} \equiv 1  ~ \mbox{mod} ~ 137
~~\hbox{ und}
\]
\[
\begin{array}{@{\Diamond~~~}r@{\hbox{~ist Primzahl und~}}l@{~\equiv~}l}
2 & 3^{136/2} & 136  ~ \mbox{mod} ~ 137 \\
17 & 3^{136/17} & 122  ~ \mbox{mod} ~ 13
\end{array}
\]
\item
$29$ ist Primzahl, denn:
\[
28 = 2 \cdot 2 \cdot 7 ~,~ 2^{28} \equiv 1  ~ \mbox{mod} ~ 29 ~\hbox{und}
\]
\[
\begin{array}{@{\Diamond~~~}r@{\hbox{~ist Primzahl und~}}l@{~\equiv~}l}
2 & 2^{28/2} & 28  ~ \mbox{mod} ~ 29 \\
7 & 2^{28/7} & 16  ~ \mbox{mod} ~ 29
\end{array}
\]
\item
$23$ ist Primzahl, denn: 
\[
22 = 2 \cdot 11 ~,~ 5^{22} \equiv 1  ~ \mbox{mod} ~ 22 ~\hbox{und}
\]
\[
\begin{array}{@{\Diamond~~~}r@{\hbox{~ist Primzahl und~}}l@{~\equiv~}l}
2 & 5^{22/2} & 22  ~ \mbox{mod} ~ 23 \\
11 & 5^{22/11} &  2  ~ \mbox{mod} ~ 23
\end{array}
\]
\item
$19$ ist Primzahl, denn: 
\[
18 = 2 \cdot 3 \cdot 3 ~,~ 2^{18} \equiv 1  ~ \mbox{mod} ~ 19 ~\hbox{und}
\]
\[
\begin{array}{@{\Diamond~~~}r@{\hbox{~ist Primzahl und~}}l@{~\equiv~}l}
2 & 2^{18/2} & 18  ~ \mbox{mod} ~ 19 \\
3 & 2^{18/3} & 7  ~ \mbox{mod} ~ 19
\end{array}
\]
\item
$17$ ist Primzahl, denn: 
\[
16 = 2 \cdot 2 \cdot 2 \cdot 2 ~,~ 3^{16} \equiv 1  ~ \mbox{mod} ~ 17 
~\hbox{und}
\]
\[
\begin{array}{@{\Diamond~~~}r@{\hbox{~ist Primzahl und~}}l@{~\equiv~}l}
2 & 3^{16/2} & 16  ~ \mbox{mod} ~ 17
\end{array}
\]
\item
$11$ ist Primzahl, denn: 
\[
10 = 2 \cdot 5~,~ 2^{10} \equiv 1  ~ \mbox{mod} ~ 11
~\hbox{und}
\]
\[
\begin{array}{@{\Diamond~~~}r@{\hbox{~ist Primzahl und~}}l@{~\equiv~}l}
2 & 2^{10/2} & 10  ~ \mbox{mod} ~ 11 \\
5 & 2^{10/5} & 4  ~ \mbox{mod} ~ 11
\end{array}
\]
\item
$7$ ist Primzahl, denn: 
\[
6 = 2 \cdot 3~,~ 3^6 \equiv 1  ~ \mbox{mod} ~ 7 ~
\hbox{und}
\]
\[
\begin{array}{@{\Diamond~~~}r@{\hbox{~ist Primzahl und~}}l@{~\equiv~}l}
2 & 3^{6/2} & 6  ~ \mbox{mod} ~ 7 \\
3 & 3^{6/3} & 3  ~ \mbox{mod} ~ 7
\end{array}
\]
\item
$5$ ist Primzahl, denn: 
\[
4 = 2 \cdot 2~,~ 2^4 \equiv 1 ~\hbox{mod}~5 ~ \hbox{und}
\]
\[
\begin{array}{@{\Diamond~~~}r@{\hbox{~ist Primzahl und~}}l@{~\equiv~}l}
2 & 2^{4/2} &  4  ~ \mbox{mod} ~ 5
\end{array}
\]
\item
$3$ ist Primzahl, denn:
\[
2 = 2 ~,~ 2^2 \equiv 1~\hbox{mod}~3~\hbox{und}
\]
\[
\begin{array}{@{\Diamond~~~}r@{\hbox{~ist Primzahl und~}}l@{~\equiv~}l}
2 & 2^{2/2} & 2  ~ \mbox{mod} ~ 3 
\end{array}
\]
\end{itemize}

Als ``Zertifikate'' geschrieben:
\begin{eqnarray*}
C(1653701519) &=&
[ ~2 \cdot 7 \cdot 19 \cdot 23 \cdot 137 \cdot 1973 ~;~
C(7), C(19), C(23), C(137), C(1973) ~;~7 ~] \\[0.25cm]
C(1973) &=&
[~2^2 \cdot 17 \cdot 29 ~;~
C(17),C(29)~;~3~] \\[0.25cm]
C(137) &=&
[~2^3 \cdot 17 ~;~C(17)~;~3 ~] \\[0.25cm]
C(29) &=&
[~2^2\cdot 7 ~;~ C(7)~;~2~] \\[0.25cm]
C(23) &=&
[~2 \cdot 11 ~;~C(11)~;~5~] \\[0.25cm]
C(19) &=&
[~2 \cdot 3^2 ~;~C(3)~;~2~] \\[0.25cm]
C(17) &=&
[~2^4 ~;~-~;~3~] \\[0.25cm]
C(11) &=&
[~2 \cdot 5~;~C(5)~;~2~] \\[0.25cm]
C(7) &=&
[~2 \cdot 3 ~;~C(3)~;~3~] \\[0.25cm]
C(5) &=&
[~2^2 ~;~-~;~2~] \\[0.25cm]
C(3) &=&
[~2~;~-~;~2~]
\end{eqnarray*}

\newpage

{\em Nachwort}: Um allf"alligen Mi"sverst\"andnissen
ein f"ur allemal vorzubeugen: Zertifikate sind
zum {\em verifizieren} da, und es ist nur dieser Vorgang,
der f"ur die Komplexit"ats"uberlegungen relevant ist.
Die Frage, welchen Aufwand es kostet, die Zertifikate
zu {\em finden} oder zu {\em konstruieren}, ist 
eine ganz andere! Tats"achlich weiss man bis heute 
beispielsweise nicht hinreichend genau, wie gro"s f"ur 
eine beliebige Primzahl $p$ die kleinste Primitivwurzel
$g~\hbox{mod}~p$ ist, um daraus etwa einen effizienten
{\em deterministischen} Primzahltest zu gewinnen. Dies
r"uhrt an sehr tiefe Fragestellungen der Zahlentheorie.


Andererseits: man kennt heute deterministische Primzahltests,
die ``fast'' polynomial sind, deren Laufzeiten sich bei input $n$
wie ${\cal O}(\log(n)^{c \cdot\log \log \log n})$ verhalten 
({\sc Adleman, Pomerance, Rumely, Cohen, Lenstra}(1980/81).
Einen Primzahltest, der sich {\em im Mittel} polynomial verh"alt,
n"amlich ${\cal O}(\ln^6 n)$, haben {\sc Goldwasser, Kilian,
Atkin, Morain}(1986 und sp"ater) vorgeschlagen. 
Ein (theoretisch) effizienter probablistischer Primzahltest (im Gegensatz
zum {\sc Miller-Rabin}-Test und dem "ahnlich gearteten
{\sc Solovay-Strassen}-Test wird tats"achlich auf Primheit
und nicht auf Zusammengesetztheit getestet) stammt von {\sc Adleman} und
{\sc Huang}(1992). Die Tatsache, da"s sowohl Primheit wie auch Zusammengesetztheit probabilistisch effizient entschieden werden k"onnen,
spricht nach Expertenmeinung dagegen, da"s {\sc Primes} ein NP-vollst"andiges
Problem ist. Eher ist zu erwarten, da"s sich dieses Problem eines Tages
als zur polynomialen Klasse P zugeh"orig erweist.

Faktorisierung ist viel aufwendiger, und die Resultate sind nicht so
ermutigend. (Kommt auf den Standpunkt an: Krypto-Spezialisten werden
darauf vertrauen, da"s sich Faktorisierung als schwieriges Problem
herausstellt). Die besten bekannten Methoden haben ein Verhalten,
das mit Hilfe der Funktion $L(x) := e^{\sqrt{\ln x \ln \ln x}}$,
etwa in der Form einer kleinen Potenz ${\cal O}(L(n)^{1 + o(1)})$,
ausgedr"uckt wird. Es handelt sich dabei um probabilistische Verfahren.
F"ur strikt deteministische Verfahren, scheinen obere Schranken der Form 
$n^{1/4+o(1)}$ das Beste derzeit Bekannte darzustellen. All diese Methoden
beruhen auf tiefsinnigen Methoden der Zahlentheorie. Wer sich davon
einen Eindruck verschaffen will, auch von der Implementierung solcher
Methoden, findet beispielsweise in dem Buch 
{\em A course in computational algorithmic number theory} von
{\sc H, Cohen}, Springer-Verlag, 1993, eine Fundgrube.
\end{document}