Составители:
Рубрика:
50
так как
.4
5
11191
=
+
⋅
=
+
⋅
=
A
kN
B
Обратная же величина для чисел A=2 и N=14 не имеет решения, так как
НОД (A, N)=2≠1
Действительно, при любом положительном целом числе k, величина B
будет дробным числом, что недопустимо.
Существуют три способа нахождения обратной величины.
1. Проверка всех значений величины B в диапазоне от 1 до (n-1), пока не
будет найдено искомое значение (способ перебора значений В).
2. Выполнение операции приведения обратного числа A по модулю N с
участием функции Эйлера.
3. Выполнение операции приведения обратного числа A по модулю N с
использованием расширенного алгоритма Евклида.
Пример 13.7. Найти значение В в выражении
B=A
-1
(mod N)
или
B
⋅
A≡1 (mod N)
при А=5 и N=7.
Используется первый способ.
Для данного примера наибольший общий делитель равен единице
НОД (A, N)=1
и значение B лежит в пределах от 1 до (N-1)=(7-1)=6.
Все возможные варианты решений сведены в табл. 13.1.
Страницы
- « первая
- ‹ предыдущая
- …
- 48
- 49
- 50
- 51
- 52
- …
- следующая ›
- последняя »
