pollard_rho_factorization.sf

#!/usr/bin/ruby

# Pollard's rho integer factorization algorithm.

# See also:
#   https://facthacks.cr.yp.to/rho.html
#   https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm

func rho_factor(n, tries = 50000) {

    func f(x) {      # can be any polynomial
        powmod(x, 2, n) + 1
    }

    var x = f(1)
    var y = f(x)

    tries.times {

        x = f(x)
        y = f(f(y))

        is_coprime(n, x-y) || break
    }

    return gcd(x-y, n)
}

say rho_factor(503*863)                   #=> 863
say rho_factor(33670570905491953)         #=> 36169843
say rho_factor(314159265358979323)        #=> 317213509
say rho_factor(242363923520394591022973)  #=> 786757556719