Pollard’s P-1 Factorization Algorithm

July 21, 2009

Fermat’s little theorem states that for any prime number $p$ , and any other number $a$ , $a^{p-1} \equiv 1 \pmod{p}$ . Rearranging terms, we have $a^{p-1} - 1 \equiv 0 \pmod{p}$ , which means that $p$ divides the left-hand side of the equation, thus $p$ is a factor of the left-hand side.

John Pollard used this idea to develop a factoring method in 1974. His idea is to choose a very large number and see if it has any factors in common with $a^{p-1} - 1$ , thus giving a factor of $p$ . A systematic way to test many very large numbers is by taking large factorials, which have many small factors within them. Thus, Pollard’s $p-1$ factorization algorithm is this:

1) Choose $b$ , which is known as the smoothness bound, and calculate the product of the primes to $b$ by $k = \mathrm{lcm}(1,2,3,\ldots,b)$ .

2) Choose a random integer $a$ such that $1 < a < n$ .

3) Calculate $g=\gcd(a,n)$ . If $g$ is strictly greater than 1, then it is a non-trivial factor of $n$ . Otherwise, continue to the next step.

4) Calculate $d = \gcd(a^k - 1, n)$ . If $1 < d < n$ , then $d$ is a non-trivial factor of $n$ . If $d=1$ , go to Step 1 and choose a larger $b$ . If $d=n$ , go back to Step 2 and choose another $a$ .

In Step 4, you can quit with failure instead of returning to Step 1 if $b$ becomes too large, where “too large” is probably somewhere around $10^6$ ; in that case, you will need to continue with some other factoring algorithm.

Your task is to write a function that factors integers by Pollard’s $p-1$ method. What are the factors of $2^{98}-1$ ? When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

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