Funktion optimieren (Miller-Rabin-Primzahltest)
Verfasst: Samstag 4. November 2006, 13:29
Ich bin grad dabei den MIller-Rabin-Primzahltest in Python zu implementieren und dabei muss ich berechnen.
Allerdings werden die Werte ziemlich groß.
Bsp: n= 123456789 (zu prüfende Zahl)
a - zufällige Zahl zw. 2 und n
u = n-1
Ihr seht also, dass das Ganze ziemlich rechenintensiv ist.
Dadurch spare ich wenigstens einige Minuten, das dauert aber immernoch sehr lange.
Code: Alles auswählen
(a**u)%nAllerdings werden die Werte ziemlich groß.
Bsp: n= 123456789 (zu prüfende Zahl)
a - zufällige Zahl zw. 2 und n
u = n-1
Ihr seht also, dass das Ganze ziemlich rechenintensiv ist.
Code: Alles auswählen
"""
Schnellerer Weg fuer:
(a**u)%n
"""
def modular_exp(a,u,n):
tmp=a
for i in xrange(u-1):
tmp = (tmp*a)%n
return tmp