RSA- Verfahren: Modulo (mod) mit riiiiiiiiiiiiiesigen Potenzen?!
Hallo Leute,
ich möchte eine RSA- Verschlüsselung decodieren und weiß aber nicht, wie man das ausrechnen kann. Ein Standard- Taschenrechner, wie er in einer Prüfung erlaubt ist, versagt.
Als Beispiel:
126^427 (mod 697)=???
Es hängt nicht mit meinem Verständnis für die Sache selbst zusammen, bei einfacheren Aufgaben funktioniert es auch mit dem Taschenrechner, aber hier?
Was ich weiß, ist, dass das Ergebnis <697 ist :D
Wer hat Tipps?
Lieben Dank, Anita
2 Antworten
Hey Anita ich weiß nicht wie praktikabel es für dich sein muss, aber wenn du die den Kram am PC ausrechnen darfst/möchtest solltest du mal den GHCI Compiler ausprobieren. Dort werden die Größen der Zahlen die du verarbeiten kannst nur von deinem Arbeitsspeicher limitiert, so dass du diese Berechnungen ganz locker anstellen kannst. Ich hoffe mal, dass diese Antwort nicht viel zu spät kommt
Hallo Martin,
das ist wieder ein anderes Thema.
In dem Fall ging es um die Lösung mit einem Taschenrechner, wie ich in der Frage auch schrieb: "Ein Standard- Taschenrechner, wie er in einer Prüfung erlaubt ist, versagt."
Ansonsten kann ich mir das ja mal im Hinterkopf behalten.
LG Anita
Der Modulo macht ja praktisch folgendes: Ziehe so lange 697 ab, bis das Ergebnis kleiner 697 ist. Anders formuliert: Teile durch 697 und zeige mir den Rest. Oder auch: Teile durch 697 und vergiss den Teil vor dem Komma. Multipliziere dann den Teil hinter dem Komma mit 697. Daher denke ich, dass du auch 126 durch die 427. Wurzel von 697 teilen kannst und den Nachkommateil des Ergebnisses mit 697 multiplizieren musst, um auf die Endlösung zu kommen.
Übernehme aber keine Garantie für die Richtigkeit dieser Überlegung, war nur mein spontaner Gedanke. Probiers mal mit ein paar einfachen Zahlen, deren Ergebnis du mit TR noch überprüfen kannst, aus!
Hab selbst gemerkt, dass ich einen Denkfehler hatte: Man muss 126 durch die 427. Wurzel von 697 teilen, dann das Ergebnis hoch 427 rechnen und dann die Nachkommastellen betrachten. Hohe Zahlen kommen immer noch vor, dürften aber schon wesentlich kleiner sein.