Primfaktorenzerlegung

aus www.mathematik.de
Das Problem

Jede natürliche Zahl ist entweder eine Primzahl oder - bis auf die Reihenfolge - eindeutiges Produkt von zwei oder mehr Primzahlen. Dieses Produkt nennt man die Primfaktorzerlegung der Zahl.

Ordnet man die Primfaktoren ihrer Größe nach, so spricht man von der kanonischen Primfaktorzerlegung.

Wie kann ich diese Zerlegung einer gegebenen Zahl finden?

Die Lösung

Das vorgestellte Verfahren arbeitet mit einer einfachen Idee: Um alle möglichen Primfaktoren einer natürlichen Zahl n zu bestimmen, teste ich alle in Frage kommenden Primzahlen, mit der 2 beginnend.

In Frage kommen diejenigen Primzahlen, welche kleiner als die Quadratwurzel von n sind: Ist nämlich n Produkt mehrerer Zahlen, so müsste zumindest eine davon kleiner oder gleich der Quadratwurzel von n sein. Falls diese eine Primzahl wäre, so hätte sie als Primfaktor im vorgestellten Verfahren bereits gefunden werden müssen, im anderen Fall aber ihre Primfaktoren.

Wurde auf die beschriebene Weise ein Primfaktor p entdeckt, wird die Berechnung nicht mit n, sondern mit n/p fortgeführt. Da alle Faktoren kleiner p bereits untersucht sind, muss nun überprüft werden, ob p noch einmal als Primfaktor auftaucht, ob also auch n/p ohne Rest durch p teilbar ist. Dies wird solange fortgesetzt, wie das Divisionsergebnis ohne Rest durch p teilbar ist. Dann wird das Verfahren mit der nächstgrößeren Primzahl fortgesetzt. Entsprechend werden nun in aufsteigender Reihenfolge alle Primzahlen getestet, bis das letzte Divisionsergebnis selbst eine Primzahl ist. Das ist genau dann der Fall, wenn ich in der Liste der Primzahlen auf eine Zahl stoße, die größer als die Quadratwurzel meines letzten Divisionsergebnisses ist.

Wird bis zum letzten Schritt kein Primfaktor gefunden, ist n Primzahl.

Beispiele

• 101 : 2 nicht ohne Rest teilbar

  101 : 3 nicht ohne Rest teilbar

  101 : 5 nicht ohne Rest teilbar

  101 : 7 nicht ohne Rest teilbar

  Die nächste zu betrachtende Primzahl wäre die 11, aber 11 * 11 = 121 > 101.

  Somit ist 101 Primzahl, ihr einziger Primfaktor ist die Zahl selbst.

   

• 504 : 2 = 252

  252 : 2 = 126

  126 : 2 = 63

  63 : 2 nicht ohne Rest teilbar

  63 : 3 = 21

  21 : 3 = 7

  7 ist Primzahl, also lässt sich 504 eindeutig in folgende Primfaktoren zerlegen:

  2 * 2 * 2 * 3 * 3 * 7 = 8 * 9 * 7 = 504

   

• 123456 : 2 = 61728

  61728 : 2 = 30864

  30864 : 2 = 15432

  15432 : 2 = 7716

  7716 : 2 = 3858

  3858 : 2 = 1929

  1929 ist ungerade, also offensichtlich nicht ohne Rest durch 2 teilbar.

  1929 : 3 = 643

  643 ist nicht ohne Rest teilbar durch 5, 7, 11, 13, 17, 19, 23, also Primzahl (die nächste Primzahl nach 23 wäre 29, 29 ist aber größer als die Quadratwurzel von 643).

  123456 = 2*2*2*2*2*2 * 3 * 643.

Aus diesen Beispielen sollte schon deutlich geworden sein, dass der Aufwand für die Primzahlzerlegung mit dem vorgestellten Verfahren mit der Größe der untersuchten Zahl zunimmt. Da die Zerlegung sehr großer Zahlen in der Praxis -zum Beispiel in Verschlüsselungsverfahren, vergleiche den Artikel zum RSA Verfahren- eine bedeutende Rolle spielt, gibt es hierfür optimierte Faktorisierungsverfahren.