"Auch Mathematiker gehen zuweilen auf Rekordjagd" formulierte die Wochenzeitschrift DIE ZEIT am 17.5.1996 in ihrem Bericht über unseren Primzahlzwillingsrekord. Hintergrund dieses "sportlichen Erfolges" war die Entwicklung und Implementierung von Programmen für sehr schnelles Rechnen mit sehr großen Zahlen, wobei "sehr große Zahlen" in diesem Kontext Zahlen mit Milliarden von Binärstellen bedeuten. Wir berichten hier über den ersten Einsatz dieser Programme in der Computational Number Theory, der zu mehreren Weltrekorden führte, und skizzieren weitere Anwendungsmöglichkeiten in der Numerik und Computeralgebra. 

Primzahlen - Zufall oder Gesetz?

Uns allen ist bekannt: Eine Primzahl ist eine natürliche Zahl größer als 1, die durch keine weitere natürliche Zahl außer der 1 geteilt wird. Dies ist auch die Definition der Zahlentheoretiker, andere Mathematiker benutzen ab und zu andere Definitionen. So ist etwafür den

Funktionentheoretiker eine Primzahl die ganzzahlige Wurzel einer gewissen analytischen Funktion, für den Algebraikerist sie "die Charakteristik eines endlichen Körpers" oder "eine nicht-archimedische Bewertung", und der Logiker definiert sie als die positiven Werte eines geeigneten Polynoms mit 26 Variablen. Wir begnügen uns mit der erstgenannten Definition.

Über die Verteilung der Primzahlen haben wir bereits seit Euklid erste Informationen: Es gibt unendlich viele Primzahlen. Seine Argumentation gilt bis heute als Paradebeispiel für einen eleganten mathematischen Beweis, den wir alle in der Schule kennengelernt haben und den auch die, für die Mathematik ein Horror war, verstehen konnten. Angenommen, es gäbe nur endlich viele Primzahlen p₁,...., p_n . Dann wäre das Produkt aller dieser Zahlen plus eins - d.h. p₁×...× p_n+1 - durch keine von ihnen teilbar und würde damit durch eine Primzahl geteilt, die nicht unter den p₁,...., p_n vorkommt. Dies ist aber ein Widerspruch zur Annahme, so daß es doch unendlich viele Primzahlen geben muß.