Primzahlcheck

Gegeben sei eine positive ganze Zahl n, n ³ 2. Wie findet man am ökonomischsten heraus, ob n eine Primzahl ist? Bei kleinen Zahlenwerten, vielleicht bis 107, wird das Nachschlagen in einer Tabelle der schnellste und ökonomischste Weg sein. Eine solche Tabelle läßt sich z.B. mit dem Sieb des Erathostenes schnell und einfach erzeugen. Bei großen Zahlen - und die interessieren uns, versagt dieses Verfahren.

Teilen I

Wir vergegenwärtigen uns: eine Primzahl ist nur durch sich selbst und durch 1 teilbar, hat also keine echten Teiler. Was liegt näher, als die fragliche Zahl systematisch durch alle ganzen Zahlen ab 2 zu dividieren und zu prüfen, ob die Division aufgeht? Gesagt, getan, implementiert:

....

Hübsch, nicht wahr? Wenn jede Rechenoperation der Prozessors 1ns benötigt (so eine 1000MHz-Maschine), wie lange dauert es dann herauszufinden, ob 232-1 eine Primzahl ist? Oha! das sind ja 4 Sekunden! Dieser Zahlenwert liegt knapp über 4 Milliarden, hat also 10 Ziffern. Wie sieht es mit einer etwa doppelt so langen Zahl aus?

Gesetzt den Fall, wir wollten das Ergebnis der Prüfung von 264-1 erfahren, dann erschrecken wir: die Rechnerei bräuchte 232 ´ 4 Sekunden, das sind ca. 199000 Tage, also gerade mal so 545 Jahre. Die Aufgabe muß also ungelöst liegen bleiben!? Quatsch! Wir müssen etwas mehr nachdenken!

 Teilen II

Bereits ein flüchtige Betrachtung zeigt, daß ein zusammengesetzte Zahl n = k ´ l mindestens 2 Faktoren hat, von denen einer nicht größer als die Quadratwurzel aus n sein kann. Die Prüfung sollte sich also auf den Bereich bis zur Quadratwurzel des Argumentes beschränken. Und siehe da: plötzlich benötigt die vorige Aufgabe gerade wieder die 4 Sekunden, die wir vorhin zähneknirschend zur Kenntnis nahmen.
Die Anzahl der Divisionen kann weiter reduziert werden, wenn bedacht wird, daß Teiler wie 2 oder 5 in den systematisch benutzen Versuchsteilern vorkommen. Damit läßt sich die Rechenarbeit deutlich unter die Hälfte der vorhin genannten Zeit drücken. Genauer: nur 40% sind noch erforderlich. Unter der Annahme, daß uns eine Primzahltabelle ausreichender Länge zur Verfügung steht, läßt sich dieser Wert nochmals verkleinern.

Auf diese Art wurde eine Aufgabe, die praktisch unlösbar schien, zu einer, die für die Bearbeitung mit dem Computer blendend geeignet ist. Nun ist der HP ein maßloser Mensch, der die Frage auf Zahlen der Größe 2128-1 ausdehnt. Das Ergebnis unserer Abschätzung ist keine Überraschung. Schon wieder sind 545 Jahre Rechenzeit fällig! Naja, Teilfaktoren 2 und 5 rausgerechnet: 217 Jahre - für die Praxis unakzeptabel. Wir müssen auf ein anderes Denkmodell umschwenken und die Denkbarriere überwinden, die durch die Definition der Primzahleigenschaft gegeben wurde. Tatsächlich haben wir bisher Faktorisierungen gesucht, anstatt einfach zu prüfen, ob n prim ist.

Anders ausgedrückt - wir haben zuviel Arbeit in die falschen Algorithmen gesteckt.

Was die "richtigen" Algortihmen sind, vermag ich hier nicht darzustellen (möglichweise gibt es gar kein richtige Verfahren, sondern nur mehr oder weniger ungünstige), aber ich kann einige bessere Methoden vorstellen. Bezeichnenderweise werden sie als "höhere" Verfahren in der Literatur geführt, nicht zuletzt wegen des benötigten mathematischen Hintergrundwissens.

 Fermat und Euler

Diesen beiden Mathematiker verdanken wir zwei interessante Kongruenzsätze.


 Programmcodes

---


 Primzahlcheck

Sogenannte "höhere" Verfahren nutzen algebraische Eigenschaften der Primzahlen aus. Einer der derzeit schnellsten Tests ist das sog. ARCL-Verfahren, das speziell zum Prüfen sehr langer Zahlen dient.

...

Gehen wir von einen 32-Bit-Prozessor aus.

...

Die ganze Rechnerei schnurrt zu einer Sache von Millisekunden zusammen - eine Ergebnis, mit dem wir getrost Feierabend machen dürfen.


Stand: 09.04.2003 /
 HPs Home      Primzahlen/Home