Verteilt Faktorisieren

Basierend auf den Funktionen für das Faktorisieren mit elliptischen Kurven kann ein Programm entwickelt werden, das die Aufgabe über mehrere Rechner verteilt.

Dazu ergänzt man die Funktion remote-search-factor. Diese führt die Suche nach einem Faktor auf einem entfernten Rechner aus.

(defproc remote-search-factor (place product)
  (at place (elliptic-curve-search-factor product)))

Die Funktion distributed-find-factor ermittelt einen Faktor, in dem sie auf jedem bekannten entfernten Rechner (und auch lokal) wiederholt eine Suche startet, bis ein Faktor gefunden wurde.

(defproc distributed-find-factor (product)
  (let
    ((channel (make-channel 1)))
    (progn
      (dolist (place (cons nil (get-places)))
        (go
          (loop
            (when (closed-channel? channel)
              (return nil))
            (awhen
              (remote-search-factor place product)
              (send-on-channel channel it nil)
              (return nil)))))
      (ensure
        (receive-from-channels (list channel) nil)
        (close-channel channel)))))

Schließlich wird die Funktion factorize so abgeändert, dass sie distributed-find-factor aufruft.

(defproc factorize (number)
  (if
    (less? number 2)
    nil
    (if
      (prime? number)
      (list number)
      (aif
        (trial-division-search-factors number)
        (append it (factorize (/ number (apply * it))))
        (let
          ((factor (distributed-find-factor number)))
          (append
            (factorize factor)
            (factorize (/ number factor))))))))


distributed-factorization.sheet.xml