modulo rechnung

Neue Frage »

blondblau-bn Auf diesen Beitrag antworten »
modulo rechnung
Meine Frage:
Hallo, ich bitte bei Antwort um Berücksichtigung: Ich bin Abiturientin, also habe ich leider noch keine Ahnung von der Hochschulmathematik (Und habe bisher nur das "Rechnen mit Zahlen" gelernt). Ich sitze gerade an einer Aufgabe, die ich versucht habe mit viel Mühe zu lösen (die ich freiweillig mache, vom Abitur bis zum Studium im Oktober hat man viel Zeit und aus Interesse)...

Ursprünglich war die Aufgabe, eine Nachricht gemäß dem RSA-Algorithmus zu verschlüsseln...
Bei einem Schritt komme ich nicht weiter:
c=17^65537 mod 120

Ich bringe mir vieles durch das Internet bei, aber die Modulorechnung kriege ich einfach nicht hin =( und jetzt auch noch bei der großen Zahl...
Sry wegen der Laberei, liebe Grüße

Meine Ideen:
fortsetzendes Quadrieren...?Und dann????
Cugu Auf diesen Beitrag antworten »

Da völlig unklar ist, wann die ersten Zahlentheoretiker hier vorbei schauen, will ich mal ein bisschen mitüberlegen. Tanzen

Nach dem Chinesischen Restsatz dürfte es wegen genügen
,
,

zu kennen.

Außerdem gilt .

-----

Anstatt kann man genauso gut ausrechnen.
Außerdem ist für .
Folglich ist .

usw.
mYthos Auf diesen Beitrag antworten »

Nicht fortgesetztes Quadrieren, sondern fortgesetztes Potenzieren wird weiterhelfen.
Dies macht man so lange, bis - nach mehr oder weniger Schritten - wieder derselbe Rest auftaucht. Daraus kann man dann einen Zyklus bestimmen.

mod(17^1; 120) = 17
mod(17^2; 120) = mod(289; 120) = 49
mod(17^3; 120) = mod(49*17; 120) = 113
mod(17^4; 120) = mod(113*17; 120) = 1
mod(17^5; 120) = mod(1*17; 120) = 17

Glück gehabt, der Zyklus ist recht kurz.
Jetzt musst du eigentlich nur noch schauen, wie oft dieser in 65537 hineingeht (wobei dieser Wert gar nicht interessiert) und was dann noch übrig bleibt (das ist wichtig) ...

mY+

@Cugu
Zahlentheoretiker bin ich nicht.
Mein Weg ist zwar nicht so pragmatisch wie deiner, aber er müsste ebenfalls funktionieren.
Cugu Auf diesen Beitrag antworten »

Ich mache ich Grunde genau dasselbe, nur dass ich vorher in teilerfremde Faktoren aufspalte. Da selbst ziemlich klein ist, war das aber nicht besonders effektiv.
blondblau-bn Auf diesen Beitrag antworten »

Danke für die schnellen Antworten smile
Nur jetzt habe ich noch ein Problem, habe zur Modulorechnung bisher im Internet gelesen, also wie sie funktioniert, am einfachen Beispiel:
12 =(kongruent?) 26 mod 7
da 12=1*7+5 und 26=7*3+5
Ist für mich alles neu und lerne viel anhand von Beispielen.... Ich glaube, bin mir nicht sicher, ob ich alles richtig verstanden habe...
Aber wie schreibe ich das jetzt auf?
Und meinst du, ich muss jetzt rausbekommen 65537=120*546+17?
LG
mYthos Auf diesen Beitrag antworten »

Dein einfaches Beispiel ist korrekt, 12 ist kongruent 26 mod 7, weil beide bei der Division durch 7 den Rest 5 hinterlassen.
_________________

Zu deiner Aufgabe: Den Exponenten 65537 zu zerlegen, bringt nichts, beinahe hätte ich auch diesen Fehlschluss begangen, das stimmt hier mit 17 nur zufällig.

Hast du gesehen, dass der Zyklus einfach 4 beträgt, d.h. beim 5. Mal wieder 17 als Ergebnis erscheint? Somit bleibt bei der Division von 65537 durch 4 als Rest 1. Somit bleibt noch ein Faktor 17 übrig. Was ist nun das Resultat dieser Modulo-Rechnung?

mY+
 
 
blondblau-bn Auf diesen Beitrag antworten »

Hmm... den 4er-Zyklus habe ich bemerkt, aber ich kann grad nicht weiter denken. Reicht das dann, bei Schritt 4 mit dem Rest 1 aufzuhören?
mYthos Auf diesen Beitrag antworten »

Na ja, schon. Also enden wir bei 65536 (xxx36 ist durch 4 teilbar!) ebenfalls mit dem Rest 1. Was kommt also noch nachher?

mY+
blondblau-bn Auf diesen Beitrag antworten »

hab gerade gemerkt: ich glaube, dass ich bei der gesammten Aufgabe ein Fehler gemacht habe an der stelle: e*d ist kongruent 1 mod phi(n)
da ich ja e in c=x^e mod n einsetzen muss
Komme dann morgen nochmal auf die Stelle hier zurück und mache weiter, werde jetzt unterbrechen und schlafen gehen... sry, ich krieg auch nicht mehr viel hin, bin ziemlich müde und
danke für die Hilfe!!=D
Manus Auf diesen Beitrag antworten »

Zitat:
Original von Cugu

Außerdem gilt .



Am schnellsten wäre es vermutlich ein bisschen die Theorie anzuwerfen und diese Aussage von Cugu zu verwenden, dann muss man nämlich eigentlich nicht mehr rechnen.
Cugu Auf diesen Beitrag antworten »

Naja
blondblau-bn Auf diesen Beitrag antworten »

Ah okay danke =) jetzt weiss ich bescheid ! Hatte doch keinen Fehler gemacht, dachte mein e wäre falsch aber konnte man doch wählen, also richtig und jetzt klappts, hat mir echt hier weitergeholen und macht spaß sich damit mit euch auseinanderzusetzen! Liebe Grüße
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »