Математические основы защиты информации. Ишмухаметов Ш.Т - 44 стр.

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

45
Пример. Найти наименьшее положительное x, удовлетворяющее
системе уравнение:
x ≡ 2 ( mod 3 )
x ≡ 5 ( mod 7 )
x ≡ 4 ( mod 11 ).
Решение. В нашем примере m
1
= 3, m
2
= 7, m
3
= 11, r
1
= 2, r
2
=
5, r
3
= 4. Будем вычислять последовательно y
i
и x
i
, i = 1, 2, 3:
y
1
= x
1
= 2,
y
2
= (r
2
− x
1
) · (m
1
)
−1
mod m
2
= (5 − 2) · (3)
−1
mod 7 = 1
x
2
= x
1
+ (y
2
· m
1
mod m
2
) = 2 + (1 · 3 mod 7) = 5,
y
3
= (r
3
− x
2
) · (m
1
· m
2
)
−1
mod m
3
= (4 − 5) · 21
−1
mod 11 = 1,
x
3
= x
2
+ y
3
· m
1
· m
2
= 5 + 1 · 3 · 7 = 26.
Ответ: x = 26.
                                                                       45

      Пример. Найти наименьшее положительное x, удовлетворяющее
системе уравнение:
          
          
           x ≡ 2 ( mod 3 )
          
            x ≡ 5 ( mod 7 )
          
          
           x ≡ 4 ( mod 11 ).

      Решение. В нашем примере m1 = 3, m2 = 7, m3 = 11, r1 = 2, r2 =
5, r3 = 4. Будем вычислять последовательно yi и xi , i = 1, 2, 3:
  y1 = x1 = 2,
  y2 = (r2 − x1 ) · (m1 )−1 mod m2 = (5 − 2) · (3)−1 mod 7 = 1
  x2 = x1 + (y2 · m1 mod m2 ) = 2 + (1 · 3 mod 7) = 5,
  y3 = (r3 − x2 ) · (m1 · m2 )−1 mod m3 = (4 − 5) · 21−1 mod 11 = 1,
  x3 = x2 + y3 · m1 · m2 = 5 + 1 · 3 · 7 = 26.

Ответ: x = 26.

Страницы