Информационная безопасность и защита информации: Конспект лекций. Будко В.Н. - 29 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Пример 1:
3
19
mod 15 = 3
19
— 15⋅Int(3
19
/15) = 1162261467 – 15⋅77484097= 12
19 = 16 + 2 + 1
3⋅9 = 27 mod 15 = 12
12⋅6 = 72 mod 15 = 12
Следствие : если x
a
mod N = 1, то и x
a⋅i
mod N = 1
Пример 2:
Общие формулы вычисления больших степеней.
a
b
mod N = (a⋅a⋅а ⋅… ⋅a (b раз) mod N) затем применяем формулу (9)
25. F(φ(x)) mod N = F(φ(x) mod N) mod N (13)
Проверка : N = 11, x = 5
φ(x) = x
2
φ(x) mod N = 5
2
mod 11 = 3 F(φ(x)) mod N = (10*25) mod 11 =
F(y) = 10y F(y) mod N = 10*3 mod 11 = 8
= 250 mod 11 = 8
26. Свойство коммутативности .
Обозначим x
a
mod N = F
a
(x), x
b
mod N = F
b
(x)
Будет верно тождество
F
a
(F
b
(x)) mod N = F
b
(F
a
(x)) mod N для всех x. (14)
Действительно :
F
a
(F
b
(x)) = (F
b
(x))
a
mod N = (x
b
mod N)
a
mod N = (см. формулу 13) = (x
b
)
a
mod N = x
ba
mod N
F
b
(F
a
(x)) = (F
a
(x))
b
mod N = (x
a
mod N)
b
mod N = (см. формулу 13) = (x
a
)
b
mod N = x
ab
mod N
но x
ba
= x
ab
следовательно и F
a
(F
b
(x)) = F
b
(F
a
(x))
27. Теорема Эвклида (300 г. до н.э.)
Если Е и М удовлетворяют условию 0 < EM и НОД(М ,Е) = 1, то существует единственное
число D, такое что 0 < D < M и
E*D ≡ 1 (mod M) ((E*D) mod M = 1) (15)
и кроме того D может быть вычислено с помощью расширения алгоритма Евклида при
нахождении HOD(M, Е). (Сравни Кнут Д. ”Искусство программирования, ” т. 1 стр . 26,
1976г.
Алгоритм Евклида при нахождении HOD (M,Е).
1 3 3
2 3
2
= 9 9
4 9
2
= 81 mod 15 = 6
8 6
2
= 36 mod 15 = 6
16
6
2
= 36 mod 15 = 6 6
Пример 1:
319 mod 15 = 319 — 15⋅Int(319/15) = 1162261467 – 15⋅77484097= 12
19 = 16 + 2 + 1
       1     3                             3
                 2
       2     3 =9                          9      3⋅9 = 27 mod 15 = 12
                 2
       4     9 = 81 mod 15 = 6
       8     62 = 36 mod 15 = 6
       16 62 = 36 mod 15 = 6               6      12⋅6 = 72 mod 15 = 12


Следствие: если xa mod N = 1, то и xa⋅i mod N = 1
Пример 2:
Общие формулы вычисления больших степеней.
ab mod N = (a⋅a⋅а⋅…⋅a (b раз) mod N) затем применяем формулу (9)


   25. F(φ(x)) mod N = F(φ(x) mod N) mod N                                                (13)
Проверка: N = 11, x = 5
φ(x) = x2            φ(x) mod N = 52 mod 11 = 3       F(φ(x)) mod N = (10*25) mod 11 =
F(y) = 10y           F(y) mod N = 10*3 mod 11 = 8 = 250 mod 11 = 8


   26. Свойство коммутативности.
Обозначим xa mod N = Fa(x), xb mod N = Fb(x)
Будет верно тождество
Fa(Fb(x)) mod N = Fb(Fa(x)) mod N для всех x.                                      (14)
       Действительно:
Fa(Fb(x)) = (Fb(x))a mod N = (xb mod N)a mod N = (см. формулу 13) = (xb)a mod N = xba mod N
Fb(Fa(x)) = (Fa(x))b mod N = (xa mod N)b mod N = (см. формулу 13) = (xa)b mod N = xab mod N
       но xba = xab следовательно и Fa(Fb(x)) = Fb(Fa(x))
   27. Теорема Эвклида (300 г. до н.э.)
Если Е и М удовлетворяют условию 0 < EM и НОД(М,Е) = 1, то существует единственное
число D, такое что 0 < D < M и
E*D ≡1 (mod M)              ((E*D) mod M = 1)                             (15)
и кроме того D может быть вычислено с помощью расширения алгоритма Евклида при
нахождении HOD(M, Е). (Сравни Кнут Д. ”Искусство программирования, ” т. 1 стр. 26,
1976г.
Алгоритм Евклида при нахождении HOD (M,Е).

Страницы