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.
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With