Binäre modulo-Exponentiation

[mikyboy]

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]

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

[BlackJack]

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]

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

... wenn man keine ahnung hat, einfach mal die fresse halten

[mikyboy]

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?

[Rebecca]

Also bei mir braucht das keine merkbare Rechenzeit, ebensowenig das erste Beispiel.

[mikyboy]

Sorry stimmt, mein Fehler lag ganz wo anders!

Danke trotzdem!

[BlackJack]

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.