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

Примеры.

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

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

а ^–1 ≡ х (mod n).

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

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

а ^–1 (mod n) ºа ^{j(n) – 1} (mod n),

используя алгоритм быстрого возведения в степень.

3. Если функция Эйлера j(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 – Нахождение обратной величины первым способом

х	5 • х	5 • х (mod 7)
3		1

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

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

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

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

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

а ^–1 (mod n) =а ^{j(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).

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

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

q	u1	u2	u3	v1	v2	v3
- -	- 4 -9	- 1	n = 23	- 4 - 9	- 1	a = 5

При 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.

Дата добавления: 2015-08-31