Schnelle Exponentiation RSA Algorithmus

Question

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?

Comments

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

Answer 1

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