Primfaktorzerlegung

Aus ProgrammingWiki

< Grundlagen der funktionsorientierten Programmierung mit SCHEME

Archivierte Version vom 2014-07-12T08:23:54+00:00. Aktuelle Version

Autor: Kocksch, Corinna

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 Primfaktorenzerlegung 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))

Algorithmus zur Primfaktorzerlegung

(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)

Zurück zum Algorithmusbegriff.

Primfaktorzerlegung

Primzahlprüfer

Algorithmus zur Primfaktorzerlegung

Suche