Primfaktorzerlegung

Aus ProgrammingWiki

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:

(define primzahl? (lambda (n) (letrec ([prim? (lambda (n t) (cond [(> t (sqrt n)) #t] [(= (modulo n t) 0) #f] [else (prim? n (+ t 2))]))]) (cond [(= n 2) #t] [(or (< n 2) (= (modulo n 2) 0)) #f] [else (prim? n 3)]))))

(primzahl? (- (expt 2 31) 1))

ausführen

Algorithmus zur Primfaktorzerlegung

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

(define primfaktoren (lambda (z) (letrec ([zerlegung (lambda (z p) (cond [(< z 2) #f] [(primzahl? z) (list z)] [(= (modulo z 2) 0) (cons 2 (zerlegung (/ z 2) p))] [(primzahl? p) (if (= (modulo z p) 0) (cons p (zerlegung (/ z p) p)) (zerlegung z (+ p 2)))] [else (zerlegung z (+ p 2))]))]) (zerlegung z 3))))

(primfaktoren 156788717)

ausführen

Zurück zum Algorithmusbegriff.