Pollard’s P-1 Factorization Algorithm

July 21, 2009

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

Filed in Exercises

5 Comments »

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

veer said
July 23, 2009 at 5:54 AM
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.
Francois Saint-Jacques said
August 13, 2009 at 3:33 PM
a must be coprime to p, not any other number.
Pollard’s P-1 Factorization Algorithm, Revisited « Programming Praxis said
September 16, 2011 at 9:00 AM
[…] 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 […]

Matías Giovannini said

September 24, 2011 at 10:56 PM

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.

programmingpraxis said
September 25, 2011 at 12:08 AM
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.

Programming Praxis