Euler Theorem
Der Satz von Euler verallgemeinert den kleinen fermatschen Satz: Gilt gcd(a,n)=1, so gilt a^φ(n)≡1 (mod n), wobei φ die eulersche Phi-Funktion ist.
Zweck
Die Vereinfachung modulärer Potenzen auf beliebige Moduli ausdehnen; Grundlage des Korrektheitsbeweises der RSA-Entschlüsselung.
Mechanismus
a^φ(n)≡1 (mod n) bedeutet, dass a^e mod n mit e mod φ(n) vereinfacht werden kann. RSA-Entschlüsselung: m^(ed)≡m^(ed mod φ(N))≡m^1≡m (mod N), denn ed≡1 mod φ(N).
Anwendungsfälle
- RSA-Korrektheitsbeweis
- Vereinfachung modularer Exponentiation
- Zahlentheorie