Primfaktorzerlegung - (engl.) factorisation, factoring
Jede ganze Zahl ist entweder eine Primzahl oder das Produkt mehrerer Primzahlen. Die Bestimmung der Primzahlen, durch deren Multiplikation sich eine ganze Zahl ergibt, heißt Primfaktorzerlegung. Die Primfaktorzerlegung wird auch als Faktorisierung bezeichnet.
Die ersten neun Primzahlen heißen 1, 2, 3, 5, 7, 11, 13, 17, 19.
Die Primfaktorzerlegung der Zahl 60 ergibt folgende Primfaktoren:
60 = 6 * 10 = 2 * 3 * 2 * 5 = 2 * 2 * 3 * 5
Da 2, 3 und 5 Primzahlen sind, wurde 60 faktorisiert.
Das schnellste, bekannte Verfahren zur Faktorisierung von Zahlen mit mehr als 110 Dezimalstellen ist das Zahlkörpersieb (Number Field Sieve, NFS). Für zahlen mit weniger als 110 Dezimalstellen ist das Quadratische Sieb (Quadratic Sieve, QS) schneller.
Das klassische Verfahren ist die versuchsweise Division. Dabei wird für jede Primzahl, die kleiner oder gleich der Quadratwurzel der zu faktorisierenden Zahl ist getestet, ob sie Teiler der Zahl ist.
Siehe auch: Faktorisierungsproblem, Sieb des Erathosthenes