Вычисление обратных элементов
В арифметике действительных чисел просто вычислить обратную величину a−1 для ненулевого a:
a-1 = 1/a или a? a-1 = 1.
В модулярной арифметике вычисление обратной величины является более сложной задачей. Например, решение сравнения
4? x ≡ 1 mod 7
эквивалентно нахождению всех значений x и k, для которых выполняется равенство 4? (x + 7k) mod 7 = 0, где k - любые целые числа.
Задачей решения сравнения является нахождение такого целого числа
x, при котором будет выполняться сравнение
a? x mod m ≡ 1,
где a - известное натуральное число, a Î{1, 2, …, m-1};
m - числовой модуль (натуральное число) для нормирования результата;
x - искомое неизвестное,
x =1, m -1.
Сравнение a? x mod m ≡ 1 также можно записать в виде:
a-1 ºxmod m
или a-1 mod m = x mod m.
Сравнение
a-1 ºxmod m
имеет единственное решение (единственный
обратный элемент a-1), если:
- числа a и m являются взаимно простыми;
- числа a и a-1 удовлетворяют условию (a · a-1) mod m ≡ 1;
- и a-1 =1, m -1.
В других случаях сравнение не имеет решения.
Пример 2.2. Найдем обратный элемент для числа 5 по простому модулю 17. Обратный элемент будет равен 7 (например, результат можно получить перебором), так как 5? 7 = 35 mod 17 ≡ 1.
Найдем также обратный элемент для числа 5 по модулю 14. Обратный элемент будет равен 3, так как 5? 3 = 15 mod 14 ≡ 1. А число 2 не имеет
обратного элемента, так как числа 14 и 2 не взаимно просты.
В поле GF(m), где m - простое число, все ненулевые элементы имеют обратные элементы.
Основные способы нахождения обратных элементов
I. Для упрощения ручного счета обратные элементы для чисел, сравнимых с размерностью машинного слова, в модульной арифметике можно вычислять по следующему итеративному алгоритму. Выполняется
перебор возможных значений в интервале
a-1 =1, m -1, до тех пор, пока не
будет найдено такое a-1, что будет выполняться (a · a-1) mod m = 1.
Пример 2.3. Пусть a = 5, m = 7. Решим равенство (a · a−1) mod m = 1 или
(5 · a−1) mod 7 = 1. Найдем a-1 перебором. При этом число a-1 должно искаться
в интервале
a-1 =1, m -1.
Результаты представим в виде трассировочной табл. 2.2 (искомый
результат подчеркнут линией).
|
| Шаг, a−1 | 5 · a−1 | (5 · a−1) mod 7 |
| 3 | 15 | 1 |
Получаем, что a-1 = 5-1 mod 7 = 3.
Вариантом переборного алгоритма также является следующий алгоритм. Если числа a и m взаимно просты (НОД(a, m) = 1), то существует обратный элемент для a, а выражение a? a−1 ≡ 1 mod m можно записать в виде a? a−1 mod m = (1 + m? t) mod m, где t - натуральное число. Числа a и m заданы, неизвестны числа t и a−1. Тогда нужно найти такое t, при котором a−1 будет целым и будет удовлетворять условию существования обратного элемента: a? a−1 ≡ 1 mod m. Перепишем выражение a? a−1 mod m = (1 + m? t)
mod m как
a -1 =æ1+
mt ö
÷mod m .
|
Запишем шаги алгоритма.
1. Если НОД(a, n) ¹ 1 (алгоритм Евклида, раздел 1.1), то выход. Обратный элемент не существует.
2. Для любого t Î[0, +¥) вычисляются следующие действия.
2.а. Если значение выражения
1 + mt
a
не является натуральным числом,
то переход к пункту 2. Иначе это выражение задает обратный элемент:
|
mt ö
÷mod m , выход.
è a ø
Алгоритм будет конечен в том случае, когда выполняется условие взаимной простоты двух чисел a и m (условие существования обратного элемента).
II. Можно вычислить для элемента a обратный элемент a-1 и при знании
функции Эйлера φ(m), где (a, m) = 1. Так как
aj(m) mod m º1 и
(a · a−1) mod m ≡ 1, то
aj(m) mod m =(a ×a-1 )mod m =>
aj(m)-1 mod m =a -1 mod m
=> a-1 ºaj(m)-1 mod m .
Данную формулу можно вычислить с меньшими вычислительными затратами, используя схему Горнера для быстрого возведения числа a в степень (φ(m) - 1).
Пример 2.4. Пусть a = 5, m = 7. Найдем a-1 с помощью функции Эйлера.
Модуль m = 7 является простым числом. Поэтому функция Эйлера равна
φ(m) = φ(7) = m − 1 = 6. Тогда обратная величина от 5 по модулю 7 равна
a-1 =aj(m)-1 mod m
= 56-1 mod 7 = 55 mod 7.
Используем схему Горнера для разложения степени у числа 5.
55mod 7 = (52mod 7)·(52mod 7)·(5 mod 7) mod 7 = (4 · 4 · 5) mod 7 =
= (2 · 5) mod 7 ≡ 3.
Таким образом, для числа a обратный элемент равен a-1 = 3.
III. Использование расширенного алгоритма Евклида.
В алгоритме все операции производятся над целыми числами. Под обозначением ]k[ будем понимать взятие от числа k только целой части, без округления.
Расширенный алгоритм Евклида для нахождения обратного элемента
a−1 можно представить в виде следующих шагов.
На вход алгоритма подаются: числа a ÎZ и m ÎN, (a, m) = 1.
На выходе ожидается число
a-1 =1, m -1.
1. Ввод числа a, для которого необходимо найти обратный элемент a−1.
2. Ввод модуля m, нормирующего результат.
3. Если a = 0 или m = 0 или m = 1, то были заданы некорректные параметры, выход (пояснение: при a = 0 не существует обратного элемента, при m = 0 возникает ситуация деления на нуль; а при m = 1 всегда будет получаться результат, равный нулю, так как во множестве результатов
1, m - 1 будет существовать только один нулевой элемент).
4. Задаются вектора U = {u1, u2, u3}, V = {v1, v2, v3}. Производится начальная установка параметров значениями. Вектор U = {0, 1, m}; вектор V = {1, 0, a}.
5. Пока u3 ¹ 1 и u3 ¹ 0 и v3 ¹ 0 выполняются следующие действия (пояснение: при u3 = 1 результат будет получен в u1 (успешное завершение алгоритма); при v3 = 0 будет деление на нуль в пункте 5.а; если u3 = 0, то доказывается, что 2 числа a и m не являются взаимно простыми):
а) найти результат целочисленного деления числа u3 на v3: q = ]u3/v3[;
б) для " i = 1, 3
- находится значение выражения t = ui - vi · q;
- ui присваивается значение vi : ui = vi (присваивается значение переменной vi с предыдущего шага);
- vi присваивается новое значение: vi = t;
в) переход к пункту 5.
6. Если u3 ¹ 1, то обратный элемент не существует, выход.
7. Если u3 = 1, то в переменной u1 хранится значение обратного элемента a−1. Если u1 < 0, то осуществляется приведение результата к положительному числу: u1 = m + u1. Далее осуществляется вывод значения u1. Выход.
Примеры работы расширенного алгоритма Евклида.
Пример 2.5. Необходимо для числа a = 16 найти обратный элемент a−1
и нормировать результат числовым модулем m = 29.
Инициализируем векторы U и V: U = {0, 1, m = 29}, V = {1, 0, a = 16}.
Далее представим шаги алгоритма в виде трассировочной табл. 2.3.
Таблица 2.3. Трассировочная таблица
| Шаг, i | u3< >1 | u3< >0 | v3<> | Выход ? | q | u1 | u2 | u3 | v1 | v2 | v3 |
| До цикла | да | да | да | нет | - | m=2 | a=1 | ||||
| да | да | да | нет | -1 | |||||||
| да | да | да | нет | -1 | -1 | ||||||
| да | да | да | нет | -1 | -9 | ||||||
| да | да | да | нет | -9 | - | ||||||
| Итог: | нет | да | нет | да | - | m+u1=2 | - | - | - | - | - |
На четвертом шаге значение u3 стало равным 1. Тогда в u1 находится результат: u1 = -9. Нормируем результат: u1 = m + u1 = 29 – 9 = 20. Обратный элемент равен 20.
Проверка. (16·20) mod 29 должно быть равно 1.
(16·20) mod 29 = 320 mod 29 = (11·29 + 1) mod 29 =
= (11·29 mod 29 + 1 mod 29) mod 29 равно 1. Правильно.
Пример 2.6. Необходимо для числа a = 6 найти обратный элемент a−1 и нормировать результат числовым модулем m = 28. Рассмотрим этот пример, в предположении, что заранее неизвестно - является ли число m простым. Рассмотрим этот случай.
Таблица 2.4. Трассировочная таблица
| Шаг, i | u3< >1 | u3<> | v3<> | Выход ? | q | u1 | u2 | u3 | v1 | v2 | v3 |
| До цикла | да | да | да | нет | - | m=2 | a=6 | ||||
| да | да | да | нет | -4 | |||||||
| да | да | да | нет | -4 | -1 | ||||||
| да | да | да | нет | -1 | - | ||||||
| Итог: | да | да | нет | да | 2 / 0 = ? | значение a-1 не определено |
Отметим, что числа a = 6 и m = 28 не взаимно простые. Инициализируем векторы U и V: U={0, 1, m = 28}, V={1, 0, a = 6}. Далее представим шаги алгоритма в виде трассировочной табл. 2.4.
На третьем шаге значение переменной v3 стало равным 0. Из-за этого невозможно вычислить выражение q=]u3/v3[. В результате алгоритм завершается с выдачей уведомления, что для числа a = 6 и модуля m = 28 не существует элемента a-1.
Дополнительные примеры для решения (решите рассмотренными способами):
1) a = 7, m = 31. Найти a-1? (a-1=9)
2) a = 6, m = 29. Найти a-1? (a-1=5)
3) a = 8, m = 29. Найти a-1? (a-1=11)
Вопросы для самопроверки.
1. Какое предназначение расширенного алгоритма Евклида?
2. Что такое взаимно простые числа? Их примеры.
3. Что такое обратный элемент? Условия его существования.
4. Какие известны методы вычисления обратного элемента? Опишите их.
5. Как находится обратный элемент для некоторого числа?
6. Поясните работу расширенного алгоритма Евклида (РАЕ).
7. Какие ограничения накладываются на входные данные алгоритмов?
8. При каких условиях происходит выполнение алгоритмов?
9. При каких условиях происходит выход из алгоритма?
10. При каких условиях, в конце работы РАЕ, определяется, что был найден
обратный элемент? Что необходимо сделать, если обратный элемент оказался отрицательным числом?
11. Какие математические операции используются в алгоритмах?