Task 72. Возводим в степень

Задача: Вычислить значение a^b mod m,

где 1 <= a <= 10^9, 1 <= b <= 10^7, 2 <= m <= 10^9.

Пример: 

a 595, b = 703, m = 991

a^b mod m = 342.

Идея: вспомним математику и воспользуемся методом быстрым возведением в степень a^b:

Осталось добавить вычисление остатка.

Более подробно про алгоритмы быстрого возведения в степень вы можете почитать на wiki:

• Возведение в степень по модулю
• Алгоритмы быстрого возведения в степень

Реализация:

https://gist.github.com/unilecs/d62ead0be11d790937a4ebd27f117ee6

Тест:

https://dotnetfiddle.net/ZIPwSh