Programming Praxis


Home | Pages | Archives


Pollard’s P-1 Factorization Algorithm

July 21, 2009 9:00 AM

Our function is a straight forward statement of the algorithm:

(define (factor n)
  (let loop1 ((b 7) (k 420))
    (let loop2 ((a (randint 2 n)))
      (let ((g (gcd a n)))
        (if (< 1 g) g
          (let ((d (gcd (- (expm a k n) 1) n)))
            (cond ((= d 1)
                    (let ((b (+ b 1)))
                      (loop1 b (lcm k b))))
                  ((= d n) (loop2 (randint 2 n)))
                  (else d))))))))

Factor assumes that its argument is composite, and may return a composite. The factors function, stolen from an earlier exercise, finds all the factors of a number:

(define (factors n)
  (sort < (let fact ((n n) (fs '()))
    (cond ((= n 1) fs)
          ((even? n) (fact (/ n 2) (cons 2 fs)))
          ((prime? n) (cons n fs))
          (else (let ((f (factor n)))
                  (append fs (fact f '()) (fact (/ n f) '()))))))))

The factors of 2^{98}-1 are:

> (factors (- (expt 2 98) 1))
(3 43 127 4363953127297 4432676798593)

We use rand, randint, expm, and sort from the Standard Prelude, and prime? is adapted from the exercise on primality checking using the Miller/Rabin algorithm. You can run the program at http://programmingpraxis.codepad.org/dx55xB8V.

Posted by programmingpraxis

Categories: Exercises

Tags:

5 Responses to “Pollard’s P-1 Factorization Algorithm”

  1. I wrote a prolog implementation ,which works now and then :), but not
    always,most of the time it says ‘out of local stack’.
    So i saved the result, factors are [4432676798593, 4363953127297, 127, 43, 3].
    I would love to see the prolog code for the above problem.

    By veer on July 23, 2009 at 5:54 AM

  2. a must be coprime to p, not any other number.

    By Francois Saint-Jacques on August 13, 2009 at 3:33 PM

  3. […] have studied John Pollard’s p−1 algorithm for integer factorization on two previous occasions, giving first the basic single-stage algorithm and later adding a second stage. In […]

    By Pollard’s P-1 Factorization Algorithm, Revisited « Programming Praxis on September 16, 2011 at 9:00 AM

  4. all_factors repeatedly applies a factorizing method factor to n:

    let all_factors factor n =
      let open Big_int in
      let rec go l n =
        if le_big_int n unit_big_int then l else
        if is_even_big_int n then go (two_big_int :: l) (shift_right_big_int n 1) else
        if is_prime n then (n :: l) else
        let f = factor n in
        go (go l f) (div_big_int n f)
      in List.sort compare_big_int (go [] n)
    

    Besides modexp_big_int and random_big_int, I need to compute lcms, in this case optimized by knowing that the first factor is always small:

    let lcm_int_big_int p q =
      let open Big_int in
      let d = gcd p (int_of_big_int (mod_big_int q (big_int_of_int p))) in
      mult_int_big_int (p / d) q
    

    Finally, Pollard’s p-1:

    let pollard_pm1 =
      let open Big_int in
      let rec go b k n =
        let a = add_int_big_int 2 (random_big_int (add_int_big_int (-2) n)) in
        let g = gcd_big_int a n in
        if gt_big_int g unit_big_int then g else
        let d = gcd_big_int (pred_big_int (modexp_big_int a k n)) n in
        if eq_big_int d n then go b k n else
        if eq_big_int d unit_big_int then
          let b = succ b in
          if b > 1_000_000 then failwith "pollard_pm1" else
          go b (lcm_int_big_int b k) n
        else d
      in
      let b = 7 in
      let k = List.fold_right lcm_int_big_int (range 2 b)
        (List.fold_right mult_int_big_int (primes b) unit_big_int) in
      all_factors (go b k)
    

    This method seems to be much, much slower than Pollard’s Rho.

    By Matías Giovannini on September 24, 2011 at 10:56 PM

  5. It shouldn’t be much, much slower than Pollard’s rho. The two methods are complementary. The rho method is generally used to find small factors, say from 4 to 12 digits, after trial division has found factors up to 3 digits. The p-1 method is generally used after the rho method has run for a while, in the hope that you get lucky and find a large factor, say 15 to 20 digits or sometimes more.

    It’s been a while since I programmed in the ML family of languages, so I’ll ask some questions instead of making some statements.

    1) I see only one bound b. If you look at the more recent p-1 exercise that uses the improved standard continuation, you’ll see a much faster version of the algorithm that uses two bounds b1 and b2.

    2) In the pollard_pm1 function, the line let k = …, do you recompute the lcm at each b?

    3) I don’t understand the List.fold_right in the line after that. You seem to be taking the product of all the primes less than b, but I’m not sure why.

    By programmingpraxis on September 25, 2011 at 12:08 AM

Leave a Reply



Mobile Site | Full Site


Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.