0 Daumen
419 Aufrufe

Aufgabe:

Schnelle Exponentiation: Berechnen Sie mithilfe des RSA Algorithmus (schnell große Potenzen modulo m berechnen)
folgendes Beispiel: \( 5^{29} \) modulo 11 .


Problem/Ansatz:

Also der erste Schritt ist es den Exponenten in Binärdarstellung umzuwandeln -> 0001 1101

Wie würde man jetzt zur Lösung kommen?

Avatar von

Man könnte für die Handberechnung zuerst Euler-Fermat nutzen:

5^29 = 5^9 mod (11)

Da φ(11)=10 und somit

5^10 = 1 mod (11)

Was die Berechnung mit dem RSA Verfahren zu tun hat ist für mich unklar. Für das RSA Verfahren muss man zwar schnell Potenzen berechnen können, aber RSA ist ja ein Verschlüsselungsverfahren und kein Exponentiations Algorithmus ...

Siehe dafür eher:

https://de.m.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation

https://en.m.wikipedia.org/wiki/Addition-chain_exponentiation

https://en.m.wikipedia.org/wiki/Modular_exponentiation

1 Antwort

0 Daumen
 
Beste Antwort

5

5^2 = 25 = 3 mod 11

3^2 = 9 mod 11

9^2 = 81 = 4 mod 4

4^2 = 16 = 5 mod 11

5 * 9 * 4 * 5 = 900 = 9 mod 11

Avatar von 477 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community