algorithm - Haskell 中的快速 Pollard Rho 分解

Question

我正在尝试实现 Pollard Rho Haskell 中的因式分解方法。这是我的目的

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

这个函数适用于像 8051 这样的小数字。但是当我试图找到大数的因子时，例如 1724114033281923457(我已经检查过，它与因子 11363592254 和 1229739323 合成)需要永远(在这种情况下函数将永远不会结束)。我究竟做错了什么？如果有任何帮助，我将不胜感激。

Answer 1

据我所知，当数字对于 Int 来说太大时，问题似乎可能是溢出 - 在这种情况下很可能在 x * x - 1 func 的一部分(Int 在我的系统上有一个 maxBound 为 9223372036854775807)

所以最简单的选择就是在任何地方都切换到 Integer，因为它们是无界的:

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

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

pollard_rho :: Integer -> Integer
...

这当然会使一切变慢