Natürliche Zahlen sind entweder prim oder das Produkt mehrerer Primfaktoren. Faktorisierung, auch Primfaktorzerlegung, bezeichnet das Herausfinden der Primfaktoren einer natürlichen Zahl.
Beispiele
Die Zahl 6 hat die beiden Primfaktoren 2 und 3 (2·3=6 und 2, 3 prim), die Zahl 30 die Primfaktoren 2, 3 und 5.
Verfahren zur Faktorisierung
Die Methode zur Faktorisierung kleinerer Zahlen ist die versuchsweise Division durch Primzahlen kleiner oder gleich der Quadratwurzel der zu prüfenden Zahl. Dieses Verfahren scheitert jedoch am exponentiell steigenden Aufwand für große Zahlen.
Zur Faktorisierung größerer Zahlen gibt es etliche Methoden. Am gebräuchlichsten sind die Methode der Eliptischen Kurven, das Quadratische Sieb und das Zahlkörpersieb. Diese Verfahren haben einen subexponentiell steigenden Aufwand.
Die Tatsache, dass die Faktorisierung extrem großer Zahlen mit heutigen Mitteln nahezu unmöglich ist, wird in der Kryptologie genutzt.