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 2k-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 B1 = 106 and B2 = 109, 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.
Pages: 1 2
[...] 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):
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) nNice Blog… Going to go through one post a time and read this whole website like it was designed for a magazine.
[...] 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 [...]