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

Сегодня я разберу возведение в степень по модулю. Этот метод очень эффективен для того, чтобы
возводить в степень вообще, но по модулю он еще эффективнее выходит.
Для начала, можно сказать, что:
a^{b+c} = a^ba^c
Любое число можно разложить в двоичное представление:
2^0 + 2^1 + 2^4 + 2^5 = 1 + 2 + 16 + 32 = 51
То есть, например, попробуем возвести в степень 51 число 17:
17^{51} = 17^{2^0 + 2^1 + 2^4 + 2^5} = 17^{1 + 2 + 16 + 32} = 17^{32}17^{16}7^217^1
Специально в обратном порядке записал, это важно сейчас. Итак, что мы видим:
17^{32} = (17^{16})^2 = ((17^8)^2)^2 = (((17^4)^2)^2)^2 = ((((17^2)^2)^2)^2)^2)
Как видим, возвести 17 надо 5 раз в квадрат, чтобы получить требуемое нам значение. Теперь давайте разложим нашу основную последовательность:
17^{51} = 17^{32}17^{16}17^217^1 = (17^{16}17^{8}17^1)^217^1 = ((17^817^4)^217)^217 = (((17^417^2)^2)^217)^217 = ((((17^217)^2)^2)^217)^217
Чтобы была видна закономерность, перепишем с добавлением * 1:
17^{51} = (((((1*17)^217)^2*1)^2*1)^217)^217
Или если в другом виде представить
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 в двоичной системе равно 1100112. Легко увидеть систему. Там где двоичный разряд равен 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
Где bi = 0 или 1 слева направо, в последнем разряде ^2 ==> ^1