Основные способы нахождения обратных величин a–1  1 (mod n).

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

2. Если известна функция Эйлера (n), то можно вычислить a^–1 (mod n)  a^(n)–1 (mod n), используя алгоритм быстрого возведения в степень.

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

Проиллюстрируем эти способы на числовых примерах.

1. Поочередная проверка значений 1, 2, ..., n – 1, пока не будет найден x = a^–1 (mod n), такой что a∙x  1 (mod n).

Пусть n = 7, a = 5. Требуется найти x = a^–1 (mod n).

a∙ x  1 (mod n) или 5∙x  1 (mod 7).

Получаем x = 5^–1 (mod 7) = 3. Результаты проверки сведены в таблицу.

x	5  x	5  x (mod 7)
1 2 3 4 5 6	5 10 15 20 25 30	5 3 1 6 4 2

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

Пусть n=7, a=5. Найти x=a^–1 (mod n)=5^–1 (mod 7). Модуль n=7 – простое число. Поэтому функция Эйлера (n)=(7)=n–1=6. Обратная величина от 5 по mod 7

a^–1 (mod n) = a^(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.

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

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

Расширенный алгоритм Евклида для нахождения обратных элементов (относительно умножения) кольца вычетов. Алгоритм Евклида обобщают и представляют в нескольких формах, которые имеют большое практическое значение.

Форма1. В этой форме во время вычисления НОД(a,b) попутно вычисляют такие целые числа u₁ и u₂, что

a∙u₁ + b∙u₂ = НОД (a,b).

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

a∙u₁ + b∙u₂ = u₃ = НОД (a, b).

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

a∙t₁ + b∙t₂ = t₃, a∙u₁ + b∙u₂ = u₃, a∙v₁ + b∙v₂ = v₃.

Для вычисления обратной величины a^–1 (mod n) используется частный режим работы расширенного алгоритма Евклида, при котором b = n, НОД (a,n) = 1, и этот алгоритм определяет вектор (u₁, u₂, u₃), такой, что

u₃ =1, a∙u₁ + n∙u₂ = НОД (a,n) =1,

(a∙u₁ + n∙u₂) mod n  a∙u₁ (mod n)  1,

a^–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 и число a = 5. Найти обратное число a^–1 (mod 23), т.е. x = 5^–1 (mod 23).

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

q	u1	u2	u3	v1	v2	v3
– 4 1 1 –	0 1 –4 5 –9	1 0 1 –1 2	n = 23 5 3 2 1	1 –4 5 –9	0 1 –1 2	a = 5 3 2 1

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

(a∙u₁ + n∙u₂ ) mod n = (5∙(– 9) + 23∙2) mod 23 = 5∙(– 9) mod 23  1,

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

Итак, x = 5^–1 (mod 23)  14 (mod 23) = 14.

Форма 2. Пусть НОД(а,n)=1, a>0, n>0. Рассматривается задача поиска целочисленного решения (x,y) уравнения a∙x-n∙y=1. Для решения задачи используют сначала алгоритм Евклида:

a = n ∙q₀ + r₁

n = r₁ ∙ q₁ + r₂

r₁ = r₂ ∙ q₂ + r₃

r₂ = r₃ ∙ q₃ + r₄

…………………

r_k–2 = r_k–1 ∙ q_k-1 + r_k

r_k–1 = r_k ∙ q_k +0

Находят последовательность q₀, q₁, q₂,…,q_k. Затем рекуррентно строят P₀,Р₁,Р₂,…,Р_k и Q₀,Q₁,Q₂,…,Q_k. Полагают

P_-2=0, P_-1=1 и P_j=q_jP_j-1+ P_j-2 для j0,

Q_-2=1, Q_-1=0 и Q_j=q_jQ_j-1+Q_j-2 для j0.

Искомые значения x, y находятся по формулам

.

Обратный элемент а^-1=(modn) для числа а есть решение уравнения