Primfaktorzerlegung

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.