Das Erkennen von Primzahlen ist seit jeher ein wichtiges Problem in der Mathematik. Die Vorarbeiten zur asymmetrischen Kryptographie durch Martin Hellman und Whitfield Diffie haben aber auch ein starkes Interesse an Primzahlen in der Informatik erzeugt und ganze neue Industriezweige ermöglicht. Einige prominente Algorithmen (z.B. AKS, Solovay-Strassen und Miller-Rabin) zur Erkennung von Primzahlen verwenden Abwandlungen des kleinen Satzes von Fermat. Interessanterweise ist aber schon lange bekannt, dass dieser Satz nicht direkt als Primzahltest verwendet werden kann, da es zusammengesetzte Zahlen gibt, die so nicht von Primzahlen unterschieden werden koennen. Diese Zahlen sind als (Fermat-)Pseudoprimzahlen bekannt. Um tiefere Einblicke in die Funktionsweise der bekannten Primzahltests zu bekommen, ist es also interessant Eigenschaften dieser Pseudoprimzahlen zu untersuchen. Obwohl bekannt ist, dass es unendlich viele solcher Zahlen gibt, ist wenig über ihre Anzahl unter einer gegebenen Schranke bekannt.
Seit einigen Jahren verbreiten sich sehr preisgünstige und extrem leistungsfähige Multiprozessorarchitekturen, wie z.B. der, in der Playstation 3 verbaute, CELL-Prozessor von IBM mit bis zu 200 GFlops.
In diesem Projekt soll beschrieben werden, welche Möglichkeiten und Probleme sich ergeben, wenn man alle Pseudoprimzahlen unter einer gegebenen Schranke mit Hilfe von (vielen) CELL-Prozessoren finden will. Dabei ergeben sich auch weitere Hinweise auf die Eignung dieser Prozessorarchitektur für andere zahlentheoretische Fragestellungen.
Letzte Änderung: 11.11.24