Информатика / математика и код

Быстрое возведение в степень по модулю

Более подробный разбор с выводом формулы.

Сегодня я разберу возведение в степень по модулю. Этот метод очень эффективен для того, чтобы возводить в степень вообще, но по модулю он еще эффективнее выходит. В статье по RSA я уже описывал алгоритм, но теперь я опишу немного подробнее.

Для начала, можно сказать, что:

$$ 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 $$

Заметим, что число 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.

Яндекс.Метрика