Funktion optimieren (Miller-Rabin-Primzahltest)

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.
rico
User
Beiträge: 10
Registriert: Samstag 4. November 2006, 13:21
Kontaktdaten:

Funktion optimieren (Miller-Rabin-Primzahltest)

Beitragvon rico » Samstag 4. November 2006, 13:29

Ich bin grad dabei den MIller-Rabin-Primzahltest in Python zu implementieren und dabei muss ich

Code: Alles auswählen

(a**u)%n
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.

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

Dadurch spare ich wenigstens einige Minuten, das dauert aber immernoch sehr lange.
Benutzeravatar
SigMA
User
Beiträge: 181
Registriert: Sonntag 4. April 2004, 13:27
Wohnort: Freiburg
Kontaktdaten:

Beitragvon SigMA » Samstag 4. November 2006, 14:14

Leichtdio.de - Das Kreativ-Blog
http://www.leichtdio.de
BlackJack

Re: Funktion optimieren (Miller-Rabin-Primzahltest)

Beitragvon BlackJack » Samstag 4. November 2006, 15:26

rico hat geschrieben:Ich bin grad dabei den MIller-Rabin-Primzahltest in Python zu implementieren und dabei muss ich

Code: Alles auswählen

(a**u)%n
berechnen.


Schau Dir mal die `pow()` Funktion an. Die nimmt auch noch ein drittes Argument.

Schneller geht's wahrscheinlich nur noch wenn Du den fertigen Miller-Rabin aus der GMP Bibliothek nimmst, für die es eine Python-Anbindung gibt: gmpy.

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder