Algorithme Rho de Pollard en Ruby

L'algorithme Rho de Pollard permet de décomposer un entier en son produit de facteurs premiers. Cet algorithme se base sur une fonction dite aléatoire f, permettant d'obtenir une suite cyclique :

xi+1 = f(xi) % n

avec n l'entier à décomposer.

Attention, si :

pgcd(|xi - x2i|, n)

prend n pour valeur, l'algorithme produit une boucle infinie (il faudrait (y a qu'à...) alors changer la fonction f ou aller se faire cuire un steak de soja) : dans mon code, je lève une erreur, en l'occurrence.
Sinon, beaucoup de récursion...

Code prime.rb :
(Ruby 1.8.6 : $ prime.rb [integer])

def pgcd m, n
(n==0)? m : pgcd(n, m%n)
end

def f x, n
(x**2 + 1) % n
end

def x i, n
(i==0)? 2 : f(x(i-1,n), n)

end

class Integer
def is_prime?
    res = true
    if self < 2 then
        res = false
    else
        for i in 2..Math.sqrt(self).to_i
            if i.is_prime? and (self%i == 0) then
                res = false
            end

        end
    end
    res
end
end

def pollard n
r = []

if n.is_prime?
    r.push n
elsif n != 1
    i, p = 0, 1
    while p == 1
        i += 1
        p = pgcd((x(i,n)-x(2*i,n)).abs, n)
    end

    raise "Pollard Algorithm: Cycle FAIL" if p==n

    if p.is_prime? then
        r.push p
    else
        r.push pollard(p)
    end

    r.push pollard(n/p)
end
r.flatten!
r
end

input = ARGV[0].to_i
pollard(input).each {|x| puts x}