МИНИСТЕРСТВО ЦИФРОВОГО РАЗВИТИЯ, СВЯЗИ И МАССОВЫХ КОММУНИКАЦИЙ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА»

(СПбГУТ)

Факультет Инфокоммуникационных сетей и систем

Кафедра Защищенных систем связи

Дисциплина Математические основы защиты информации

ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ №4

Расширенный алгоритм Евклида

10.03.01 Информационная безопасность

ФИО:

Группа:

Преподаватель: Кушнир Д.В.

Санкт-Петербург

Оглавление

Нахождение обратного элемента по модулю. 7

Теоретическая часть по исследуемому вопросу

Расширенный алгоритм Евклида

Кроме вычисления d=НОД(a,b), алгоритм Эвклида позволяет дополнительно определить два целых числа α и β, таких что:

α * a + β * b = d; (соотношение Безу)

α и β – коэффициенты Безу.

Замечание, «почти всегда» если α положительна, то β отрицательно и наоборот.

Эти два числа можно вычислять одновременно с выполнением шагов в алгоритме Эвклида по следующей схеме:

Ручной метод «прямой»:

Рассмотрим шаги получения НОД (24;15):

24 = 15 * 1 + 9

15 = 9 * 1 + 6

9 = 6 * 1 + 3

6 = 3 * 2 + 0

Добавим для каждого шага представление «текущего» остатка как линейной комбинации исходных чисел a и b:

9=24+(-1)*15

6=15-9=15-(24-15)=2*15+(-1)*24

3=9-6=24+(-1)*15-[2*15+(-1)*24]=2*24+(-3)*15; т.е. α=2; β=-3.

Алгоритм в общем виде: Найти: НОД(a,b) a =b *q₁ + r₁ и r₁ = α * x₁ + β * y₁ b =r₁ *q₂ + r₂ и r₂ = α * x₂ + β * y₂ ………………………………

r_n-3=r_n-2 *q_n-1 +r_n-1 и r_n-1= α * x_n-1 + β * y_n-1 //на этом шаге получаем α,β r_n-2=r_n-1 *q_n r_n=0 Ответ: НОД(a,b)=r_n-1 //ответ – последний ненулевой остаток.

Представим это в виде таблицы:

остатки	частные	x	y
a	*	x(-1)	y(-1)
b	*	x0	y0
r1	q1	x1	y1
r2	q2	X2	y2
rn-2	qn-2	xn-2	yn-2
rn-1	qn-1	xn-1	yn-1

Заметим, что в начале этой таблицы появились две дополнительные строчки.

Они нам помогут вычислить x₁ и y₁ : x_(-1)=1, y_(-1)=0, x₀=0, y₀=1; x_j=x_j-2-q_j*x_j-1; y_j=y_j-2-q_j*y_j-1; //Пояснение соотношений – см. лекции.

Пример расширенного алгоритма Эвклида для чисел 1234 и 54

остатки	частные	x	y
1234	*	1	0
54	*	0	1
46	22	1-22*0=1	0-22*1=-22
8	1	0-1*1=-1	1-1*(-22)=23
6	5	1-5*(-1)=6	-22-5*23=-137
2	1	-1-1*6=-7	23-1*(-137)=160
0	3	*	*

α = -7; β=160. Действительно: (-7)*1234+160*54=2.

Нахождение обратного элемента по модулю.

Определение. Обратным к числу a по модулю n называется такое число b (обычно обратное к a обозначают как a-1), что: a*b = 1 mod n ( a * a-1 = 1 mod n )

Рассмотрим выражение: a * х + n * y = 1 (это и есть соотношение Безу), возьмём от обеих частей уравнения остаток по модулю n, то получим:

a * х = 1 mod n, х – и есть обратный элемент к a.

Пример: m=11, a=3; 4*3+(-1)*11=1; 4*3=1 mod 11, т.е. a-1 = 4.

Если получаете отрицательный ответ – переведите в положительный: через n-х.

Нахождение противоположного элемента по модулю.

Определение. Противоположным к числу a по модулю n называется такое число b, что: a+b = 0 mod n. b записывают в виде положительного числа.

Задание

1. Выполнить «вручную» расширенный алгоритмом Эвклида.

2. Выполнить вычисление расширенного алгоритма Эвклида в среде Excel или в любой другой программной среде, которая позволяет выводить промежуточные шаги выполнения алгоритма.

3. Найти обратный элемент по модулю

Вариант 22.

Вручную - a = 20 b = 24 ; a = 3 n = 17, программно – a = 3198268 b = 4859598

Ход работы

1. Вручную найти НОД(24,20)

24 = 20 * 1 + 4 20 = 4 * 5 + 0

НОД(24,20) = 4

Добавим для каждого шага представление «текущего» остатка как линейной комбинации исходных числе а и b. Представим соотношение Безу.

x * a + y * b = d ; d = 4 a = 24 b = 20 x * 24 + y * 20 = 4

Из вычислений НОД получаем, что

4 = 24 + (-1) * 20 4 = 1 * 24 + (-1) * 20

Значит, x = 1; y = -1. Проверим, подставив в соотношение Безу.

1 * 24 + (-1) * 20 = 4 4 = 4, верно.

2. Выполнить вычисление в среде Excel. НОД(4859598, 3198268)

В Excel создадим таблицу с шапкой «A,B,Делится нацело, Остаток от деления» И заполним исходными данными.

В столбец «Делится нацело» введем формулу =ЦЕЛОЕ(A2/B2)

В столбец «Остаток от деления» введем формулу =ОСТАТ(A2;B2

В следующую строчку в столбцы А и В введем =B2 =D2 соответственно. Протянем все формулы вниз, до получения остатка от деления равному 0.

В данном случае, имеем НОД(4859598, 3198268) = 2 (т.к. последний остаток от деления)

Теперь найдем коэффициенты x,y для x*4859598 + y*3198268 = 2

Основывая на теоретическую часть вопроса, создадим следующую таблицу:

В третью строчку с данными введем следующие формулы: для х - =C2-B4*C3 для y - =D2-B4*D3 и протянем в конец таблицы. В результате получим следующие данные:

Проверим верность решения. =4859598*(-768585)+ 1167824*3198268 = 2 Верно.

3. Найти обратный элемент по модулю a = 3 n = 17 (модуль)

3^-1 mod 17 = x x*3+(-1)*17=1; x*3-17=11; x = 6; 6*3-17=18-17=1; 6*3= 1 mod 17; 3^-1=6