Die Eulersche-$\phi$-Funktion

Die Eulersche-$\phi$-Funktion macht eine Aussage darüber, wie viele teilerfremde Zahlen zu einer Zahl $n$ im Intervall $[ 1; n - 1 ]$ existieren. Die Zahl $1$ wird dabei immer als teilerfremde Zahl gezählt. Ist $n$ eine Primzahl, so macht man sich leicht klar, dass $\phi (n) = n - 1$ gelten muss.

Ist $n$ das Produkt zweier Primzahlen $p$ und $q$, so gilt $\phi (n) = \phi(pq) = (p - 1) (q - 1)$. Das heisst, die Berechnung der Eulerschen-$\phi$-Funktion ist für das Produkt zweier Primzahlen genau dann trivial, wenn beide Faktoren bekannt sind.

Eine weitere für die Kryptographie wichtige Aussage der $\phi$-Funktion ist, dass folgender Zusammenhang gilt, wenn $\phi (n)$ und $e$ teilerfremd sind:

$$p^e \equiv p^{e \bmod \phi (n)} \pmod{n}$$ (1)

Ein Beweis dieses Zusammenhangs ist leider im Rahmen dieser Facharbeit nicht möglich. Interessierte seien auf [5] verwiesen.