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

Модульная алгебра - это довольно важный раздел, касательно информационной безопасность, а именно криптографии. И не смотря что курс теории чисел и модульной арифметики на кафедре СИБ довольно хорош, многие не всегда могут вспомнить некоторые нюансы, которые в будущем могут облегчить жизнь. Более того, я увидел что в ВГУ также "увлекаются" криптографией, и RSA (http://fkn.ktu10.com/?q=node/4214) и так как при реализации нужно возводить число в очень большую степень а потом находить остаток от деления на другое (модуль) из-за чего приходится использовать либо слишком малые блоки либо работать с большими числами (http://fkn.ktu10.com/?q=node/4233).
В реальности, же, многие устройства реализуют ассиметричные блочные алгоритмы шифрования, и при этом они работают с полноценными блоками и часто не используют большие числа (не всегда это возможно).

О том как возвести число в очень большую степень в модульной арифметике и при этом не повесив комп, я сегодня расскажу.

Итак, сначала математика. Потом будет алгоритм и код на python.
Мы будем работать в кольце - эта такая особая алгебраическая структура. Это знать не обязательно, главное пользоваться особым свойством, но прежде поговорим об обозначениях: стандартно пишут так: $7^4 \pmod{13}$ - это значит 7 в степени 4 по модулю 13, тоесть 7 возвести в 4 и найти остаток от деления на 13 (грубо говоря, тут математики могут меня поругать). А выражение $7^4 \equiv 9 \pmod{13}$ -это значит, что 7 в 4-й степени эквивалентно 9 по модулю 13, по сути если возвести 7 в 4-ю степень и найдя остаток деления на 13 то мы получим 9, но можем туда записать любое число которое нахождении остатка также даст 9, скажем $7^4 \equiv 100 \pmod{13}$ тоже верно - как видим образуется целый класс эквивалентных чисел - это и будем использовать (это использует RSA).
Для более краткого обозначения:
$7^4 \pmod{13}$ будем обозначать, используя стиль неописанного тут алгебраического понятия "кольца" вот так: $[7]^4_{13}$, и позволим себе наглую вольность, вместо $\equiv$ будем использовать $=$.

Рассмотрим предлагаемый алгоритм сначала на примере, потом в общем виде. Пусть нам необходимо возвести число 7 в степень..... эм..... 45 по модулю 5. Тогда делаем так:
$$
[7]^{45}_{5} = [7]_{5} * [7]^{44}_{5} = [7]_{5} * [49]^{22}_{5} = [7]_{5} * [4]^{22}_{5}
$$
Посмотрев на формулу выше, можно уже угадать алгоритм)))) Что мы тут сделали, а вот как раз воспользовались мельком оговоренном мною свойством. Давайте по шагам:

• Сначала мы вынесли множитель чтобы получить чётную степень - это можно, мы в "кольце"
• Потом понизили степень, возведя число в квадрат (обычно для этого не нужны большие числа)
• Далее, просто вспомнили, что по-модулю у нас есть большое количество эквивалентных чисел, ну и просто нашли от получившегося числа - 49 остаток от деления на 5 - это 4 (ведь они эквивалентны в кольце), и с ним дальше работаем (таким образом мы не вылезаем за квадрат модуля, в нашем случае 5)

Далее, просто делаем всё по кругу:
$$
[7]_{5} * [4]^{22}_{5} = [7]_{5} * [16]^{11}_{5} = [7]_{5} * [1]^{11}_{5} = [7]_{5} * [1]_{5} = [7]_{5} = [2]_{5}
$$

К сожалению пример не очень удачный, но короткий (быстро закончился, 1 в 11-й степени это 1), а так, в конце у нас может появиться к примеру такой вот список:
$$
[7]_{5} * [4]_{5} * [3]_{5} * [2]_{5} * [1]_{5} * [2]_{5}
$$
В этом случае их попарно перемножаем и каждый раз после умножения находим остаток, к примеру:
$[7]_{5} * [4]_{5} = [3]_{5} $

Теперь более-менее общее описание алгоритма:

• Сразу сокращаем исходное выражение, пример: $[7]_{5} = [2]_{5}$
• Добиваемся чётной степени путём выноса множителя и добавления его в список (при добавлении в список на любителя, можно копить элементы и потом их попарно умножать, либо оптимизировать и при добавлении элемента смотреть, если там уже один есть, то мы просто перемножаем добавляемый с уже имеющимся и записываем остаток при делении на модуль - таким образом "список" никогда не вырастет больше одного элемента и по-сути не станет "списком")
• Повторяем предыдущий пункт нужное кол-во раз
• Перемножаем между собой элементы списка (эффективно, тоесть используя свойства применяемые выше), и оставшейся элемент в списке перемножаем с полученным элементом операцией "понижения степени" и получаем результат (не забываем что он должен быть тоже поделён на модуль и ответ - остаток - хотя это не обязательно - так как это эквивалентные числа)

Вот и всё, пора показать пример на python (кому было непонятно описание выше - поможет код):

def Zpow(a, p, m):
    """
    Функция возведения в степень по модулю
    принимает 3 аргумента
    a - сам математический аргумент, возводимое число
    p - степень
    m - модуль
    """
    result = 1
    while p > 2: # когда степень сократится до квадрата и меньше - завершаем
        if p % 2 == 0: # если степень кратна 2
            a = (a ** 2) % m
            p = p // 2 # целочисленное деление (на всякий)
        else:
            result = (result * a) % m
            p = p - 1
    a = (a ** p) % m
    result = (result * a) % m
    return result

Можете поиграть с этой функцией - она очень быстро считает, и так как в Питоне по умолчанию все числа Большие, то попробуйте вбивать самые большие числа в аргументы этой функции, какие взбредут вам в голову!!!
В Криптоусиках, также реализована эта функция - и я всячески старался повесить сервак - не получилось.

Зная сколько студентов на лабах по-программированию сломали голову с этой процедурой возведения в степень по-модулю, я думаю этот материал будет полезен.