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)])))