5.1.3 Основные способы нахождения обратных величин

Существуют три основных способа нахождения обратных величин

а ^–1 ≡ х (mod n).

1. Проверить поочередно значения 1, 2, … , n – 1, пока не будет найден а ^{– 1}  1 (mod n), такой, что а • а ^–1 (mod n)  1.

2. Если известна функция Эйлера (n), то можно вычислить

а ^–1 (mod n)  а ^{(n) – 1} (mod n), используя алгоритм быстрого возведения в степень.

3. Если функция Эйлера (n) не известна, можно использовать расширенный алгоритм Евклида.

Примеры.

1. Поочередная проверка значений 1, 2, … , n – 1, пока не будет найден х = а ^{– 1} (mod n), такой, что а • х  1 (mod n).

Пусть n = 7, a = 5. Найти х = а ^{– 1} (mod n).

а • х  1 (mod n) или 5 • х  1

n – 1 = 7 – 1 = 6.

Получаем х = 5 ^{– 1} (mod 7) = 3.

Результаты проверки приведены в таблице 5.2.

Таблица 5.2 – Нахождение обратной величины первым способом

2. Нахождение а ^–1 (mod n), если известна функция Эйлера (n).

Пусть n = 7, a = 5. Найти х = а ^{– 1} (mod n) = 5 ^–1 (mod 7).

Модуль n = 7 – простое число. Поэтому функция Эйлера

(n) = (7) = n – 1 = 6.

Обратная величина от5 по mod 7:

а ^–1 (mod n) = а ^{(n) – 1} (mod n) = 5 ^{6 – 1} mod 7 = 5 ⁵ mod 7 =

= (5 ² mod 7) (5 ³ mod 7) mod 7 = (25 mod 7) (125 mod 7) mod 7 =

= (4 • 6) mod 7 = 24 mod 7 = 3.

Итак, х = 5 ^–1 (mod 7) = 3.

3. Нахождение обратной величины а ^–1 (mod n) с помощью расширенного алгоритма Евклида.

Алгоритм Евклида можно обобщить способом, который имеет большое практическое значение. При этом способе во время вычисления НОД (а, b) можно попутно вычислить такие целые числа u₁ и u₂, что

а • u₁ + b • u₂ = НОД (а, b).

Это обобщение (расширение) алгоритма Евклида удобно описать, используя векторные обозначения.

Расширенный алгоритм Евклида

При заданных неотрицательных целых числах а и b этот алгоритм определяет вектор (u₁, u₂, u₃), такой, что

а • u₁ + b • u₂ = u₃ = НОД (а, b).

В процессе вычисления используются вспомогательные векторы (v₁, v₂, v₃), (t₁, t₂, t₃). Действия с векторами производятся таким образом, что в течение всего процесса вычисления выполняются соотношения

а • t₁ + b • t₂ = t₃,

а • u₁ + b • u₂ = u₃,

а • v₁ + b • v₂ = v₃.

Для вычисления обратной величины а ^–1 (mod n) используется частный режим работы расширенного алгоритма Евклида, при котором:

b = n, НОД (а, n) = 1, и этот алгоритм определяет вектор (u₁, u₂, u₃), такой, что

u₃ = 1, а • u₁ + n • u₂ = НОД (а, n) = 1,

(а • u₁ + n • u₂) mod n  а • u₁ (mod n)  1,

а ^–1 (mod n)  u₁ (mod n).

Шаги алгоритма:

1. Начальная установка.

Установить (u₁, u₂, u₃) : = (0, 1, n),

(v₁, v₂, v₃) : = (1, 0, a).

2. u₃ = 1 ?. Если u₃ = 1, то алгоритм останавливается.

3. Разделить, вычесть.

Установить q : = [u₃ / v₃].

Затем установить

(t₁, t₂, t₃) : = (u₁, u₂, u₃) – (v₁, v₂, v₃) • q,

(u₁, u₂, u₃) : = (v₁, v₂, v₃),

(v₁, v₂, v₃) : = (t₁, t₂, t₃).

Возвратиться к шагу 2.

Пример. Даны модуль n = 23 и число а = 5.

Найти обратное число а ^–1 (mod 23), т.е. х = 5 ^–1 (mod 23).

Используя расширенный алгоритм Евклида, выполним вычисления, записывая результаты отдельных шагов в таблицу 1.5.1.

Таблица 5.3 – Шаги выполнения алгоритма Евклида

При u₃ = 1, u₁ = - 9, u₂ = 2.

(а • u₁ + n • u₂) mod n = (5 • (- 9) + 23 • 2) mod 23 = 5 • (- 9) mod 23  1,

а ^–1 (mod n) = 5 ^–1 (mod 23) = (- 9) (mod 23) = (- 9 + 23) (mod 23) = 14.

Таким образом, х = 5 ^–1 (mod 23)  14 (mod 23) = 14.

Для решения более сложных сравнений

а • х  b (mod n), т.е. b  1, x = ?

используется следующий прием. Сначала решают сравнение

а • y  1 (mod n),

т.е. определяют y = a ^–1 (mod n),

а затем находят

x = a ^–1 • b (mod n) = y • b (mod n).

{ Пример. Найти х для сравнения 5 • х  9 (mod 23).

Сначала решаем сравнение 5 • y  1 (mod 23).

Получаем y = 5 ^–1 (mod 23) = 14. Затем находим

x = 5 ^–1 • 9 (mod 23) = 14 • 9 (mod 23) = 126 (mod 23)  11 (mod 23).

x = 11. }