Der Satz von Euler

Der Satz von Euler stellt eine Verallgemeinerung des „kleinen Satzes von Fermat“ auf beliebige Moduli $n \in \mathbb{N}$ dar.

Der Satz von Euler besagt folgendes:

Falls der $ggT(a,n)=1 \Longrightarrow a^{\varphi(n)} \equiv 1 \ mod \ n$

Beweis:
Es gilt: $ggT(a,n)=1$ ( $a,n$ sind teilerfremd).
1) man nehme zu $n$ teilerfremde Zahlen aus $\mathbb{Z}_n$ : $k_1,\ k_2, \ \cdot\cdot\cdot,\ k_{\varphi(n)}$
2) man multipliziere $k_1,\ \cdot\cdot\cdot, \ k_m$ mit $a$ und erhält: $ak_1, \ ak_2, \ \cdot\cdot\cdot, \ ak_{\varphi(n)} \Longrightarrow ggT(ak_i,n)=1$

Einschub Beispiel:
$n=9: \varphi(9)=6 \Longrightarrow 1,\ 2,\ 4, \ 5, \ 7, \ 8$
für $a=2$ (da 2 teilerfremd zu $n$ )

$\\ 2 \cdot 1 \ mod \ 9=\textbf{2}, \\ \ 2 \cdot 2 \ mod \ 9=\textbf{4},\\ \ 2 \cdot 4 \ mod \ 9=\textbf{8}, \\ \ 2 \cdot 5 \ mod \ 9=\textbf{1}, \\ \ 2 \cdot 7 \ mod \ 9=\textbf{5}, \\ \ 2 \cdot 8 \ mod \ 9=\textbf{7} \Longrightarrow es \ entsteht \ eine \ Permutation.$

Beweis (Fortsetzung):
3) Bilden des Produktes aller $k_i$ und aller $ak_i$ $\Longrightarrow k_1 \cdot k_2 \cdot k_3 \cdot\cdot\cdot k_{\varphi(n)} \equiv ak_1 \cdot ak_2 \cdot ak_3 \cdot\cdot\cdot ak_{\varphi(n)} \ mod \ n$
4) Nun kann abschließend durch $k_i$ geteilt werden, da alle $k_i$ teilerfremd zu $n$ sind.
$\Longrightarrow 1 \equiv a^{\varphi(n)} \ mod \ n \quad (q.e.d)$

Der Satz von Euler dient der Reduktion großer Exponenten $modulo \ n$ . Praktische Anwendung findet er u.a. in der Kryptographie beispielsweise beim RSA-Verschlüsselungsverfahren.

IT-Sicherheit

IT- und Systemsicherheit

Schreibe einen Kommentar Antwort abbrechen