## Extending Pollard’s P-1 Factorization Algorithm

### March 19, 2010

We studied John Pollard’s *p*-1 factorization algorithm in a previous exercise. You may recall that the algorithm finds factors of a number *n* by calculating the least common multiple of the integers up to some bound *B*, call it *k*, then calculates the greatest common divisor of 2^{k}-1 and *n*; if the greatest common divisor is between 1 and *n*, it is a factor of *n*.

What is happening mathematically is that we are trying to find a factor *p*|*n* (that’s “*p* divides *n*“, meaning that *p* is a factor of *n*, for those not familiar with the mathematical notation), for which we know the factorization of *p*-1. Consider the number 15770708441 = 135979 × 115979. If we apply Pollard’s *p*-1 algorithm with a bound of 150, no factors are found, but if we apply Pollard’s *p*-1 algorithm with a bound of 180 the 135979 factor is found, because 135979 – 1 = 2 × 3 × 131 × 173; increasing the bound to include the factor 173 makes Pollard’s *p*-1 algorithm work. The 135979 factor is found first because 115979 – 1 = 2 × 103 × 563, and 563 is out-of-bounds.

An alternative to increasing the bound is to call a second stage that looks for a *p*-1 for which all factors are less than the first-stage bound except one factor that is between the first-stage bound and the second-stage bound. That is, instead of calculating lcm(1..180), we calculate lcm(1..150) × *j*, where *j* ranges from 151 to 180. For small numbers like 150 and 180, the difference doesn’t matter, but for larger numbers like *B*_{1} = 10^{6} and *B*_{2} = 10^{9}, the difference in the computational cost is noticeable.

Your task is to write a two-stage version of Pollard’s *p*-1 algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

[…] 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 […]