Pollards algorithm can be used to factor huge numbers.

Pollards algorithm can be used to factor huge numbers.

Date Created:Friday October 03rd, 2008 05:51 PM

Date Modified:Tuesday January 19th, 2010 10:36 PM

You essentially begin with a starting number, and then have a z and an x... apply the function twice to z, and once to x. Eventually, they will hit a loop and you can take the greatest common divisor of the difference between the values and the number you are trying to factor.

(define (euclid a b) (if (= b 0) a (euclid b (modulo a b) ) )) (define (pollards n y z fn) (let ( (n-y (fn y)) (n-z (fn (fn z))) ) (let ( (g (gcd (abs (- n-y n-z)) n)) ) (if (= g 1) (pollards n n-y n-z fn) g ) ) ) ) ;; THIS FUNCTION WILL LOOP FOREVER IF IT DOES NOT FIND A FACTOR

Downloads:

Download: pollards.scm 466 B

Please login or Click Here to register for downloads

Pollards Algorithm by Dan Lynch

is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License

Based on a work at www.3daet.com

Permissions beyond the scope of this license may be available at http://www.3daet.com