Schnelle Pollard-Rho-Faktorisierung in Haskell

Question

Ich versuche, Pollard Rho Faktorisierungsmethode in Haskell zu implementieren. Hier ist, was ich zu

kam

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 

Diese Funktion, wenn fein für kleine Zahlen wie 8051. Aber wenn ich versuche Faktoren für eine große Zahl zu finden, zum Beispiel 1724114033281923457 (I geprüft habe, ist es Verbund mit Faktoren 11363592254 und 1229739323) es dauert ewig (in diesem Fall endet die Funktion nie). Was mache ich falsch? Ich wäre sehr dankbar für jede Hilfe.

Answer 1

soweit ich das Problem sagen kann, scheint möglich zu sein, überläuft erhalten Sie, wenn die Zahlen für Int zu groß werden - in diesem Fall höchstwahrscheinlich im x * x - 1 Teil func (Int ein maxBound von 9223372036854775807 auf meinem System haben)

so ist die einfachste Möglichkeit, nur um Integer überall zu wechseln, wie sie unbegrenzt sind:

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

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

pollard_rho :: Integer -> Integer 
... 

dies natürlich alles etwas langsamer, obwohl

machen