Kann man diese Gleichung lösen?
Neue Frage »

18.02.2013, 18:29 tomRacket99 Auf diesen Beitrag antworten »
Kann man diese Gleichung lösen?
Meine Frage:
Hallo Mathe-Freaks!

p = 41
q = 11
e = 1039
n = p*q = 451

Phi(n) = (p - 1)*(q - 1) = 400

Wie berechne ich mit diesen Informationen d aus:

d * e mod Phi(n) = 1




Meine Ideen:
nach d auflösen schaffe ich nicht :

d * e mod Phi(n) = 1 || /d
e mod Phi(n)= 1 / d

...ich kann schließlich nicht 1 nach links bekommen...oder steh ich auf dem Schlauch?

Danke jetzt schon mal für die Hilfe Big Laugh
18.02.2013, 18:39 Bummbumm Auf diesen Beitrag antworten »
RE: Kann man diese Gleichung lösen?
Warum nimmst du nicht den Kehrwert?
18.02.2013, 18:43 Magnitude Auf diesen Beitrag antworten »

Euklidischer Algorithmus ist hier das Stichwort.
18.02.2013, 18:53 tomRacket99 Auf diesen Beitrag antworten »
Re
Und wie genau würdest du das berechnen? Kannst du mir sagen was d ist?

mit "euklidischer algorithmus" kann ich nichts anfangen -> das Hilft mir nicht weiter
18.02.2013, 18:57 Bummbumm Auf diesen Beitrag antworten »
RE: Re


edit von sulo: Rest gelöscht, Komplettlösungen sind unerwünscht.
18.02.2013, 21:21 Magnitude Auf diesen Beitrag antworten »

Zitat:
mit "euklidischer algorithmus" kann ich nichts anfangen -> das Hilft mir nicht weiter

ich ging auch davon aus, dass du dich mit diesem Stichwort schlau machst was das ist und dann zu eventuell noch vorhandenen Problemen konkrete Fragen stellst.

Wie genau man das Ganze aufbereiten sollte hängt sehr stark von deinen Vorkenntnissen ab bzw. davon wofür das Ganze sein soll. z.B. wie genau kennst du dich mit modulo-Rechnung aus?
 Anzeige 
 
18.02.2013, 22:47 Bummbumm Auf diesen Beitrag antworten »

Komplettlösung? Um Gottes Willen, ich darf nicht mal zeigen, wie man den Kehrwert bildet?

Stattdessen soll er sich mit dem euklidschen Algorithmus auseinander setzen? Der Hinweis ist doch total überzogen.

Aber bitte, ich bin dann halt raus!
18.02.2013, 23:09 Magnitude Auf diesen Beitrag antworten »

@Bummbumm:
Wie bildest Du denn modulo n den "Kehrwert" wenn nicht mit dem eukl. Algorithmus?
Der eukl. Algorithmus ist das beste mir bekannte Verfahren dafür.
19.02.2013, 00:00 Mystic Auf diesen Beitrag antworten »

Um in diesem Beispiel zu entschlüsseln, braucht man nur noch einmal zu verschlüsseln... Wie praktisch! Big Laugh
19.02.2013, 17:10 tomRacket99 Auf diesen Beitrag antworten »

noch mal eine kleine Frage: Wie ist die Priorität von modulo?

Punkt vor Strich lernt man in der Grundschule!

Gehört Modulo zur Punktrechnung(Multiplizieren und Dividieren) oder Strichrechnung(Addition und Subtraktion)?
Oder hat modulo eine höher Priorität als die Punktrechnung?
Oder sogar eine geringere als Strichrechnung?

PS: wenn ich mich richtig erinnere berechnet man mit dem Euklidischer Algorithmus den ggT(größter gemeinsamer Teiler)!?!?! Erstaunt2
19.02.2013, 17:18 Bummbumm Auf diesen Beitrag antworten »

Zitat:
Wie ist die Priorität von modulo?


Das kann man ja ausprobieren:

Google sagt: 2*3 mod 2 = 0
19.02.2013, 17:52 Mystic Auf diesen Beitrag antworten »

Was die Priorität von modulo betrifft, ist die Frage nicht so ganz leicht so beantworten... Im Prinzip wäre es ja eine Punktrechnung, da ja einfach der Rest bei einer Division berechnet wird, aber das heißt noch lange nicht, dass die übliche Regel "Punkt- vor Strichrechnung" hier anwendbar wäre... Z.B. liefert Maple im folgenden Beispiel zwei unterschiedliche Ergebnisse

code: 
1:
2:
3:
4:

5 mod 3+2;
                                4
2+5 mod 3;                      1

Mein Rat daher: Bei Verwendung eines CAS oder eines anderen Programms einfach ausprobieren...

Und ja, der Euklidische Algorithmus dient in seiner erweiterten Form (EEA) nicht nur dazu, denn ggT(a,b) zweier ganzer Zahlen a und b zu berechnen, sonderm man kann damit auch ganze Zahlen x und y finden, sodass ggT(a,b)=xa+yb gilt...
Neue Frage »
Antworten »



Verwandte Themen

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


MatheBoard » Schulmathematik » Sonstiges » Kann man diese Gleichung lösen?