Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Fast Pollard Rho factorization in Haskell

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.

like image 699
ponkin Avatar asked Jun 01 '16 05:06

ponkin


1 Answers

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

like image 155
Random Dev Avatar answered Nov 15 '22 05:11

Random Dev