Составители:
Рубрика:
49
В криптосистемах особое место занимают дискретные логарифмы с
обратными величинами.
В арифметике действительных чисел обратную величину обозначают как
A
A
1
1
=
−
.
Выражение математической операции приведения обратного числа А
-1
по
модулю N в этом случае примет вид
А
-1
≡
B (mod N)
или
)(mod
1
NB
A
≡
или
B
⋅
A (mod N)=1.
В криптосистемах чаще задача сводится к нахождению B из выражения
А
-1
≡
B (mod N),
которое эквивалентно нахождению таких зависимостей B и k, что
k
N
BA
=
−
⋅
1
.
Не всегда существует решение операции приведения обратного числа A
по модулю N. Решение существует если A и N взаимно простые числа, т.е. эти
два числа имеют наибольший общий делитель (НОД) равный лишь единице
НОД (A, N)=1,
а значение B заключено в пределах от 1 до (N-1).
Пример 13.6. Обратная величина для чисел A=5 и N=19 имеет решение
B=4.
Действительно, подставив в выражение
В
⋅
А (mod N)=1,
значения A=5 и N=19 получим
(4⋅5) (mod N)=20 (mod 19)=1,
Страницы
- « первая
- ‹ предыдущая
- …
- 47
- 48
- 49
- 50
- 51
- …
- следующая ›
- последняя »
