Primfaktorzerlegung

Aus ProgrammingWiki

< Grundlagen der funktionsorientierten Programmierung mit SCHEME

Archivierte Version vom 2014-07-14T05:56:22+00:00. Aktuelle Version

Autorin: 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 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))

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 (quotient z 2) p))]
              [(primzahl? p)
               (if (= (modulo z p) 0) 
                   (cons p (zerlegung (quotient 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