Quick factorization of Pollard Roe in Haskell

Question

I am trying to implement the Polla Rho factorization method in Haskell . That's what I came in

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

This function is great for small numbers, such as 8051. But when I try to find factors for large numbers, for example, 1724114033281923457 (I checked, it is composed with factors 11363592254 and 1229739323), it takes forever (in this case the function will never end) . What am I doing wrong? I would really appreciate any help.

Answer 1

as far as I can judge that the problem seems to be possible overflows when the numbers get too big for Int - in this case, most likely in the x * x - 1 func ( Int is maxBound from 9223372036854775807 in my system)

So, the easiest option is to simply switch to Integer everywhere, as they are not limited:

 func :: Integer -> Integer -> Integer ... pollardStep :: Integer -> Integer -> Integer -> Integer -> Integer -> Integer ... pollard_rho :: Integer -> Integer ... 

this of course will make things a little slower though