\newcommand{\ggT}{\operatorname{ggT}}

\begin{slide}{Etwas Zahlentheoretie}

\begin{itemize}
\item
  Beobachtung: wenn $n=p \cdot q$ 
  für \emph{große} (z. b. $\approx 10^{100}$) Primzahlen $p,q$,
  dann kann man $p,q$ aus  $n$  allein praktisch nicht bestimmen.
\item
  (Kleiner) Satz von Fermat/Euler: für $\ggT(x,n)=1$ gilt
  gilt $x^{\phi(n)} \equiv 1 \bmod n$.

  wobei $\phi(n)= |F(n)|$
  mit $F(n)= \{ y \mid 0 < y < n, \ggT(y,n)=1 \} $ 

  (alle Zahlen in $\{1, 2, n-1\}$, die zu $n$ teilerfremd sind)
\item
  Folgerung: wenn $a \equiv 1 \bmod \phi(n)$,
  dann $x^a \equiv x \pmod n$. (Entschlüsselung)
\item
  man kann $\phi(n)$ aber nur bestimmen,
  wenn man $p, q$ kennt:  $\phi(n)=\phi(p) \phi(q)=(p-1)(q-1)$.
\end{itemize}

\end{slide}


