## 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 B1 to B2, 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

### 4 Responses to “Extending Pollard’s P-1 Factorization Algorithm”

1. [...] 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 [...]

2. Remco Niemeijer said

```import Data.Bits
import Data.List

expm :: Integer -> Integer -> Integer -> Integer
expm b e m = foldl' (\r (b', _) -> mod (r * b') m) 1 .
filter (flip testBit 0 . snd) .
zip (iterate (flip mod m . (^ 2)) b) .
takeWhile (> 0) \$ iterate (`shiftR` 1) e

pollard :: (Integer -> t) -> (Integer -> t) -> Integer -> Integer -> t
pollard found notFound n b1 = f 2 2 where
f a i | i < b1         = f (expm a i n) (i + 1)
| 1 < d && d < n = found d
| otherwise      = notFound a
where d = gcd (a - 1) n

pollard1 :: Integer -> Integer -> Maybe Integer
pollard1 = pollard Just (const Nothing)

pollard2 :: Integer -> Integer -> Integer -> Maybe (String, Integer)
pollard2 n b1 b2 = pollard (Just . ((,) "stage1")) (f b1) n b1 where
f j a | j == b2        = Nothing
| 1 < d && d < n = Just ("stage2", d)
| otherwise      = f (j + 1) a
where d = gcd (expm a j n - 1) n
```
3. Nice Blog… Going to go through one post a time and read this whole website like it was designed for a magazine.

4. [...] 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 [...]