Die Rückkehr der Primzahl

Posted by Jesco Freund at Sept. 2, 2010 9:16 p.m.

Vor über einem Jahr hatte ich mal über einen kleinen Wettstreit bezüglich eines Primzahl-Generators gebloggt. Damals hatte ich mich darauf beschränkt, das Problem durch geschickte Partitionierung des zu testenden Intervalls zu parallelisieren. Allerdings war meine Implementierung alles andere als perfekt und krankte vor allem an Pythons Global Interpreter Lock. Meine Freundin hatte mich mit ihrer Implementierung fast um Faktor 2 geschlagen

Doch nun habe ich sie in Händen, die ultimative Waffe des Primalitätstesters: im Zen Python Blog ist die Implementierung des Miller-Rabin-Tests in Python wunderbar beschrieben und erklärt. Dieser Test ist probabilistisch; nach unseren Spielregeln muss also bei einem positiven Treffer auf jeden Fall ein deterministischer Test (Primfaktorzerlegung) durchgeführt werden. Allerdings liefert Miller-Rabin verhältnismäßig wenige False Positives, so dass sich mit Hilfe dieses Tests das Finden von Primzahlen noch deutlich beschleunigen lassen sollte.

No comments | Defined tags for this entry: algorithms, programming, Project Euler, python

Comments

No comments