Primfaktorzerlegung

Aus ProgrammingWiki

Wechseln zu: Navigation, Suche

Autorin: Corinna Kocksch (2014)

Es gibt nach wie vor intensive Bemühungen, große natürliche Zahlen effizient in ihre Primfaktoren zu zerlegen (vgl. auch Verschlüsselung von Daten mit dem RSA-Verfahren). Nachfolgend soll ein Algorithmus vorgestellt werden, der bereits recht effizient diese Primfaktorzerlegung vornimmt.

Primzahlprüfer

Zur Konstruktion eines Primzahlfilters haben wir bereits ein Prädikat kennen gelernt, das eine effiziente Primzahlprüfung zulässt:

Algorithmus zur Primfaktorzerlegung

Damit lässt sich nun auch eine effiziente Primfaktorzerlegung realisieren:

Zurück zum Algorithmusbegriff.

Persönliche Werkzeuge