eharetea

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
            

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