## Extending Pollard’s P-1 Factorization Algorithm

### March 19, 2010

We begin by restating the one-stage algorithm, in a somewhat different form than it appeared in the previous exercise:

`(define (pollard1 n b1)`

(let stage1 ((a 2) (i 2))

(if (< i b1)

(stage1 (expm a i n) (+ i 1))

(let ((d (gcd (- a 1) n)))

(if (< 1 d n) d #f)))))

The two-stage algorithm starts the same, but the continuation loops over the integers from *B*_{1} to *B*_{2}, making the same computation as the first stage:

`(define (pollard2 n b1 b2)`

(let stage1 ((a 2) (i 2))

(if (< i b1)

(stage1 (expm a i n) (+ i 1))

(let ((d (gcd (- a 1) n)))

(if (< 1 d n) (list 'stage1 d)

(let stage2 ((j b1))

(if (= j b2) #f

(let ((d (gcd (- (expm a j n) 1) n)))

(if (< 1 d n) (list 'stage2 d)

(stage2 (+ j 1)))))))))))

We can see how this works using the sample problem given above:

`> (pollard1 15770708441 150)`

#f

> (pollard1 15770708441 180)

135979

> (pollard2 15770708441 150 180)

(stage2 135979)

We use expm from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/VpaXvPEN.

Pages: 1 2

[…] Praxis – Extending Pollard’s P-1 Factorization Algorithm By Remco Niemeijer In today’s Programming Praxis exercise we need to write an improved version of a factorization algorithm. I […]

My Haskell solution (see http://bonsaicode.wordpress.com/2010/03/19/programming-praxis-extending-pollard%E2%80%99s-p-1-factorization-algorithm/ for a version with comments):

[…] 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 today’s […]