Fast simple integer Factorizer

factorizer.ex

defmodule Factorizer do

  def factorize(n) do
    t = System.system_time

    x = pollard(n, 2_000_000, 2_000_000)
    y = div(n, x)
    p = min(x, y)
    q = max(x, y)

    t = System.system_time - t

    IO.puts "
Factorized #{n}: into [#{p} , #{q}] in #{t} μs
"

    {p, q}
  end

  defp gcd(a,0), do: a
  defp gcd(a,b), do: gcd(b,rem(a,b))

  defp pollard(n, a, b) do
    a = f0(a, n)
    b = f0(f0(b, n), n)

    p = gcd(abs(b - a), n)

    case p > 1 do
      true  -> p
      false -> pollard(n, a, b)
    end
  end

  defp f0(x, n), do: rem((x * x) + 1, n)

end