Почему большое количество тайм-аутов в Эликсире? - PullRequest
Новая
       14

Почему большое количество тайм-аутов в Эликсире?

0 голосов
/ 04 июня 2018

Я пытаюсь воссоздать некоторые основы биткойна в эликсире.Я знаю, что Elixir - не идеальный язык для этой задачи, но я делаю это для развлечения и в учебных целях.Я столкнулся со следующей проблемой, пытаясь реализовать вывод открытого ключа из секрета, который включает в себя очень большую степень очень большого числа в конечном поле.Я реализовал это сам, учитывая, что: math.pow / 2 уже борется с сравнительно небольшими числами.Но моя реализация занимает очень много времени, и функция со временем перестает работать.

Значения и вызов функции: 

prime = 115792089237316195423570985008687907853269984665640564039457584007908834671663
val = 65341020041517633956166170261014086368942546761318486551877808671514674964848

Util.my_fpow(val, prime - 2, prime)

Метод my_fpow / 3 в модуле Util: 

defmodule Util do
  def my_fpow(n, k, prime), do: my_fpow(n, k, 1, prime)
  defp my_fpow(_, 0, acc, _), do: acc
  defp my_fpow(n, k, acc, prime) do
    new_acc = n * acc
              |> rem(prime)

    my_fpow(n, k - 1, new_acc, prime)
  end
end

Прежде всего, я хотел бы понять наболее глубокий уровень, почему этот метод занимает так много времени для этих больших чисел.Также мне было бы интересно, есть ли другие более эффективные реализации, которые все еще могут сделать жизнеспособными такие вычисления в Elixir (не в масштабе, просто так, чтобы вычисления могли фактически закончиться до истечения времени ожидания).

1 Ответ

0 голосов
/ 04 июня 2018

Ваша функция будет повторяться prime - 2 раз, так как вы вычитаете ее по 1 за раз.Даже если Elixir выполняет 1 миллиард вызовов в секунду (чего не будет на текущем оборудовании), это займет более 10 ^ 60 лет.

Гораздо более быстрое решение включает в себя возведение в квадрат числана каждой итерации , что уменьшает количество вызовов до log2(x), что довольно быстро.Вот перевод этого алгоритма: 

defmodule A do
  # Calculates (n ^ k) % m.
  def powmod(n, k, m), do: powmod(n, k, m, 1)
  def powmod(_, 0, _, r), do: r
  def powmod(n, k, m, r) do
    r = if rem(k, 2) == 1, do: rem(r * n, m), else: r
    n = rem(n * n, m)
    k = div(k, 2)
    powmod(n, k, m, r)
  end
end

prime = 115792089237316195423570985008687907853269984665640564039457584007908834671663
val = 65341020041517633956166170261014086368942546761318486551877808671514674964848

IO.inspect A.powmod(val, prime - 2, prime)

Вывод: 

83174505189910067536517124096019359197644205712500122884473429251812128958118
...