Вычисление обратных величин в модулярной алгебре

В теории криптографических преобразований достаточно часто приходится сталкиваться с трудоемкой задачей вычисления обратных величин по модулю. Во многих криптографических задачах для заданных чисел «а» и «Р» требуется нахождение числа «d» меньшего «Р» (d < P), чтобы выполнялось единичное сравнение a * d mod P ≡ 1.

Необходимо отметить, что такое число «d» существует, если числа «а» и «Р» взаимно простые, при этом число «d» называют инверсией числа «а» по модулю «Р» и обозначают как: а^-1 mod P. Например, требуется определить инверсию 6^-1 mod 17; необходимо найти такое число, которое при умножении на число 6 и делении этого произведения на число 17 в остатке образует число 1. В рассматриваемом примере таким числом будет являться число 3, т.к. 6 * 3 mod 17 ≡ 1, следовательно, число 3 является инверсией числа 6 по модулю 17.

Для вычисления обратных величин при условии, что если Р - простое число, что практически справедливо для всех криптографических задач асимметричной криптографии, можно воспользоваться малой теоремой Ферма.

Малая теорема Ферма интерпретируется следующим образом: если «Р» - простое число, «а» - целое число, то инверсию числа «а» по модулю «Р» можно определить как:

а^-1 (mod Р) = а^{φ(P) – 1} mod P

где: φ (Р) – функция Эйлера;

для простых чисел φ (Р) = Р – 1.

Функция Эйлера указывает сколько во множестве чисел от 0 до Р, есть чисел взаимно простых с Р.

Например, если Р = 17, то φ (Р) = Р-1 = 17-1 = 16. Требуется вычислить инверсию числа 2 по модулю 17, т.е. вычислить 2^-1 mod 17.

2^-1mod 17 = 2^{φ(P) – 1}mod Р = 2¹⁵mod 17 = 32768 mod 17 = 9 mod 17 → 9.

Следовательно, число 9 является инверсией числа 2 по модулю 17, т.к. 2 * 9 mod 17 = 18 mod 17 = 1 mod 17 → 1.