Haskell 中的快速 Pollard Rho 分解

Question

我正在尝试在 Haskell 中实施 Pollard Rho 分解方法。这是我的结果

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 来说太大时，问题似乎可能是溢出 - 在这种情况下，最有可能出现在 [=13] 的 x * x - 1 部分=]（Int 在我的系统上有一个 maxBound 9223372036854775807）

所以最简单的选择就是随处切换到 Integer，因为它们是无界的：

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

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

pollard_rho :: Integer -> Integer
...

这当然会使一切变慢

Haskell 中的快速 Pollard Rho 分解

Fast Pollard Rho factorization in Haskell

algorithm

haskell

math

prime-factoring