Возведение в степень по модулю

Наконец, давайте рассмотрим экспоненциальное свойство.

Часто нам бывает нужно вычислить A^B mod C для больших значений B.
К сожалению, A^B очень быстро растёт даже для довольно маленьких значений B.

2^90 = 1 237 940 039 290 000 000 000 000 000

7^256 = 2 213 595 400 050 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 83 794 038 078 300 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 721 264 246 243 000 000 000 000 000

А для больших значений калькуляторы и компьютеры могут выдать ошибку переполнения.
Даже если мы не получили ошибку, вычисление модуля таких огромных чисел может занять очень много времени.

Представьте, что нам нужно вычислить 2^90 mod 13, но наш калькулятор не умеет работать с числами, больше чем 2^50.

Тут вступает в дело простая стратегия разделяй и властвуй:

2^90 = 2^50 * 2^40

2^50 mod 13 = 1125899906842624 mod 13 = 4
2^40 mod 13 = 1099511627776 mod 13 = 3

2^90 mod 13 = (2^50 * 2^40) mod 13
2^90 mod 13 = (2^50 mod 13 * 2^40 mod 13) mod 13
2^90 mod 13 = ( 4 * 3 ) mod 13
2^90 mod 13 = 12 mod 13
2^90 mod 13 = 12

Как вычислить 7^256 mod 13 при помощи калькулятора, который работает только с числами, меньшими чем 7^10?

Можно разбить 7^256 на 25 частей по 7^10 и 1 часть по 7^6, но это не самое лучшее решение.

Есть способ лучше…