Непривычное быстрое возведение в степень

Обычно, все возводят число в степень бинарно, попробуем сделать это изощреннее.

Бинарное возведение в степень, которому все учат

У нас есть число, допустим 7. Нам его нужно возвести в степень 19, по модулю 1024, к примеру. Как оно обстоит:

1. У нас изначально есть переменная, хранящая такое же значение, как и база для возведения в степень, и отдельная переменная, изначально равная 1.
2. Идем по битам сначала степени.
3. Если в бите стоит 1, то мы умножаем финальное число на переменную. Если 0, то пропускаем.
4. После условия мы умножаем базовое число само на себя, убираем последний бит у степени (мы его использовали только что) и начинаем новую итерацию.

Выглядит оно следующим образом

def binpow(base, power, mod) :
    res = 1
    base = base % mod
    while power ! = 0 :
        if power & 1:
            res = res * base % mod
        base = base * base % mod
        power >> = 1
    
    return res;

В чем удобство данного алгоритма? Он достаточно быстрый. Для возведения в степень 19 - 10011, мы проделаем всего 5 итераций циrла, O(LogN).

Максимально простое представление:

7 ^ 19 mod 1024 = 7^1 * 7^2 *7^16 - в сумме степени дают 19, и это как раз что нам надо.

В чем же проблема данного алгоритма? Если мы будем смотреть по тактам, то легко можем понять что происходит внутри. Из-за наличия условия, где происходят самые большие вычисления, алгоритм не является безопасным на аппаратном уровне: либо два умножения (одно из которых гораздо сложнее другого) и сдвиг, либо одно простое и сдвиг.

И тут появляется Монтгомери и предлагает свою лесенку

Лестница Монтгомери

В чем основная идея лестницы? В том, что умножения происходят также и если условие не выполняется. Что это дает? Постоянно происходят разные вычисления, сложно понять что происходит извне (да, в последние годы были исследования уязвимостей и там находили проблемы, но нам важна идея сейчас и понимание), а также эта лесенка применяется в разных кривых как быстрый способ вычисления.

Как выглядит код:

def mont_ladder(base, power, mod):
    power_bin = format(power, 'b')

    first = 1
    second = base % mod

    for i in power_bin:
        if i == "0":
            second = (first * second) % mod
            first = pow(first, 2, mod)
        else:
            first = (first * second) % mod
            second = pow(second, 2, mod)

   return first
}

Думаю проще будет показать на примере вычислений:

1. base = 7, power = 19, mod = 1024
2. x = 1, y = 7
3. pow_bin = 10011
4. заходим в цикл
1. i == 1
   x = 1 *7 mod 1024 = 7
   y = 7 * 7 = 49
2. i == 0
   y = 7*49 mod 1024=343
   x = 7 * 7 = 49
3. i == 0
   y = 343*49 mod 1024 = 423
   x = 49 * 49 = 353
4. i == 1
   x = 353*423 mod 1024 = 839
   y = 423*423 mod 1024 = 753
5. i == 1
   x = 839*753 mod 1024 = 983
   y = 753*753 mod 1024 = 737

Получили x = 983, это и есть ответ.

7^19 = 11 398 895 185 373 143 % 1024 = 983.

При всем при этом, лесенка монтгомери не всегда выдает ответ на x, порой она дает правильные значения на втором из оперируемых переменных при возведении в степень

Это все хорошо, но зачем оно нам?

Понадобится позже для понимания того, как происходят вычисления в эллиптических кривых, важность понимания постоянных вычислений (не пропуская вычисления если условие не совпадает, что важно для криптографии) и важность