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?
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
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
Ein anderes Problem?
Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos