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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 1. Системы шифрования с открытым ключом 24
Третий столбец содержит остаток от деления A на B , а четвертый столбец
- целую часть от деления A на B .
Во второй части работы алгоритма к таблице добавляются два новых
столбца, озаглавленных x и y . Поместим в последнюю строчку столбцов
x и y значения 0 и 1. Затем, считая значения x
i+1
y
i+1
известными,
последовательно вычисляем значения x
i
и y
i
, i ≥ 0, по формулам:
x
i
= y
i+1
, y
i
= x
i+1
− y
i+1
· (A div B)
i
Пример. Решить уравнение 72x + 25y = 1. Помещаем в первую
строчку значения A = 72, B = 25. Вычисляем A mod B – остаток от деления
A на B , и [A /B] – целую часть от деления A на B . Потом переносим
значения B и A mod B на строчку вниз и на одну клетку влево. Повторяем
вычисления во второй строке. Продолжаем вычисления, пока значение в
столбце A mod B не станет равным 0. Тогда заносим в последнюю строчку
столбцов x и y значения 0 и 1, и ведем вычисление снизу вверх по формулам,
описанным выше.
A B A mod B [A/B] x y
72 25 22 2 8 -25
25 22 3 1 -7 8
22 3 1 7 1 -7
3 1 0 3 0 1
Ответ: Н.О.Д.(72, 25) = 1 – последнее значение в столбце B . Пара (x, y) =
(8, −25), дающая решение уравнению 72x + 25y = 1, берется из первой
строки таблицы.
Пример 2. Найти обратный элемент для e = 7 по составному модулю
φ(n) = 40 из примера параграфа 2.4.
Решение. Запустим расширенный алгоритм Евклида, взяв A =
φ(n) = 40 и B = e = 7. Получим:
Глава 1. Системы шифрования с открытым ключом                          24

Третий столбец содержит остаток от деления A на B , а четвертый столбец
- целую часть от деления A на B .
      Во второй части работы алгоритма к таблице добавляются два новых
столбца, озаглавленных x и y . Поместим в последнюю строчку столбцов
x и y значения 0 и 1. Затем, считая значения xi+1 yi+1 известными,
последовательно вычисляем значения xi и yi , i ≥ 0, по формулам:

             xi = yi+1 ,        yi = xi+1 − yi+1 · (A div B)i

      Пример. Решить уравнение 72x + 25y = 1. Помещаем в первую
строчку значения A = 72, B = 25. Вычисляем A mod B – остаток от деления
A на B , и [A /B] – целую часть от деления A на B . Потом переносим
значения B и A mod B на строчку вниз и на одну клетку влево. Повторяем
вычисления во второй строке. Продолжаем вычисления, пока значение в
столбце A mod B не станет равным 0. Тогда заносим в последнюю строчку
столбцов x и y значения 0 и 1, и ведем вычисление снизу вверх по формулам,
описанным выше.
        A        B   A mod B [A/B]           x     y
        72      25         22         2      8   -25
        25      22         3          1     -7    8
        22       3         1          7      1    -7
        3        1         0          3      0    1
Ответ: Н.О.Д.(72, 25) = 1 – последнее значение в столбце B . Пара (x, y) =
(8, −25), дающая решение уравнению 72x + 25y = 1, берется из первой
строки таблицы.

      Пример 2. Найти обратный элемент для e = 7 по составному модулю
φ(n) = 40 из примера параграфа 2.4.

      Решение. Запустим расширенный алгоритм Евклида, взяв A =
φ(n) = 40 и B = e = 7. Получим:

Страницы