## pollard rho algorithm

in lua

### Source Code

-- Pollard's Rho Integer Factorization algorithm implementation
-- See: http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm

-- Returns the greatest common divisor of a and b
local function gcd(a, b)
if a == 0 then return b
elseif b == 0 then return a
end
if a == b then return a end
return a > b and gcd(a - b, b) or gcd(a, b - a)
end

-- n       : an integer number to be factored
-- f       : a factorization function
-- returns : a non trivial factor or n, or nil if failure.
return function (n, f)
local x, y, d = 2, 2, 1
while d == 1 do
x = f(x)
y = f(f(y))
d = gcd(math.abs(x - y), n)
end
return d ~= n and d
end
-- Tests for pollard_rho.lua
local rho = require 'pollard_rho'

local total, pass = 0, 0

local function dec(str, len)
return #str < len
and str .. (('.'):rep(len-#str))
or str:sub(1,len)
end

local function run(message, f)
total = total + 1
local ok, err = pcall(f)
if ok then pass = pass + 1 end
local status = ok and 'PASSED' or 'FAILED'
print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

run('Pollard\'s rho factorization', function()
local n = 8051
local function f(x) return (x^2+1)%n end
assert(rho(n, f) == 97)
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
:format(total, pass, total-pass, (pass*100/total)))