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)
(catch-and-apply
(quote io-error)
(lambda (name value)
(if
(member? place (get-places))
(sleep 30)
(throw name value)))
(at place (elliptic-curve-search-factor product))))
Die Funktion remote-thread-count ermittelt, wieviele Threads auf einem entfernten Rechner zur Verfügung stehen.
(defproc remote-thread-count (place)
(catch-and-apply
(quote io-error)
(lambda (name value) 0)
(max 1 (- (at place *thread-count*) 1))))
Die Funktion remote-find-factor ermittelt einen Faktor, in dem sie auf einem entfernten Rechner wiederholt eine Suche startet, bis ein Faktor gefunden wurde. Zurückgemeldete Ergebnisse werden mit dem Prädikat non-trivial-divisor? darauf geprüft, ob sie tatsächlich ein Faktor sind.
(defproc non-trivial-divisor? (factor product)
(and
(integer? factor)
(greater? factor 1)
(less? factor product)
(integer? (/ product factor))))
(defproc remote-find-factor (place product channel)
(dotimes (index (remote-thread-count place))
(go
(loop
(when (closed-channel? channel)
(return nil))
(awhen
(remote-search-factor place product)
(when
(non-trivial-divisor? it product)
(send-on-channel channel it nil))
(return nil))))))
Die Funktion distributed-find-factor ruft remote-find-factor für jeden bekannten entfernten Rechner (und auch lokal) auf und wartet, bis ein Faktor gefunden wurde.
(defproc distributed-find-factor (product)
(let
((channel (make-channel 1)))
(ensure
(dolist (place (cons nil (get-places)) (receive-from-channels (list channel) nil))
(remote-find-factor place product channel))
(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))))))))
Damit ist es möglich, das Resultat von (+ (expt 3 126) (expt 4 126)), die Zahl 7237005577332263523993695200663346632037469754104609216711831475588027168825 in die Faktoren (5 5 29 73 193 7057 12601 28729 95257 196201 376853 29110508281 20417342465521 66248492183974801) zu zerlegen.
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)
(catch-and-apply
(quote io-error)
(lambda (name value)
(if
(member? place (get-places))
(sleep 30)
(throw name value)))
(at place (elliptic-curve-search-factor product))))
Die Funktion remote-thread-count ermittelt, wieviele Threads auf einem entfernten Rechner zur Verfügung stehen.
(defproc remote-thread-count (place)
(catch-and-apply
(quote io-error)
(lambda (name value) 0)
(max 1 (- (at place *thread-count*) 1))))
Die Funktion remote-find-factor ermittelt einen Faktor, in dem sie auf einem entfernten Rechner wiederholt eine Suche startet, bis ein Faktor gefunden wurde. Zurückgemeldete Ergebnisse werden mit dem Prädikat non-trivial-divisor? darauf geprüft, ob sie tatsächlich ein Faktor sind.
(defproc non-trivial-divisor? (factor product)
(and
(integer? factor)
(greater? factor 1)
(less? factor product)
(integer? (/ product factor))))
(defproc remote-find-factor (place product channel)
(dotimes (index (remote-thread-count place))
(go
(loop
(when (closed-channel? channel)
(return nil))
(awhen
(remote-search-factor place product)
(when
(non-trivial-divisor? it product)
(send-on-channel channel it nil))
(return nil))))))
Die Funktion distributed-find-factor ruft remote-find-factor für jeden bekannten entfernten Rechner (und auch lokal) auf und wartet, bis ein Faktor gefunden wurde.
(defproc distributed-find-factor (product)
(let
((channel (make-channel 1)))
(ensure
(dolist (place (cons nil (get-places)) (receive-from-channels (list channel) nil))
(remote-find-factor place product channel))
(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))))))))
Damit ist es möglich, das Resultat von (+ (expt 3 126) (expt 4 126)), die Zahl 7237005577332263523993695200663346632037469754104609216711831475588027168825 in die Faktoren (5 5 29 73 193 7057 12601 28729 95257 196201 376853 29110508281 20417342465521 66248492183974801) zu zerlegen.