pollard rho algorithm


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Tags

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