Primzahlen: IIIb. Kapitel: Primfaktorzerlegung

Primfaktorzerlegung

Einleitung

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

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 $n$ läßt sich als Produkt zweier ungerade natürlicher Zahlen $t_1$ und $t_2$ darstellen:

$n=t_1\cdot t_2$

Man kann, unter der Bedingung $t_2<t_1$, zwei natürliche Zahlen $a$ und $b$ mit $b<a$ finden, so dass $t_1=a+b$ und $t_2=a-b$ gilt, nämlich als Lösung eines linearen Gleichungssystems mit den Variablen $a,$ und $b$. Über die dritte binomische Formel kommt man zu der Gleichung $n=a^2-b^2$:

$n=t_1\cdot t_2={\left(\frac{t_1+t_2}{2}\right)}^2-{\left(\frac{t_1-t_2}{2}\right)}^2=a^2-b^2$

Man kann $n$ also auch als Differenz zweier Quadrate ansehen Das ist die Grundlage für die Primfaktorzerlegung nach Fermat: Wenn man eine Quadratzahl $a$ findet, so dass für $a^2-n=r$ auch $r$ ein Quadrat ist $(r=b^2),$ 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 $a$ mit $a^2>n.$ Die obere Grenze liegt bei $a=\frac{n-1}{2}+1,$ so dass $b=\frac{n-1}{2}$ 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

Zu faktorisieren ist die Zahl 19043. Die untere Grenze liegt bei $a=138$ und die obere Grenze bei $a=9522.$ Schon bei

$138^2-19043=19044-19043=1$

findet man ein Quadrat, was die Zerlegung

$19043=138^2-1^2=(138+1)(138-1)=139\cdot 137$

liefert.

Wie man sehen kann, liegt der kleinste positive Treffer $a^2-n=b^2$ mit $a=138$ 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:

$9522^2-19043=90668484-19043=90649441=9521^2,$

was die Zerlegung

$19043=9522^2-9521^2=(9522+9521)(9522-9521)=19043\cdot 1$

liefert.

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

Das negative Beispiel

Zu faktorisieren ist die Zahl 12341. Die untere Grenze liegt bei $a=112$ und die obere Grenze bei $a=6170.$

$112^2-12341=12544-12341=203$ ist kein Quadrat,

$113^2-12341=12769-12341=428$ ist kein Quadrat,

und so weiter. Erst bei

$165^2-12341=27225-12341=14884=122^2$

findet man ein Quadrat, was die Zerlegung

$12341=165^2-122^2=(165+122)(165-122)=287\cdot 43$

liefert.

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

$\begin{array}{cccccc}12341& =171^2-130^2& & =(171+130)(171-130)& & =287\cdot 43\\ 12341& =885^2-878^2& & =(885+878)(885-878)& & =1763\cdot 7\\ 12341& =6171^2-6170^2& & =(6171+6170)(6171-6170)& & =12341\cdot 1\\ \end{array}$

Erst bei $a=165$ liefert die Gleichung $a^2-n=b^2$ 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.