Die
Primfaktorzerlegung ist die Darstellung einer
natürlichen Zahl als
Produkt aus
Primzahlen, die dann als
Primfaktoren von
bezeichnet werden. Diese Darstellung ist (bis auf die Reihenfolge der Faktoren) eindeutig und zählt zu den grundlegenden und klassischen Werkzeugen der
Zahlentheorie. Sie ist Gegenstand des Fundamentalsatzes der Arithmetik. Es ist bisher kein
effizientes Faktorisierungsverfahren bekannt, um die Primfaktorzerlegung einer beliebigen Zahl zu erhalten.