Полезный алгоритм - Modular exponentiation

Суть алгоритма в вычислении a^b mod c без вычесления значения a^b.

Подробное описание алгоритма

(Псевдо)код

Bignum modpow(Bignum b, Bignum e, Bignum m) {

 

   Bignum result = 1;

 

   while (e > 0) {

      if ((e & 1) == 1) result = (result * b) % m;

      e >>= 1;

      b = (b * b) % m;

   }

   return result;

}