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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 2. Криптостойкость RSA. Алгоритмы факторизации 62
A B A mod B A div B y x
7 4 3 1 -1 2
4 3 1 1 1 -1
3 1 0 3 0 1
Таким образом, 7 ·(−1) + 4 ·2 = 1, или, 7 ·(−6) + 4 ·12 = 6. Положим,
x
0
= x = 12. Поскольку, d > 1, то корень X уравнения (3.32) определяется
с точностью до слагаемое (p − 1)/d = 7, т.е. имеет вид X = x
0
+ 7k , где
k ∈ Z. Будем подставлять в (3.32) последовательно числа 12, 19, 25, ..., пока
не получим тождество 3
25
mod 43 = 15. Задача решена.
Глава 2. Криптостойкость RSA. Алгоритмы факторизации                        62

       A B A mod B A div B y           x
       7   4      3         1      -1 2
       4   3      1         1      1 -1
       3   1      0         3      0   1
      Таким образом, 7 · (−1) + 4 · 2 = 1, или, 7 · (−6) + 4 · 12 = 6. Положим,
x0 = x = 12. Поскольку, d > 1, то корень X уравнения (3.32) определяется
с точностью до слагаемое (p − 1)/d = 7, т.е. имеет вид X = x0 + 7k , где
k ∈ Z. Будем подставлять в (3.32) последовательно числа 12, 19, 25, ..., пока
не получим тождество 325 mod 43 = 15. Задача решена.

Страницы