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.

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Twitter account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s

Programming Praxis