Primzahlen: IIIb. Kapitel: Primfaktorzerlegung

Primfaktorzerlegung

Einleitung

Bearbeiten

Angenommen, man hat eine Zahl vor sich, z.B. 7657 und möchte nun die Teiler dieser Zahl bestimmen. Mal vorausgesetzt, es handelt sich um keine Primzahl, kann man anfangen, die Zahl auf einzelne Teiler zu testen:

Die letzte Ziffer ist 7, also ist sie weder durch 2 noch durch 5 teilbar. Die Quersumme ist 25, die nicht durch 3 teilbar ist, und damit ist 7657 auch nicht durch 3 teilbar.
Durch 7 dividiert ergibt 7657 als Ergebnis 1093 Rest 6. Folglich ist 7657 auch nicht durch 7 teilbar. Machen wir es kurz: 7657 ist auch nicht durch 11, 17, 23 und 29 teilbar. Die Primfaktorzerlegung von 7657 ist 13·19·31.

Um die Primfaktorzerlegung zu Automatisieren, kann man nun, rein theoretisch, die Teilbarkeit durch eine Liste von Primzahlen testen, die in dem Programm fest vorgegeben ist. Das hat zwei Nachteile:

  1. Das Programm wird dadurch ziemlich groß.
  2. Es besteht immer die Möglichkeit, dass die Zahl, zu der die Primfaktorzerlegung durchgeführt werden soll, Primfaktoren enthält, die in dem Programm nicht vorhanden sind.

Die Mutter aller Faktorisierungsverfahren

Bearbeiten

Es gibt ein Verfahren, mit dem man diese Probleme umgehen kann. Dieses Verfahren heißt nach dem französischen Amateurmathematiker Pierre de Fermat die Primfaktorzerlegung nach Fermat. Aber zuerst ein paar Überlegungen:

Eine zusammengesetzte, ungerade natürliche Zahl   läßt sich als Produkt zweier ungerade natürlicher Zahlen   und   darstellen:
 
Man kann, unter der Bedingung  , zwei natürliche Zahlen   und   mit   finden, so dass   und   gilt, nämlich als Lösung eines linearen Gleichungssystems mit den Variablen   und  . Über die dritte binomische Formel kommt man zu der Gleichung  :
 
Man kann   also auch als Differenz zweier Quadrate ansehen Das ist die Grundlage für die Primfaktorzerlegung nach Fermat: Wenn man eine Quadratzahl   findet, so dass für   auch   ein Quadrat ist   so kann man zwei Teiler bestimmen.

Bei dem Fermatschen Verfahren sind ein paar Dinge zu beachten:

  1. Das fermatsche Verfahren kann nur ungerade Zahlen faktorisieren. Zweierpotenzen sind also vor der Primfaktorisierung zu entfernen.
  2. Das fermatsche Verfahren kann Quadrate nicht von Primzahlen unterscheiden (dazu später mehr).

Der Bereich des Fermatschen Verfahren läßt sich eingrenzen:

Man beginnt bei dem kleinsten   mit   Die obere Grenze liegt bei   so dass   ist.

Die Effizienz des Faktorisierungsverfahren nach Fermat hängt vom Aufbau der zu testenden Zahl ab. Es folgen ein ideales und ein negatives Beispiel.

Das ideale Beispiel

Bearbeiten

Zu faktorisieren ist die Zahl 19043. Die untere Grenze liegt bei   und die obere Grenze bei   Schon bei

 

findet man ein Quadrat, was die Zerlegung

 

liefert.

Wie man sehen kann, liegt der kleinste positive Treffer   mit   bei der unteren Grenze. Und nicht nur das, er liefert auch gleich die vollständige Primfaktorzerlegung 19043 = 137·139 zurück. Dass dies so ist, liegt daran, dass die Zahl nur aus zwei Primfaktoren besteht und außerdem die beiden Primfaktoren dicht beieinander liegen.

Die obere Grenze führt noch zu:

 

was die Zerlegung

 

liefert.

So ein Fall kommt eher selten vor; deshalb folgt noch das Negativbeispiel.

Das negative Beispiel

Bearbeiten

Zu faktorisieren ist die Zahl 12341. Die untere Grenze liegt bei   und die obere Grenze bei  

  ist kein Quadrat,
  ist kein Quadrat,

und so weiter. Erst bei

 

findet man ein Quadrat, was die Zerlegung

 

liefert.

Die weiteren Prüfungen liefern (nur) für die Zahlen 171, 885 und 6171 Treffer. Diese Zahlen führen zu folgenden Zerlegungen:

 

Erst bei   liefert die Gleichung   den ersten positiven Treffer. Das bedeutet, es müssen 53 Quadratzahlen getestet werden, bis der erste Treffer gefunden wird. Demgegenüber findet man beim Divisionsverfahren schon mit der vierten Primzahl (der 7) einen Teiler. Noch schlechter ist, dass 12341 = 287·43 nicht die komplette Primfaktorisierung zurückliefert.

Man braucht alle drei Treffer, um alle Primfaktoren zu ermitteln, und erst ein Kreuzvergleich über den größten gemeinsamen Teiler mit allen Teilergebnissen bringt Sicherheit.