Modulo, große Potenzen, große Basis, großes n, RSA

Neue Frage »

Suppi Auf diesen Beitrag antworten »
Modulo, große Potenzen, große Basis, großes n, RSA
Meine Frage:
Wir haben bei der Entschlüsselung (public key -> (n, e) = (94, 3))
schließlich 45^31 mod 94 zu lösen.
Allerdings dürfen wir keinen Taschenrechner benutzen. Fermat und Euler scheinen nichts zu bringen, da keine Prim und phi(94)=46 und damit größer als 31 ist.
Gibts da nicht einen Trick wie man das ohne große Zahlen zu multiplizieren hinbekommt ?

Meine Ideen:
Man könnte ja ((((45²)*45)²*45)²*45)²*45 und jeweils mit dem Rest ersetzen. Lustig nur, dass man gleich zu Beginn schon zwei zweistelliggen Zahlen multipliziert. Da is einem doch nicht geholfen.

Wie bekommt man das denn ohne Rechner hin ???
lgrizu Auf diesen Beitrag antworten »
RE: Modulo, große Potenzen, große Basis, großes n, RSA
Zitat:
Original von Suppi
Man könnte ja ((((45²)*45)²*45)²*45)²*45 und jeweils mit dem Rest ersetzen. Lustig nur, dass man gleich zu Beginn schon zwei zweistelliggen Zahlen multipliziert. Da is einem doch nicht geholfen.


Wieso zwei zweistellige Zahlen?

Nutze:
Suppi Auf diesen Beitrag antworten »

Dann bin ich bei 45 mod 94, was ja wieder 45 ist und direkt wieder bei

45*45 mod 94


Was sehe ich denn nicht, was du siehst ?
René Gruber Auf diesen Beitrag antworten »

Optional kannst du auch erstmal ausrechnen, das Ergebnis lässt sich unter der Zusatzinfo "ungerade" dann leicht auf hochrechnen.
lgrizu Auf diesen Beitrag antworten »

Zerlege 45 in Primfaktoren, diese lassen sich zumeist einfach Potenzieren, also 45=5*3*3.

Nun berechnest du die Potenzen der Primfaktoren modulo 94, so sieht man leicht, dass ist, siehst du, welche Idee dahinter steckt?
Suppi Auf diesen Beitrag antworten »

Okay, ich könnte also

31^10 * 5 machen, dann hab ich aber wie so ne große Zahl !?!


Oder ?


@ rene

Wie hast du denn das gemacht ???
 
 
lgrizu Auf diesen Beitrag antworten »

Rene hat das zuerst auf ein Problem modulo 47 reduziert (also 94/2) und dann den betragskleinsten Repräsentanten der Restklasse modulo 47 genommen.

Bei meiner Variante zerlegen wir weiter, wir haben

Nun wissen wir .

also

Fernerhin ist

und usw...

Das macht man dann auch mit den anderen Primzahlen und erhält (zugegebenermaßen relativ rechenaufwendig) eine Lösung.
Suppi Auf diesen Beitrag antworten »

Ich versteh nicht ganz warum



Das leuchtet mir noch nicht ein.....

Genauso wenig wie Rene das gemacht hat !
lgrizu Auf diesen Beitrag antworten »

ist auch Blödsinn, ich meinte , die einsen haben sich da so eingeschlichen, da haben meine Hände etwas anderes gemacht als mein Hirn wollte Augenzwinkern
Suppi Auf diesen Beitrag antworten »

Jetzt hab ich das mal einen Moment lang probiert...





usw
dann erhalte ich




was hab ich dadurch gewonnen ?
und ich muss ja dann doch zweistellige Zahlen multiplizieren, oder ?
lgrizu Auf diesen Beitrag antworten »

Im Laufe dieser Rechnung zweistellige Zahlen zu multiplizieren lässt sich nicht vermeiden, aber was ist daran so schlimm?
Suppi Auf diesen Beitrag antworten »

Ich finde es ist extrem aufwendig, da ich das für 8 verschlüsselte Zahlen machen muss, um mein Lösungswort zu bekommen.

also 45^31

für
45
40
88
9
58
69
51
79
45
3

Da brauch ich ja Stunden ;-)
lgrizu Auf diesen Beitrag antworten »

Dann solltest du Renes Lösung in Betracht ziehen, aber ein wenig rechnen ist auch da notwendig, und man sollte die 2er Potenzen kennen.
René Gruber Auf diesen Beitrag antworten »

Viele, sehr viele Wege führen nach Rom. Ein weiterer, schon ziemlich exotischer wäre der:

,

unter Nutzung von sowie . Big Laugh


Entweder man sieht sowas und rechnet weniger, oder man sieht es nicht und rechnet mehr. Egal, man kommt so oder so zum Ziel, jedenfalls wenn man nicht soviel rummosert. Augenzwinkern
Suppi Auf diesen Beitrag antworten »

Die würde mich mal interessieren....bzw was und wie genau er das gemacht hat !


Edith says:

Ha, da hatters schon gemacht !


THXALOT
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von Suppi
Ha, da hatters schon gemacht !

Nein, das ist noch ein weiterer Weg - ich bin halt etwas sprunghaft. Teufel
Suppi Auf diesen Beitrag antworten »

Wenn ich eh mit so großen Zahlen multiplizieren muss, kann ich ja auch :








da

Suppi Auf diesen Beitrag antworten »

Wie kamst du denn auf

René Gruber Auf diesen Beitrag antworten »

Gründlich lesen:

Zitat:
Original von René Gruber
unter Nutzung von [...] .
Suppi Auf diesen Beitrag antworten »

Ich hab keine Ahnung wieso man euler so anwenden kann !
René Gruber Auf diesen Beitrag antworten »

Da muss ich mich aber sehr wundern, denn deinem Eröffnungsposting nach

Zitat:
Original von Suppi
Fermat und Euler scheinen nichts zu bringen, da keine Prim und phi(94)=46 und damit größer als 31 ist.

dachte ich, dass dir folgendes geläufig ist:

Für teilerfremde gilt nach Euler und folglich dann

.

Nichts anderes habe ich hier für angewandt.
Suppi Auf diesen Beitrag antworten »

der erste denkansatz ist mir geläufig, den zweiten hab ich nicht weitergedacht. Aber ich habs jetzt verstanden und finds extrem gut zu wissen...


Nochmals vielen Dank


Kannst du mir noch erklären, was du in deinem erstn Post gemacht hast ???
René Gruber Auf diesen Beitrag antworten »

Es ist , also auch

,

oder was meinst du? verwirrt
Suppi Auf diesen Beitrag antworten »

Genau, wie kommt man da auf die 47 ?

Also hinten das mod 47
René Gruber Auf diesen Beitrag antworten »

Das hat doch lgrizu schon gesagt:

Wenn man den Rest modulo 94 ermitteln will, dann kann man einzeln den Rest modulo 2 ermitteln (ist hier einfach 1 wegen Ungeradheit) sowie modulo 47 ermitteln und dann zusammenführen. Letzteres geschieht mit chinesischem Restsatz, was hier aber großspuriger klingt als es am Ende ist: Ist der Rest modulo 47, dann ist die ungerade der beiden Zahlen sowie dann der gesuchte Rest modulo 94.
Neue Frage »
Antworten »



Verwandte Themen

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