§ Математический вывод

Сегодня я разберу возведение в степень по модулю. Этот метод очень эффективен для того, чтобы
возводить в степень вообще, но по модулю он еще эффективнее выходит.
Для начала, можно сказать, что:
Любое число можно разложить в двоичное представление:
То есть, например, попробуем возвести в степень 51 число 17:
Специально в обратном порядке записал, это важно сейчас. Итак, что мы видим:
Как видим, возвести 17 надо 5 раз в квадрат, чтобы получить требуемое нам значение. Теперь давайте разложим нашу основную последовательность:
Чтобы была видна закономерность, перепишем с добавлением * 1:
Или если в другом виде представить

r = 1
1: r = (r*17)2
1: r = (r*17)2
0: r = (r*1)2
0: r = (r*1)2
1: r = (r*17)2
1: r = (r*17)2

Заметим, что число 51 в двоичной системе равно 110011₂. Легко увидеть систему. Там где двоичный разряд равен 1, предыдущее вычисленное значение умножается на основание, у нас здесь оно 17, и возводится в степень 2. Там где разряд равен 0, то ничего не делается (точнее, умножается на 1), и потом возводится в квадрат. Так везде, кроме 0-го разряда. Если мы обрабатываем 0-й разряд (младший бит), то тогда возводить в квадрат не надо (это и понятно, это же 0-й разряд).
Алгоритм очень простой. Вначале у нас R=1, и умножаем на него в любом случае.

ЦИКЛ от старшего бита к младшему:

    ЕСЛИ бит = 1:
        R = R * A [MOD M]

    ЕСЛИ не последний разряд:
        R = R * R [MOD M]

Здесь только стоит добавить высчитывание модуля по основанию M, чтобы мы получили число, ограниченное модулем. То есть после каждого умножения или возведения в степень нужно брать модуль (т.е. остаток) от R и M.

§ Программный код

1unsigned long fpow(unsigned long a, unsigned long b, unsigned long m) {
2
3    unsigned long r = 1;
4    for (int id = 31; id >= 0; id--) {
5        if (b & (1 << id)) r = (r * a) % m;
6        if (id) r = (r * r) % m;
7    }
8    return r;
9}
10
11printf("%li\n", fpow(20735, 23527, 33389)); // =84

§ Примеры

Возвести в степень (3 ^ 9) % 17, где 10012 = 9
Итак: r=1

    1: (r*a)^2 % c = r
    0: (r*1)^2 % c = r
    0: (r*1)^2 % c = r
    1: (r*a)^1 % c = r

Результат =14

    (1*3)^2 % 17 = 9
    (9*1)^2 % 17 = 13
    (13*1)^2 % 17 = 16
    (16*3)^1 % 17 = 14

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

    Ri+1 = (Ri * abi)2 mod c

Где b_i = 0 или 1 слева направо, в последнем разряде ^2 ==> ^1