Modulo, große Potenzen, große Basis, großes n, RSA |
16.12.2010, 19:14 | Suppi | Auf diesen Beitrag antworten » | ||
Modulo, große Potenzen, große Basis, großes n, RSA 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 ??? |
||||
16.12.2010, 19:17 | lgrizu | Auf diesen Beitrag antworten » | ||
RE: Modulo, große Potenzen, große Basis, großes n, RSA
Wieso zwei zweistellige Zahlen? Nutze: |
||||
16.12.2010, 19:36 | 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 ? |
||||
16.12.2010, 19:39 | 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. |
||||
16.12.2010, 19:41 | 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? |
||||
16.12.2010, 19:46 | 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 ??? |
||||
Anzeige | ||||
|
||||
16.12.2010, 20:04 | 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. |
||||
16.12.2010, 20:35 | Suppi | Auf diesen Beitrag antworten » | ||
Ich versteh nicht ganz warum Das leuchtet mir noch nicht ein..... Genauso wenig wie Rene das gemacht hat ! |
||||
16.12.2010, 20:37 | 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 |
||||
16.12.2010, 21:05 | 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 ? |
||||
16.12.2010, 21:08 | lgrizu | Auf diesen Beitrag antworten » | ||
Im Laufe dieser Rechnung zweistellige Zahlen zu multiplizieren lässt sich nicht vermeiden, aber was ist daran so schlimm? |
||||
16.12.2010, 21:13 | 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 ;-) |
||||
16.12.2010, 21:27 | 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. |
||||
16.12.2010, 21:34 | 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 . 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. |
||||
16.12.2010, 21:34 | 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 |
||||
16.12.2010, 21:38 | René Gruber | Auf diesen Beitrag antworten » | ||
Nein, das ist noch ein weiterer Weg - ich bin halt etwas sprunghaft. |
||||
16.12.2010, 21:47 | Suppi | Auf diesen Beitrag antworten » | ||
Wenn ich eh mit so großen Zahlen multiplizieren muss, kann ich ja auch : da |
||||
16.12.2010, 21:54 | Suppi | Auf diesen Beitrag antworten » | ||
Wie kamst du denn auf |
||||
16.12.2010, 21:55 | René Gruber | Auf diesen Beitrag antworten » | ||
Gründlich lesen:
|
||||
16.12.2010, 22:01 | Suppi | Auf diesen Beitrag antworten » | ||
Ich hab keine Ahnung wieso man euler so anwenden kann ! |
||||
16.12.2010, 22:04 | René Gruber | Auf diesen Beitrag antworten » | ||
Da muss ich mich aber sehr wundern, denn deinem Eröffnungsposting nach
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. |
||||
16.12.2010, 22:09 | 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 ??? |
||||
16.12.2010, 22:12 | René Gruber | Auf diesen Beitrag antworten » | ||
Es ist , also auch , oder was meinst du? |
||||
16.12.2010, 22:16 | Suppi | Auf diesen Beitrag antworten » | ||
Genau, wie kommt man da auf die 47 ? Also hinten das mod 47 |
||||
16.12.2010, 22:23 | 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. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|