Вычисление (Pow(a,b) mod c) при больших a,b,c

#c_sharp

Как вычислить данное выражение не словив переполнение при Pow ?

ulong Pow(ulong a, ulong b)
{
  ulong p = 1;
  for (ulong i = 0; i < b; ++i)
    p *= a;
  return p;
}

ulong m = Pow(a, b) % c;

    

Ответы

Ответ 1

Если a * c не вылезает за ulong, то так:

ulong Pow(ulong a, ulong b)
{
  a = a % c;
  ulong p = 1;
  for (ulong i = 0; i < b; ++i)
    p = (p * a) % c;
  return p;
}


Инвариант: p < c. При умножении p * a < c * a, и по условию переполнения не происходит.



Обновление: для больших значений степени имеет смысл умножать путём последовательного
возведения в квадрат.

ulong Pow(ulong a, ulong b)
{
  a = a % c;
  ulong p = 1;
  ulong r = 1;
  while (b > 0)
  {
    if (b % 2 != 0)
      r = (r * p) % c;
    b = b / 2;
    p = (p * a) % c;
  }
  return r;
}


Ответ 2

Алгоритм Монтгомери позволяет это делать https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9C%D0%BE%D0%BD%D1%82%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%B8