Programming Praxis

A collection of etudes, updated weekly, for the education and enjoyment of the savvy programmer

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.

Like this:

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
5 Comments »

5 Responses to “Pollard’s P-1 Factorization Algorithm”

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

2. Francois Saint-Jacques said
August 13, 2009 at 3:33 PM

a must be coprime to p, not any other number.

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

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

5. 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.

%d bloggers like this:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 29, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.923088788986206, "perplexity_flag": "middle"}