Faktorisierung (auch Faktorisierung und Factoring genannt) ist das Zerlegen einer zusammengesetzten Zahl in Zahlen, die sich miteinander multiplizieren, um die ursprüngliche Zahl zu erhalten. Diese kleineren Zahlen werden als Faktoren oder Divisoren bezeichnet. 1 ist ein Faktor aller Zahlen.
Unter Primfaktorzerlegung versteht man das Aufbrechen einer zusammengesetzten Zahl in Primzahlen, die multipliziert werden können, um die größere Zahl zu erhalten. Da 1 keine Primzahl ist, wird sie nicht in die Primfaktorzerlegung einbezogen.
Zum Beispiel kann 12 als 4 × 3 faktorisiert werden. Da 4 keine Primzahl ist, ist das nicht ihre Primfaktorzerlegung. Die Primfaktorzerlegung von 12 ist in der Tat 3 × 2 × 2.
Die Zahlen, die sich aus der Faktorisierung ergeben, sind in der Regel geordnet, z.B. beginnend mit der kleinsten Zahl. Zum Beispiel 72=2^3*3^2. Die Faktorisierung jeder Zahl ist einzigartig. Dies verallgemeinert sich zu:
- Jede Zahl hat eine einzigartige Primfaktorzerlegung
- Jede Primfaktorzerlegung entspricht einer eindeutigen Zahl
Da es bei großen Zahlen sehr schwierig ist, die miteinander zu multiplizierenden Zahlen zu finden, kann diese Tatsache in der Kryptographie genutzt werden.
