Pollard 的 Rho 算法的方案代码

Question

我正在尝试通过实现一些算法来学习方案。

Pollards-Rho(n)
 g(x) = x2 + 1 mod n
    x ← 2; y ← 2; d ← 1;
    While d = 1:
        x ← g(x)
        y ← g(g(y))
        d ← gcd(|x - y|, n)
    If d = n, return failure.
    Else, return d

我正在尝试在方案中实现上述算法。任何帮助，将不胜感激。谢谢

Answer 1

Racket 中的实现：

;;; ALGORITHM 19.8  Pollard's rho method
; INPUT   n>=3 neither a prime nor a perfect power
; OUTPUT  Either a proper divisor of n or #f
(: pollard : Natural -> (U Natural False))
(define (pollard n)
  (let ([x0 (random-natural n)])
    (do ([xi x0 (remainder (+ (* xi xi) 1) n)]
         [yi x0 (remainder (+ (sqr (+ (* yi yi) 1)) 1) n)]
         [i  0  (add1 i)]
         [g  1  (gcd (- xi yi) n)])
      [(or (< 1 g n) (> i (sqrt n)))
       (if (< 1 g n)
           (cast g natural?)
           #f)])))

Pollard 的 Rho 算法的方案代码

Scheme code for Pollard's Rho algorithm

scheme