Banner der Website mathematik.de. Motiv: Überall ist Mathematik

Primfaktorzerlegung

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.

Links: