Faktorisierungsproblem
Faktorisierungsprobleme sind in der Mathematik eine Klasse von Problemen, die sich mit dem Fehlen effizienter Algorithmen zur Primfaktorzerlegung einer natürlichen Zahl größer 1 befassen.
Für relativ kleine Zahlen ist eine solche Zerlegung durch Probedivision möglich. Die Komplexität des Problems wächst jedoch mit der Größe der Zahlen. Ist die zusammengesetzte Zahl n das Produkt zweier Primfaktoren gleicher Größenordnung (d.h. beide Primfaktoren liegen in der Nähe von 
), dann muss das Probierverfahren alle Kandidaten bis fast zu ausprobieren. Wird die zu untersuchende Zahl um nur 4 Dezimalstellen größer, benötigt dieses Verfahren die 100fache Zeit.
Faktorisierungsprobleme werden in der Kryptologie ausgenutzt, speziell in RSA- und Rabin-Kryptosystemen.
Bisher bekannte Faktorisierungsverfahren haben zwar ein deutlich besseres Zeitverhalten als das reine Probierverfahren. Für die Zerlegung von in der Kryptologie verwendeten großen Zahlen (über 600 Dezimalstellen) würden diese Verfahren jedoch Jahrhunderte brauchen. Ob es schnellere Verfahren gibt, ist nicht bekannt, aber auch nicht auszuschließen.