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

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:

Samstag 4. November 2006, 14:14

Leichtdio.de - Das Kreativ-Blog
http://www.leichtdio.de
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.
Antworten