Primzahlen: III. Kapitel: Primfaktorzerlegung und andere Methoden

Einleitung

Es sind häufig zwei Fragen, die sich in Bezug auf die Primzahlen stellen:

Ist die vorliegende Zahl eine Primzahl?
Wie läßt sich die vorliegende Zahl zerlegen?

Ist die vorliegende Zahl eine Primzahl?

Wenn die vorliegende Zahl sehr klein ist, also kleiner als 90, dann kann man schon mit etwas Überlegung sagen, ob es sich um eine Primzahl handelt, oder nicht. Die 91 ist der erste kleine Stolperstein, da sie die erste Zahl ist, deren sämtliche Primfaktoren größer als fünf sind (91=7·13). Wer allerdings Primzahlen auswendig weiß, kann durchaus bis 127 und höher kommen. Aber wer lernt schon vier- oder mehrstellige Primzahlen auswendig (333667 mag da, z.B. wegen ihrer Eigenschaften, eine Ausnahme sein). Also braucht man ein Verfahren, um solche Zahlen auf ihre Primalität zu testen.

Primzahlen: naive Ansätze

Probabilistische Verfahren

Fermat
Solovay-Strassen
Miller-Rabin

Sonderfall Sieb des Eratosthenes

Das Sieb des Eratosthenes ist ein Sonderfall. Im Gegensatz zu Verfahren, die einzelne Zahlen auf ihre Primalität prüfen, siebt das Siebverfahren aus einem vorgegebenen Zahlenbereich, von 2 bis zu einer vorgegebenen Obergrenze, alle Nichtprimzahlen aus, so dass nur die Primzahlen übrig bleiben. Dabei wird wie folgt vorgegangen. Jede natürliche Zahl zwischen 2 und der Obergrenze bekommt eine Art kleines Schild, auf der ihr Zustand bezüglich der Primalität geschrieben steht. Am Anfang werden alle Zahlen zwischen 2 und Obergrenze als Primzahl deklariert. Nun wird die erste Zahl genommen, das ist die 2, und nachgesehen, ob es eine Primzahl ist. Die 2 hat die Information Primzahl. Wenn also die 2 eine Primzahl ist, dann können alle Vielfachen von 2, angefangen mit 2² keine Primzahlen mehr sein. Dementsprechend wird auf allen Schildern der Vielfachen von 2, angefangen mit 2² bis Obergrenze, die Information von Primzahl auf Nichtprimzahl geändert. danach wird die nächste Zahl, das ist die 3, auf ihre Primalität getestet. Wieder werden, im Falle, dass es sich um eine Primzahl handelt alle Vielfachen in ihrem Zustand von Primzahl auf Nichtprimzahl geändert. Das Ganze wird solange gemacht, bis man die Quadratwurzel von Obergrenze erreicht hat, weswegen es sinnvoll ist, als Obergrenze eine Quadratzahl einzusetzen. Wenn man z.B. ein Zahlenfeld von 2 bis 10.000 siebt, dann muß man nur bis 100 testen, da 100² = 10.000 ist. Alle Zahlen größer 100, die noch auf ihrem Schild Primzahl stehen haben, sind auch Primzahlen.

Der Sinn des Sieb des Eratosthenes ist, Primzahltabellen zu erstellen, in denen man - bei kleineren Zahlen - nachsehen kann, ob es sich bei der gesuchten Zahl um eine Primzahl handelt. Im Anhang findet man mit Primzahlen: Tabelle der Primzahlen (2 - 100.000) eine Primzahltabelle (bzw. einen Teil einer Primzahltabelle), die mit einem Programm, das den Algorithmus Sieb des Eratosthenes benutzt, generiert worden ist.

Wie ist die Primfaktorzerlegung?

Primzahlen: Primfaktorzerlegung nach Fermat
Primfaktorzerlegung nach Lehman