\begin{slide}{Primzahlgenerierung/-Test}

Für RSA werden große Primzahlen $p,q$ benötigt.
Wo kommen die her? Würfeln und testen!

eine Primzahl hat keine nichttrivialen Faktoren.

Faktoren einer großen Zahl anzugeben ist schwer.

Feststellen, \emph{ob} sie nichttriviale Faktoren hat,
ist verhältnismäßig viel einfacher.


z. B. nach Satz von Fermat/Euler:
wenn $x^{n-1} \not\equiv 1 \bmod n$,
dann ist $n$ \emph{nicht} prim. ---
Um Primalität zu \emph{beweisen}, braucht man aber mehr
als nur \emph{ein} $x^{n-1} \equiv 1 \bmod n$.

Es gibt dafür schnelle probabilistische Verfahren
(und seit ca. 2 Jahren sogar ein relativ schnelles, exaktes,
siehe Primes is in P:
\url{http://www.cse.iitk.ac.in/news/primality.html})


\end{slide}
