Fast Pollard Rho factorization w Haskell

Question

Próbuję wdrożyć metodę faktoryzacji Pollard Rho w Haskell. Oto co mi przyszło do

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 

tę funkcję, jeśli dobrze dla małych ilościach jak 8051. Ale gdy próbuję znaleźć czynniki dużych liczb, na przykład, 1724114033281923457 (mam zaznaczone, to kompozyt z czynnikami 11363592254 i 1229739323) trwa to wiecznie (w tym przypadku funkcja nigdy się nie zakończy). Co robię źle? Byłbym bardzo wdzięczny za każdą pomoc.

Answer 1

miarę mogę powiedzieć, problem wydaje się być możliwe przepełnienia można uzyskać, gdy numery zbyt duży dla Int - w tym przypadku najprawdopodobniej w x * x - 1 części func (Int ma maxBound z 9223372036854775807 w moim systemie)

więc najprostszym rozwiązaniem jest po prostu przełączyć się Integer wszędzie jak te są nieograniczone:

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

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

pollard_rho :: Integer -> Integer 
... 

to oczywiście uczyni wszystko nieco wolniej chociaż