Алгоритм операции возведения числа в степень по модулю

Этот алгоритм является одной из важнейших операций в криптографических преобразованиях с открытым ключом. Для простоты рассуждений рассмотрим этот алгоритм на численном примере.

Например, требуется вычислить y = a^x mod P при числовом отображении y = 6¹⁸¹ mod 77.

Во всех вычислениях степенной функции по модулю на первом шаге вводится параметр t = ë log ₂ X û – целая часть log ₂ X. Символы ë…û означают, выбор целой части включенного выражения.

Если y = a^x mod P, где: а = 6; х = 181; Р = 77, то y = 6¹⁸¹ mod 77.

1. На первом шаге алгоритма определяется значение целой части логарифма по модулю 2 показателя степени х (в примере х = 181) t = ë log ₂ 181û;

2^t ≤ х = 2^t ≤ 181, откуда t = 7, следовательно, 2⁷ ≤ 181; 128 ≤ 181.

2. На втором шаге алгоритма вычисляются числа ряда S_i = aⁿ, где n = 2^t. В рассматриваемом числовом примере t = 7, следовательно, последний член ряда определится как S₇ = a¹²⁸. Таким образом, искомый числовой ряд может быть представлен следующим образом:

S_i → а а² а⁴ а⁸ а¹⁶ а³² а⁶⁴ а¹²⁸, т.к. а = 6; Р = 77, то степенные значения ряда вычисляются по модулю Р = 77

а а² а⁴ а⁸ а¹⁶ а³² а⁶⁴ а¹²⁸

6 36 64 15 71 36 64 15 при а =6 по mod Р (Р = 77)

1. После вычисления значений степенного ряда необходимо показатель степени выражения y = a^x mod P отобразить в двоичной форме

Х = 181 → (1 0 1 1 0 1 0 1)₂; 1 0 1 1 0 1 0 1 → 2⁷+2⁵+2⁴+2²+2⁰ = 128+32+16+4+1 = 181.

4. Составляется следующая таблица

а128	а64	а32	а16	а8	а4	а2	а0	Искомый ряд
								Двоичное представление показателя степени «Х»
								Численные значения ряда Si

В соответствии со значением отображения показателя степени «х» в двоичной форме вычисляется произведение:

П = (а¹²⁸ * а³² * а¹⁶ * а⁴ * а⁰) mod P = (15 * 36 * 71 * 64 * 6) mod 77 =

= (14722560) mod 77 = 6 mod 77 ≡ 6.

Следовательно, 6¹⁸¹mod 77 = 6 mod 77 ≡ 6.

На рис.2 представлен фрагмент вычисления степенной функции по модули в рамках разработанной автором автоматизированной обучающей системы.

Рис.2. Пример решения задачи возведения числа по модулю.