Pollard Rho算法的計劃代碼

我正試圖通過實施少數算法來學習計劃。Pollard Rho算法的計劃代碼

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

我想在方案中實現上述算法。任何幫助，將不勝感激。由於

來源

2015-04-23 leaner

好吧，我回答你的最後一個問題，因爲我很感興趣，但在一般情況下，只是要求人們編寫代碼對你來說是不能接受的在這裏。你試過什麼了？你有什麼特別的掙扎？ –

你不能從維基百科發佈僞代碼，並要求我們爲你實現它。 – Richard

我已經在Java和C＃中實現了這些算法。很好奇這些計劃如何運作。通過查看我知道的算法的實現，我學得很快。 – leaner

的實施球拍：

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

來源

2015-04-23 07:46:47 soegaard

Pollard Rho算法的計劃代碼

回答

相關問題