defmodule Prime.MillerRabin do
  @moduledoc """
  Implementation of Miller-Rabin-test.

  This module provides the primality test based on
  Miller-Rabin's method.

  The methodology is essentially probablistic.
  See the doc of `Prime.Fermat` for details.

  The unignorable difference between fermat-test and
  miller-rabin-test is that the latter defeats Carmichael
  numbers while giving up no efficiency. You might
  feel easier to reason towards employing this algorithm
  than the fermat-test, although they are equally great
  formulations of the intrinsic nature of numbers.
  """

  @iterations 128

  @doc """
  Returns the result of miller-rabin-test.

  ## Examples

      iex> Prime.MillerRabin.test(1)
      false

      iex> Prime.MillerRabin.test(2)
      true

      iex> Prime.MillerRabin.test(3)
      true

      iex> Prime.MillerRabin.test(42)
      false

      iex> Prime.MillerRabin.test(561)
      false # won't get fooled by the first carmichael number.

  """
  @spec test(pos_integer()) :: boolean()
  def test(n) when n < 2, do: false

  def test(n) when n == 2, do: true

  def test(n) do
    do_test(n, @iterations)
  end

  defp do_test(_, 0), do: true

  defp do_test(n, k) do
    p = Enum.random(2..(n - 1))

    if powmod_with_check(p, n - 1, n) == 1 do
      do_test(n, k - 1)
    else
      false
    end
  end

  defp powmod_with_check(_, 0, _), do: 1

  defp powmod_with_check(base, exp, mod) when rem(exp, 2) == 0 do
    case powmod_with_check(base, div(exp, 2), mod) do
      x when rem(x * x, mod) == 1 and x != 1 and x != mod - 1 -> 0
      x -> rem(x * x, mod)
    end
  end

  defp powmod_with_check(base, exp, mod) do
    rem(base * powmod_with_check(base, exp - 1, mod), mod)
  end
end