Primzahlen
Ueber längere Zeit habe
ich mich intensiv mit der Charakteristik von Primzahlen auseinandergesetzt.
Eine Herausforderung war
dann auch eine grösste bekannte Primzahl zu suchen. Es gibt da ein Projekt mit namen
GIMPS. An diesem Projekt sind Weltweit zehntausende Computer beteiligt. Fast
zweieinhalb Jahre waren diese Computer nach der Suche einer grössten noch nicht
bekannten Primzahl. Am 17.November 2003 war eine neue Primzahl gefunden worden.
Es ist die vierzigste Mersenne’sche Primzahl. Die 20'996'011-te Zweierpotenz
-1. Diese Zahl hat 6'320'430 Dezimalstellen. Die Zahl ist so gross dass man sie
nicht einmal mit etwas veraunschaulichen könnte. Mit einer verhältnissmässig
winzigen Zahl von 200 Dezimalstellen, kann man nämlich bereits jedes Atom im
Universum nummerieren.
Eine Mersenn’sche
Primzahl hat die Form (2 hoch n)-1 wobei
n eine Primzahl sein muss.
Für mich war es
natürlich nicht intressant, einer von den Zehntausenden Usern zu sein. Ich
mache nämlich keine Glücksspiele. Vielmehr suchte ich nach einem neuen
Algorithmus zur Bestimmung von Mersenne’schen Primzahlen oder um eine
effizientere Lösung der Implementation des bisher schnellsten Algorithmen.
Ich hatte etliche Dinge
untersucht, um einen neuen Algorithmus anwenden zu können. Zuguterletzt habe
ich zwar einiges begriffen aber nach wie vor blieb der Lucas-Lehmer Test der
effizienteste um Mersenne’sche Primzahlen zu testen.
Also gut, ich
implementierte zuerst einmal den Lucas-Lehmer Test für kleine Zahlen. Dann
baute ich einen Rechner mit den Grunrechenoperationen für riesige Zahlen mit
Millionen von Dezimalstellen. Diesen Rechner verwendete ich dann für den
Lucas-Lehmer Test.Den Rechner kannst Du dir übrigens Gratis herunterladen mit
folgendem Link: Riesiger
Rechner
Dieser Rechner basierte
auf Schulmathematik und war natürlich viiiiel zu langsam. Aber ich brauchte
unbedingt diese Implementation um andere Verfahren überprüfen zu können.
Für den Lucas-Lehmer
Test brauchte ich folgende Funktionen:
A eine
Funktion um eine Zahl zu Quadrieren.
B eine
Funktion um von einer Zahl 2 zu subtrahieren. (jaja, tönt simpl ….)
C eine
Funktion um den Rest einer Divison, mit der Mersenne’schen Zahl als Divisor, zu
bestimmen. (Modulofunktion)
B Die
Funktion um -2 zu subtrahieren, kann effizient programmiert werden unter
Berücksichtigung, dass sie nur in extrem ungünstigen Fällen, welche extrem
selten auftreten, einige tausendstel Sekunen CPU Zeit verbraucht.
C Eine
superelegante Lösung habe ich für die Restwertdivision gefunden. Die Lösung ist
einfach und trotzdem hammer gut. Wie es geht
ist kein Geheimnis, wenns Dich
intressiert dann klicke auf folgenden Link:
Pitri's Restwertberechnung
A Es bleibt
noch einen effizienten Algorithmus zum Quadrieren zu finden.
Das ist wirklich ein
happiges Problem und hat mich lange beschäftigt. Nachdem ich einige
effizientere Multiplikationsalgorithmen, als den Algorithmus der
Schulmathematik, studiert habe, musste ich einsehen, dass auch mit den besseren
nicht das gelbe vom Ei erreicht wird.
Nach ‚Schönhage und
Strassen’ lässt sich mittels (missbrauchen) der ‚Fourier-Transformation’ eine sehr
schnelle Multiplikation durchführen. Von der Fourier Transformation hatte ich
keinen Schimmer…. Wie war das schon wieder mit den komplexen Zahlen… zum Glück
habe ich gute Freunde welche mir da wieder mal einiges erklärt haben. Und siehe
da, die Fourier Transformation ist ja gar nicht schwierig durchzuführen. Aber
was schwierig ist, das ist die Fourier Transformation zu verstehen. Nun gut,
als nächstes habe ich dann die Multiplikationsfunktion mit der Fourier
Transformation implementiert und in den Lucas-Lehmer Test eingebaut. Das
funktioniert wunderbar, aber ist viiiiiiel zu langsam. Wirklich effizientes
Multiplizieren ist nur mit der Fast-Fourier-Multiplikation möglich. Nachdem ich mir auch diese zu Gemüte
geführt habe, implementierte ich den Lucas-Lehmer Test auch noch mit der
Fast-Fourier-Transformation. Endlich funktionierte die Sache recht effizient.
Aber bei allem Respekt.. es war immer noch zu langsam….
Ich hatte während ich
die Fast-Fourier-Transformation (abgek. FFT) studiert hatte, eine Frage welche
ich niergends nachlesen konnte. Wieso rechnet man nicht mit einer möglichst
grossen Basis ?
Würde man nämlich die
FFT in einem anderen Zahlensystem rechnen so könnte man viel, sehr viel
effizienter multiplizieren. Das heisst der Trick basiert eigentlich darauf,
dass je grösser die Basis ist, je kleiner wird die Anzahl Koeffizienten für die
Diskrete Fourier Transformation (abegk. DFT, Teil der FFT).
Ausgerichtet für mein Computer mit 32bit Archidektur wählte ich. statt das
uns geläufige Zehnersytem, das Zahlensystem mit Basis 4294967296.
Das bringt natürlich
sehr hohe Geschwindigkeitszunahme. Ein Inputvektor welcher zuvor im
Dezimalsystem 20 Koeffizienten hatte braucht noch 3 Koeffizienten.
Ich habe also den ganzen
Lucas-Lehmer Test umgeschrieben zur Basis
4294967296.
Das Funktionierte
tatsächlich. Jedoch bereits bei Multiplikationen mit etwas über 500 Stellen
stimmte das Ergebnis der Multiplikation nicht mehr.
Alle Programme habe ich
in C geschrieben. In C hat ein Datentyp Longint 32 Bit und ein Datentyp Double
80 Bit. Wenn ich den grösstmöglichen Longint quadriere gibt das eine 64 Bit
Zahl. Ich hatte ohne Ueberprüfung angenommen dass dieses Resultat absolut genau
in einen Double Typ eingetragen wird. Dem ist eben nicht so. Obschon der Double
Typ genug gross wäre um das Resultat aufzunehmen wird das Resultat gerundet.
Es blieb mir nichts
anderes übrig als eine kleinere Basis nämlich 16 Bit also Basis 65536 zu wählen
damit ich noch korrekte Resultate erhalte. Das ist natürlich sehr schlecht und
verlangsamt den Algorithmus um das X-Fache. Die Inputvektoren werden doppelt so
lang und die 32 Bit Archidektur meines Computers wird nicht ausgenutzt.
Trotzdem habe ich den
Lucas-Lehmer Test umgeschrieben zur Basis
65536.
Endlich konnte ich
grosse Zahlen Testen. Aber wieder gabe es Probleme. Mersenne’sche Primzahlen
grösser (2 hoch 19937)-1 wurden nicht mehr korrekt berechnet….
Ich vermute, die
berechneten Einheitswurzeln sind zu ungenau und daraus entstehen bei sehr
grossen Multiplikationen Fehler. Die
Einheitswurzeln berechne ich mit Sinus und Cosinus der Standartlibraries. Ich
weiss also nicht wie genaue Resultate diese Funktionen liefern…..
Man muss sich schon im
Klaren sein, ein einziges falsches Bit und alles ist im Eimer…..
Vielleicht untersuch ich
das irgenwann.. aber für mich ist die Sache vorerst
mal abgeschlossen. Ich habe einfach keine Zeit mehr um gratis an solchen
Projekten zu arbeiten.
Warum habe ich überhaubt
so viel Zeit investiert… Ich habe gehofft einen schnelleren Lucas-Lehmer Test zu
programmieren als der bisherige von GIMPS. Leider bin ich steckengeblieben…
obschon ich noch weitere Ideen zur Verbesserung hätte finde ich die
Entscheidung richig, an diesem Punkt aufzuhören.
Falls sich jemand
intressiet, kann er sich hier einige C-Sourcen und Exe Files downloaden.
Die C-Sourcen stelle ich
zur freien Verfügung. Jede Source ist eine abgeschlossene Applikation. Es
braucht keine speziellen Libraries. Compiliert werden kann jede C-Source als
Konsolenapplikatione mit Visual C++ 6.0 . Ansonsten sind die enthaltenen Funktionen auch
problemlos portierbar. Zur Downloadseite