Binäre modulo-Exponentiation

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
mikyboy
User
Beiträge: 9
Registriert: Donnerstag 8. November 2007, 13:50

Montag 12. November 2007, 21:22

Wie kann man eine Binäre modulo-Exponentiation in Python durchführen?

z.B. damit er es nicht ewig dauert, um (123**121)%4482139 auszurechnen...
brauche es für eine RSA verschlüsselung, bei kleinen Zahlen funktionierts problemlos ohne die Binäre modulo-Exponentiation, bei grösseren Zahlen dauert es jedoch sehr lange...

Greez, mike
Jona
User
Beiträge: 94
Registriert: Sonntag 23. September 2007, 23:25

Montag 12. November 2007, 21:56

python selbst kann das nicht.
musst dir das also selbst schreiben.
es gibt aber ischer irgendeine bibliothek die das kann.
BlackJack

Montag 12. November 2007, 21:59

Doch Python selbst kann das:

Code: Alles auswählen

In [94]: pow(123, 121, 4482139)
Out[94]: 4194574L
Wobei das konkrete Beispiel auch mit "normaler" Rechnung nicht wahrnehmbar viel Zeit benötigt.
Jona
User
Beiträge: 94
Registriert: Sonntag 23. September 2007, 23:25

Montag 12. November 2007, 22:09

oh sorry, wusste nicht, dass pow() schnelle exponentation kann.

... wenn man keine ahnung hat, einfach mal die fresse halten :)
mikyboy
User
Beiträge: 9
Registriert: Donnerstag 8. November 2007, 13:50

Montag 12. November 2007, 22:16

hm bist du sicher dass pow() wirklich eine schnelle exponentation durchfürht? also zb bei dein zahlen pow(727438,813451,975449) geht das immernoch sehr lange, oder sind die Zahlen einfach allgemein zu gross? :D
Benutzeravatar
Rebecca
User
Beiträge: 1662
Registriert: Freitag 3. Februar 2006, 12:28
Wohnort: DN, Heimat: HB
Kontaktdaten:

Montag 12. November 2007, 22:18

Also bei mir braucht das keine merkbare Rechenzeit, ebensowenig das erste Beispiel.
Offizielles Python-Tutorial (Deutsche Version)

Urheberrecht, Datenschutz, Informationsfreiheit: Piratenpartei
mikyboy
User
Beiträge: 9
Registriert: Donnerstag 8. November 2007, 13:50

Montag 12. November 2007, 22:21

Sorry stimmt, mein Fehler lag ganz wo anders!

Danke trotzdem!
BlackJack

Dienstag 13. November 2007, 00:30

Problem bei Rechnungen mit grossen Zahlen ist oft nicht die Rechnung an sich, sondern das Ausgeben der Zahlen. Weil die Umrechnung von einer Zahl, die intern zur Basis 2 gespeichert ist, in eine Zeichenkettendarstellung zur Basis 10, leider nicht besonders effizient bewerkstelligt werden kann.
Antworten