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

UptoLike

ВУЗ: 

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

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

Рубрика: 

M
i
⋅ N
i
+ m
i
⋅ n
i
= 1, i = 1, 2, …, t.
Рассмотрим частный случай. Пусть M = m
1
⋅ m
2
, где m
1
, m
2
– взаимно
простые числа. Тогда для произвольных целых a
1
< m
1
и a
2
< m
2
существует единственное число x < M такое, что
N
1
⋅ M
1
≡ 1(mod m
1
) и N
2
⋅ M
2
≡ 1 (mod m
2
).
Здесь M
1
= M/m
1
= (m
1
⋅ m
2
)/m
1
= m
2
; M
2
= M/m
2
= m
1
.
Значение x вычисляют из соотношения
x = (a
1
⋅ N
1
⋅ M
1
+ a
2
⋅ N
2
⋅ M
2
)(mod M).
Пример VΙ [22]: решить систему из двух сравнений
x ≡ 1(mod 5), x ≡ 10(mod 11)
и найти общее решение x по модулю 55.
Здесь m
1
= 5; M = m
1
⋅ m
2
= 5 ⋅ 11 = 55; a
1
= 1; a
2
= 10;
M
1
= M/m
1
= m
2
= 11; M
2
= M/m
2
= m
1
= 5.
Найдём значения N
1
и N
2
, обратные к M
1
и M
2
соответственно по
mod m
1
и mod m
2
:
M
1
⋅ N
1
≡ 1(mod m
1
), 11 ⋅ N
1
≡ 1(mod 5) ⇒N
1
= 1,
M
2
⋅ N
2
≡ 1 (mod m
2
), 5 ⋅ N
2
≡ 1(mod 11) ⇒ 9.
Вычислим общее значение
x = (a
1
M
1
N
1
+ a
2
M
2
N
2
)(mod M) = (1 ⋅ 11 ⋅ 1 + 10 ⋅ 5 ⋅ 9)(mod 55) = (11 +
450)(mod 55) = 461(mod 55) = 21 (mod 55).
Итак, x = 21(mod 55), x = 21.
П.4. Вычисления в конечных полях Галуа
В поле Галуа [18, 19] определены операции сложения, вычитания,
умножения и деления на ненулевые элементы. Существует
единичный элемент сложения - 0, и умножения - I. Для каждого
ненулевого числа существует единственное обратное число.
Выполняются коммутативный, ассоциативный и дистрибутивный
законы.
Конечное поле F(p) с конечным числом p элементов играет
важную роль в криптографии. В общем случае число элементов
определяется как p = q
n
, где q – некоторое простое число и n ≥ 1.
160

Страницы