Informatik und Elektronik Hacklab Verein Schweiz

REGISTER LOGIN

Primzahlen Generator

Die Ermittlung der Primzahlenabfolge ist eine der grössten Herausforderung der modernen Mathematik. Viele hochbegabte Mathematiker haben bei der Formel suche nach der Berechnung der Primzahlenabfolge entweder längst aufgegeben oder wurden bei dem Versuch selbst Wahnsinnig.

Die Primzahlenabfolge ist die wichtigste Zahlenfolge in der Mathematik. Primzahlen sind die Atome der Zahlen Welt und sind die Zahlen welche nur durch eins oder durch sich selbst Teilbar sind.

Es gibt Wissenschaftler welche glauben das in den Primzahlen der Schlüssel zu geheimen Informationen steckt. Einige davon sind der Meinung das mit den Primzahlen die Physikalische Gesetze des Universum im speziellen in dem Bereich der Atome und Elektronen besser verstehen werden können. Im Hollywood Film "Contact" mit Jodie Foster zum Beispiel nehmen hoch entwickelte Ausserirdische Zivilisationen mittels komplexe Mathematikformeln und Primzahlen kontakt zu den auf der Erde lebenden Menschen auf.

Über ein Jahrhundert haben Mathematiker in aller Welt nach einer Struktur in den Primzahlen gesucht und sind daran verzweifelt. Euklid hat in der Antike bewiesen das es unendlich viele Primzahlen gibt.

Im 18. Jahrhundert hat der Schweizer Mathematiker Leonard Euler als einer der ersten die Vermutung geäussert das es ein Zusammenhang zwischen Primzahlen und Physikalische Gesetzte gibt ja sogar eine kosmische Verbindung. Der im Jahre 1772 an der Akademie der Wissenschaften berufene Euler gilt als der Begründer der Analysis dessen Leidenschaft den Primzahlen gehörte. Euler stellte sich die Primzahlen als Treppenstufen auf einem Langen Treppenweg vor welche er im Geiste beschritt.

Einer der bekanntesten und bedeutendster Mathematiker aus den 1950 Jahren welche die Primzahlen zum Wahnsinn getrieben haben ist der Amerikaner J. Nash dessen Leben im Hollywood Film "A Beautyfull Mind" verfilmt wurde.

Die Grundlage moderner Verschlüsselungstechnik beruht zudem darauf, dass es äusserst schwierig ist, von einer Zahl, die das Produkt zweier sehr grosser Primzahlen ist, zu ermitteln, aus welchen beiden Primzahlen diese Zahl zusammen multipliziert wurde. Das ist insofern wichtig, als der elektronische Zahlungsverkehr und andere Datenübertragungen der digitalen Welt ohne Verschlüsselungen nicht auskommen - und die funktionieren eben mit sehr grossen Primzahlen.

Ermittlung der Primzahlen

Zur Ermittlung der Primzahlen wird ein selbst geschriebener Primzahlengenerator verwendet welcher in der Programmiersprache C# / .NET programmiert wurde. Der Vorteil dieser Programmiersprache ist es dass der Programmcode mithilfe des Open Source Projekts Mono der Firma Novell sehr einfach auf jede mögliche Computer Betriebssystem Plattform wie Microsoft, Apple oder Linux ausführbar ist. Es ist ähnlich wie Java nur das es nicht von Oracle stammt sondern von den Entwickler des Hauses Microsoft. Das heiss man programmiert das entsprechende Programm nur einmal und hat dafür die Möglichkeit es auf jede beliebige Plattform laufen zu lassen.

Der Algorithmus zur Berechnung der Primzahlen ist relativ einfach und beruht auf die sichere Siebtechnik welche heute als Standard verwendet wird um Primzahlen zu ermitteln.

Da alle gerade Zahlen wie zum Beispiel 4, 6, 8, 10 usw. ein vielfaches der Primzahl 2 sind werden diese bei der Ermittlung der Primzahlen ausgeschlossen in dem zu einer aktuell zu berechnenden und bestehenden ungeraden Zahl X nach der Schleifen Wiederholung 2 dazu addiert (x=x+2) um so die nächste ungerade Zahl zu erhalten und somit die gerade Zahl zu überspringen.

Bei allen Ungeraden Zahlen in der Schleife werden am Anfang stets zwei führende Primzahlen Tests durchgeführt. Zum einen wird geprüft ob die entsprechende ungerade Zahl ein vielfaches der Primzahl 3 mittels der Modulo Funktion ist. (x % 3)

Ebenfalls wird überprüfft ob die entsprechende ungerade Zahl ein vielfaches der Primzahl 5 mittels der Modulo Funktion ist. (x % 10)

Ist die entsprechende ungerade Zahl weder durch die Primzahl 3 Teilbar noch durch die Primzahl 5 findet das testen durch alle übrigen in der liste gespeicherte Primzahlen statt.

Findet sich keine gespeicherte Primzahl in der Liste welche die Zahl X in der Schlaufe teilt ist die entsprechende Zahl unteilbar und somit eine Primzahl. Die neu ermittelte Primzahl wird am Schluss in die entsprechende Liste der Primzahlen aufgenommen. PrimZahlen.Add(x);


			for(double x=StartZahl; x<=nMax; x=x+2) {	
				Wurzel3 = x % 3;
				Wurzel10 = x % 10;

				if( Wurzel3 != 0 && Wurzel10 != 5 && && Wurzel10 != 0) {
					//Zahl ist weder durch die Primzahl 3 noch durch die Primzahl 5 Teilbar
					
					bPrimTeilbar = false;
					//Find the nearest Index in the List for the Prime Number x/2 to stop dividing the number X
					//by Primes in the List that Multiplied by itself are bigger than the Number x 
					nMaxLooping = PrimZahlen.IndexOf((x / 2)+1);

					for(unsigned double y = 0; y < nMaxLooping; y++) {
						if(x % PrimZahlen[y] == 0) {
							bPrimTeilbar = true;
							break;
						}
					}
					
					if(bPrimTeilbar==false) {
						Console.WriteLine(x);

						if(bDataBase) {
							//Insert Prime Number into Database

							SQLQuery.CommandText = "INSERT INTO UnteilbareZahlen (primzahl) VALUES ('" + x + "');";
							SQLQuery.ExecuteNonQuery();
						}

						PrimZahlen.Add(x);
					}
				}
			
}

Aktueller Status

Die Ermittlung der unendlichen Primzahlen ist ein Gebiet bei welchen man stets einen Computer Rechner Vollauslasten und welche Ihn an die Leistungsgrenze bringen kann. Die unendliche niemals aufhörende grosse Anzahl an Primzahlen welche stets durch die zuvor unendlich ermittelten Primzahlen reziprok aka rückwirkend getestet werden müssen bringt jeden Computer Rechner früher oder später an seine Grenzen.

Aktuell wurden auf einen D630C DualCore Dell Laptop mittels dem oben aufgeführten simplen Algorithmus und dem unten verfügbaren Primzahlengenerator die ersten 140 Millionen Zahlen getestet und davon knapp 8 Millionen Primzahlen ermittelt.

Ziel ist es mit einem noch besseren und stark optimierten Algorithmus sowie einer dezentralen Server und Client Programmstruktur Milliarden von Primzahlen über das Internet in Verbund mit anderen zu ermitteln.

Test und Download

Der aktuelle Primzahlengenerator kann in der neuesten Version hier heruntergeladen werden.

Für die Ausführung des in Microsoft C# / .NET geschriebenen Programm auf Plattformen wie Linux oder Apple benötigen sie zusätzlich das Open Source Programm MONO. Unter Linux kann das Programm wie folgt gestartet werden "mono PrimZahlenGenerator.exe"

Um die ermittelten Primzahlen Lokal zu speichern wird optional eine MySQL Datenbank Server mit der Tabelle "UnteilbareZahlen" und der Spalte "primzahlen" benötigt.


Powered by LionWiki. Projekte Recent changes Last changed: 2014/01/04 10:36 History