Fast Pollard Rho factorization in Haskell

Question

I am trying to implement Pollard Rho factorization method in Haskell. Here is what I came to

func :: Int -> Int -> Int
func x n = mod ( x * x - 1) n

pollardStep :: Int -> Int -> Int -> Int -> Int -> Int
pollardStep i k n x y
      | d /= 1 && d /= n = d
      | i == k = pollardStep (i+1) (2*k) n x1 x1
      | otherwise = pollardStep (i+1) k n x1 y
      where d = gcd n $ abs $ y - x
            x1 = func x n

pollard_rho :: Int -> Int
pollard_rho n = pollardStep 1 2 n 2 2

This function if fine for small numbers like 8051. But when I try to find factors for large numbers, for example, 1724114033281923457(I have checked, it is composite with factors 11363592254 and 1229739323) it takes forever(in that case function will never ends). What am I doing wrong? I would be very appreciate to any help.

Answer 1

as far as I can tell the problem seems to be possible overflows you get when the numbers get too big for Int - in this case most likely in the x * x - 1 part of func (Int has a maxBound of 9223372036854775807 on my system)

So the easiest option is just to switch to Integer everywhere as those are unbounded:

func :: Integer -> Integer -> Integer
...

pollardStep :: Integer -> Integer -> Integer -> Integer -> Integer -> Integer 
...

pollard_rho :: Integer -> Integer
...

this of course will make everything a bit slower though