Zum Inhalt springen

Primfaktorzerlegung

Aus FLBK-Wiki
Version vom 15. November 2026, 07:57 Uhr von Flbkwikiadmin (Diskussion | Beiträge)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Jede natürliche Zahl größer als 1 lässt sich in Primzahlen zerlegen. Bei kleinen Zahlen ist das eine einfache Übung, bei sehr großen Zahlen gelingt es nicht in vertretbarer Zeit. Darauf beruht die Sicherheit des RSA-Verfahrens.

Definition

Die Primfaktorzerlegung ist die Darstellung einer natürlichen Zahl [math]\displaystyle{ n }[/math] als Produkt aus Primzahlen, die dann als Primfaktoren von [math]\displaystyle{ n }[/math] bezeichnet werden. Diese Darstellung ist (bis auf die Reihenfolge der Faktoren) eindeutig und zählt zu den grundlegenden und klassischen Werkzeugen der Zahlentheorie.

Primzahl

Eine Primzahl ist eine natürliche Zahl größer als 1, die ausschließlich durch 1 und durch sich selbst ohne Rest teilbar ist. Die Primzahlen bis 20 lauten:

2, 3, 5, 7, 11, 13, 17, 19

Teilbarkeitsregeln

Im Rahmen einer Primfaktorzerlegung ist es notwendig herauszufinden, ob eine zu zerlegende Zahl durch eine bestimmte Primzahl teilbar ist. Hierfür existieren hilfreiche Teilbarkeitsregeln. Eine ganze Zahl ist teilbar durch:

  • 2, wenn ihre letzte Ziffer durch 2 teilbar ist (sie also auf 0, 2, 4, 6 oder 8 endet).
  • 3, wenn ihre Quersumme durch 3 teilbar ist.
  • 5, wenn ihre letzte Ziffer durch 5 teilbar ist (sie also auf 0 oder 5 endet).

Es ist relativ einfach und schnell zu erkennen, ob eine Zahl durch 2, 3 oder 5 teilbar ist. Wenn allerdings größere Primzahlen im Spiel sind, ist eine schriftliche Division oder der Einsatz eines Taschenrechners zur Überprüfung der Teilbarkeit meist unumgänglich.

Vorgehensweise

Das systematische Vorgehen bei der Primfaktorzerlegung lässt sich in folgenden Schritten beschreiben:

  1. Suche nach einem Primfaktor (einer Primzahl, welche die Ausgangszahl ohne Rest teilt). Man beginnt hierbei idealerweise bei der kleinsten Primzahl, der 2, und prüft die nächstgrößeren Primzahlen aufsteigend.
  2. Division der Zahl durch diesen gefundenen Primfaktor.
  3. Suche nach einem neuen Primfaktor für den berechneten Quotienten (die geteilte Zahl).
  4. Erneute Division durch den gefundenen Primfaktor.

Dieser Prozess wird so lange wiederholt, bis der verbleibende Quotient selbst eine Primzahl ist. Die Primfaktorzerlegung ergibt sich am Ende aus dem Produkt aller gefundenen Primfaktoren.

Bei der Suche nach einem Primfaktor genügt es, die Primzahlen bis zur Wurzel der Zahl zu prüfen: Hat eine Zahl überhaupt einen Teiler außer 1 und sich selbst, dann auch einen, der höchstens so groß ist wie ihre Wurzel.

Bedeutung für die Kryptologie

Zwei Primzahlen zu multiplizieren ist leicht, auch wenn sie hunderte Stellen haben. Die Umkehrung ist schwer: Für die Zerlegung einer großen Zahl in ihre Primfaktoren ist kein schnelles Verfahren bekannt. Das Probieren aller Primzahlen bis zur Wurzel dauert bei einer Zahl mit mehreren hundert Stellen länger, als das Universum alt ist, und auch die besten bekannten Verfahren brauchen dafür viel zu lange.

Diese Eigenschaft macht die Multiplikation zweier Primzahlen zu einer Einwegfunktion. Das RSA-Verfahren nutzt sie: Der RSA-Modul [math]\displaystyle{ N = p \cdot q }[/math] ist öffentlich, die beiden Primzahlen bleiben geheim. Wer [math]\displaystyle{ N }[/math] zerlegen kann, berechnet daraus den privaten Schlüssel (siehe Sicherheit des RSA-Verfahrens).

Beispiele

Beispiel: Primfaktorzerlegung der Zahl 12

Gesucht ist die Primfaktorzerlegung der Zahl 12. Wir gehen systematisch vor:

Primfaktor suchen

Wir beginnen die Suche nach einem geeigneten Teiler bei der kleinsten Primzahl, der 2. Wir prüfen: Ist 12 durch 2 teilbar?

  • Antwort: Ja.
  • Begründung: Gemäß den Teilbarkeitsregeln ist eine ganze Zahl durch 2 teilbar, wenn ihre letzte Ziffer durch 2 teilbar ist (hier die 2).

Zahl durch gefundenen Primfaktor teilen

Wir führen die Division durch:

[math]\displaystyle{ 12 : 2 = 6 }[/math]

Den ersten Primfaktor (die 2) haben wir somit gefunden. Da das Ergebnis 6 jedoch noch keine Primzahl ist, ist die Zerlegung noch nicht abgeschlossen.

Erneut Primfaktor suchen

Für die Zahl 6 beginnen wir die Suche nach einem Primfaktor wieder bei der kleinsten Primzahl, der 2. Wir prüfen: Ist 6 durch 2 teilbar?

  • Antwort: Ja.

Zahl erneut teilen

Wir führen die nächste Division durch:

[math]\displaystyle{ 6 : 2 = 3 }[/math]

Da es sich bei dem Ergebnis 3 um eine Primzahl handelt, ist die schrittweise Zerlegung nun erfolgreich abgeschlossen.

Ergebnis

Die Primfaktorzerlegung bildet sich aus dem Produkt aller identifizierten Primfaktoren:

[math]\displaystyle{ 12 = 2 \cdot 2 \cdot 3 }[/math]

RSA-Modul faktorisieren

Gesucht ist die Primfaktorzerlegung von [math]\displaystyle{ 133 }[/math].

  • 133 ist nicht durch 2 teilbar, denn die letzte Ziffer ist ungerade.
  • 133 ist nicht durch 3 teilbar, denn die Quersumme 7 ist nicht durch 3 teilbar.
  • 133 ist nicht durch 5 teilbar, denn die letzte Ziffer ist weder 0 noch 5.
  • 133 ist durch 7 teilbar: [math]\displaystyle{ 133 : 7 = 19 }[/math]

19 ist eine Primzahl, also ist [math]\displaystyle{ 133 = 7 \cdot 19 }[/math].