Методы и средства защиты компьютерной информации. Хамидуллин Р.Р - 157 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

a ⋅ t
1
+ b ⋅ t
2
= t
3
, a ⋅ u
1
+ b ⋅ u
2
= u
3
, a ⋅ v
1
+ b ⋅ v
2
= v
3
.
Если использовать частный режим работы РАЕ, при котором
b = n, НОД (a, n) = 1 и u
3
= 1, то обратная величина a
-1
(mod n)
определяется из следующего сравнения:
a ⋅ u
1
+ n ⋅ u
2
= НОД (a, n) = 1,
(a ⋅ u
1
+ n ⋅ u
2
) mod n ≡ a ⋅ u
1
(mod n) ≡ 1,
a
-1
(mod n) ≡ u
1
(mod n).
Для решения более сложных сравнений a ⋅ x ≡ b (mod n), b ≠ 1
используется следующий алгоритм. Сначала решают сравнение
a ⋅ y ≡ 1 (mod n), т.е. определяют y = a
-1
(mod n), а затем находят
x = a
-1
⋅
b (mod n) = y ⋅ b (mod n).
Пример V [6, 14]. Найти x для сравнения 5 ⋅ x ≡ 9(mod 23).
Сначала решаем сравнение 5 ⋅ x ≡ 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
П.3. Китайская теорема об остатках
Китайская теорема об остатках [1,22] формулируется следующим
образом.
Если m
1
, m
2
, …, m
t
– модули, которые являются попарно взаимно
простыми целыми числами, то есть. НОД (m
i
, m
j
) = 1 при i ≠ j, то
сравнения x ≡ a
i
(mod m
i
), i= 1, 2,…,t имеют в интервале [0, M-1]
единственное общее решение
()
MMNax
iii
t
i
mod
1
⋅⋅=
∑
=
,
где
M = m
1
⋅ m
2
⋅ … ⋅ m
t
– произведение всех m; N
i
- обратный элемент к
M
i
(mod m
i
), i = 1, 2, …, t, то есть M
i
⋅ N
i
≡ 1(mod m
i
); a
1
, a
2
,…,a
t
–целые
числа , 0 ≤ a
i
≤ m
i
;
M
i
= M/m
i
.
Так как НОД (M
i
, m
i
) = 1, то обратный элемент N
i
существует и легко
находится с помощью алгоритма Евклида из соотношения
159

Страницы