Алгоритм нахождения числа по модулю

Операцию нахождения числа по модулю (операцию нахождения вычета числа «а» по модулю «Р») называют приведением числа «а» по модулю «Р»

y = a mod P

Эта запись в модулярной алгебре читается как «число y сравнимо с числом а по модулю Р». Это соотношение справедливо для целых значений чисел: y, a, P и Р ≠ 0. Число «а» определяют как «вычет» числа «y» по модулю «Р». Операцию нахождения вычета числа «а» по модулю «Р» можно интерпретировать численным примером следующим образом. Найти вычет выражения y = 23 mod 17 = 6 mod 17, т.е. число 23 делится на 17, находится остаток, который и будет являться вычетом числа 23 по модулю 17. Набор целых чисел от 0 до Р-1 называется полным набором вычетов по модулю Р. Для последующих вычислений необходимо определять вычеты и от отрицательных чисел, например:

-23 mod 7 = -16 mod 7 = -9 mod 7 = -2 mod 7 = 5 mod 7 и т.д.

Модулярная алгебра полностью отвечает требованиям коммутативности, ассоциативности и дистрибутивности:

(а + b) mod P = [ a (mod P) + b (mod P)] mod P

(а - b) mod P = [ a (mod P) - b (mod P)] mod P

(а * b) mod P = [ a (mod P) * b (mod P)] mod P

[а * (b + c)] mod P = {[ a * b (mod P)] + [a * c (mod P)]} mod P

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

В теории криптографических преобразований достаточно часто приходится сталкиваться с трудоемкой задачей вычисления обратных величин по модулю. Во многих криптографических задачах для заданных чисел «а» и «Р» требуется нахождение числа «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.

Поиск по сайту: