Основное содержание

Информатика

Course: Информатика > Модуль 2

Урок 5: Модульная арифметика

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

Классная комната Google

Как быстро вычислить A^B mod C, если B представляет собой степень 2?

Используя правила модульного умножения:

например, A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C

Мы можем использовать это свойство для быстрого вычисления 7^256

7^1 mod 13 = 7
7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13

Можно подставить предыдущий результат от 7^1 mod 13 в данное выражение.

7^2 mod 13 = (7 *7) mod 13 = 49 mod 13 = 10
7^2 mod 13 = 10

7^4 mod 13 = (7^2 *7^2) mod 13 = (7^2 mod 13 * 7^2 mod 13) mod 13

Можно подставить предыдущий результат от 7^2 mod 13 в данное выражение.

7^4 mod 13 = (10 * 10) mod 13 = 100 mod 13 = 9
7^4 mod 13 = 9

7^8 mod 13 = (7^4 * 7^4) mod 13 = (7^4 mod 13 * 7^4 mod 13) mod 13

Можно подставить предыдущий результат от 7^4 mod 13 в данное выражение.

7^8 mod 13 = (9 * 9) mod 13 = 81 mod 13 = 3
7^8 mod 13 = 3

Продолжим те же рассуждения, каждый раз подставляя в выражение предыдущий результат.

...через 5 итераций мы получим:

7^256 mod 13 = (7^128 * 7^128) mod 13 = (7^128 mod 13 * 7^128 mod 13) mod 13
7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
7^256 mod 13 = 9

Мы получили способ быстрого вычисления A^B mod C, если B — степень 2.

Но нам нужен метод быстрого модульного возведения в степень, когда B не является степенью 2.

Как быстро вычислить A^B mod C для любого B ?

Шаг 1. Разложим B на степени 2, записав его в двоичном виде

Начнём с самого правого разряда. Пусть k=0. Затем для каждого разряда проделываем следующее:

Если на месте этого разряда стоит 1, записываем 2^k, в другом случае ничего не пишем.
Увеличиваем k на 1 и переходим к следующему разряду

Шаг 2. Вычисляем mod C степеней двойки ≤ B

5^1 mod 19 = 5

5^2 mod 19 = (5^1 * 5^1) mod 19 = (5^1 mod 19 * 5^1 mod 19) mod 19
5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19
5^2 mod 19 = 6

5^4 mod 19 = (5^2 * 5^2) mod 19 = (5^2 mod 19 * 5^2 mod 19) mod 19
5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19
5^4 mod 19 = 17

5^8 mod 19 = (5^4 * 5^4) mod 19 = (5^4 mod 19 * 5^4 mod 19) mod 19
5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19
5^8 mod 19 = 4

5^16 mod 19 = (5^8 * 5^8) mod 19 = (5^8 mod 19 * 5^8 mod 19) mod 19
5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19
5^16 mod 19 = 16

5^32 mod 19 = (5^16 * 5^16) mod 19 = (5^16 mod 19 * 5^16 mod 19) mod 19
5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19
5^32 mod 19 = 9

5^64 mod 19 = (5^32 * 5^32) mod 19 = (5^32 mod 19 * 5^32 mod 19) mod 19
5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19
5^64 mod 19 = 5

Шаг 3. Используем свойства модульного умножения, чтобы свести воедино полученные значения mod C

5^117 mod 19 = ( 5^1 * 5^4 * 5^16 * 5^32 * 5^64) mod 19
5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19
5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19
5^117 mod 19 = 61200 mod 19 = 1
5^117 mod 19 = 1

Примечание:

Существуют более эффективные алгоритмы, но они выходят за рамки данной статьи. Имейте в виду, что при работе с модульной экспонентой в криптографии нередко встречаются показатели степени B > 1000 битов.

Хотите присоединиться к обсуждению?

Войти

Сортировать по:

Пока нет ни одной записи.

Знаете английский? Нажмите здесь, чтобы увидеть обсуждение, которое происходит на английской версии сайта.