Быстрое возведение в степень по модулю

Даны base, exponent (может быть очень большим, до 10^9 и выше) и modulus. Верните (base ^ exponent) mod modulus. Умножение base на себя exponent раз слишком медленное при большом exponent. Разложите exponent по битам (бинарное возведение в степень) - тогда потребуется всего O(log exponent) умножений.