Funktion optimieren (Miller-Rabin-Primzahltest)

[rico]

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.

[SigMA]

http://www.python.org/doc/essays/list2str.html
http://wiki.python.org/moin/PythonSpeed/PerformanceTips

Möge Google mit dir sein

SigMA

[BlackJack]

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.