Алгоритм последовательного возведения в квадрат

Алгоритм последовательного возведения в квадрат

(https://granitnayki.com/?cat=6)

Пусть необходимо вычислить

y = a^x mod n,

где a – неотрицательное целое число, меньшее n (a < n), x ³ 0.

Для вычисления y = a^x mod n применяем

1. Если , то закончить работу алгоритма.

2. , , где - длина x в битах.

3. Для i от k до 0 выполнить шаги 4 и 5.

4. .

5. Если i-й бит x =1, то .

6. Закончить работу алгоритма.

Этот алгоритм называется также SX-алгоритмом (https://granitnayki.com/?cat=6). Смысл такого названия состоит в следующем: считаем, что S(squaring) соответствует операции возведения в квадрат, а X – операции умножения на основание. К примеру, возведем основание a в степень 23 по модулю p. Запишем 23 в двоичной системе счисления как 10111. Далее, пропуская самый левый бит, который всегда равен 1 запишем под каждой цифрой 1 SX, а под каждой цифрой 0 – X.

	S	SX	SX	SX

Двигаясь слева направо, получим определяющую строку SSXSXSX. Помня, что S – это возведение в квадрат, а X – умножение на основание, получаем следующую последовательность операций:

(((((((((((a²mod n)²)mod n)*a) mod n)² mod n)*a) mod n)² modn)*a) mod n)=a²³ mod n,

что соответствует действительности.

Пример. Вычислить 2¹⁸ mod 13, параметры: a = 2, k = 18, n =13.

x = 2⁴ +2¹® (1, 0, 0, 1, 0)

1. y:=2

2. k:=3

3(4-5). i = 3 x ₃ = 0 y:=2² mod 13 = 4

i = 2 x ₂ = 0 y:=4² mod 13 = 3

i = 1 x ₁=1 y:=3² mod 13 = 9 y:=y*2 mod 13=5 y=5

i = 0 x ₀=0 y:=5² mod 13 = 12

6. y = 12

Таким образом, 2¹⁸ mod 13 = 12.

Контрольные вопросы

1. Опишите алгоритм последовательного возведения в квадрат.

2. В каких криптографических алгоритмах необходимо вычислять степени числа по модулю?