Нахождение наибольшего общего делителя НОД

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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ

ИМ. ПРОФ. М. А. БОНЧ-БРУЕВИЧА

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

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

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

Отчет по лабораторной работе №3

«Нахождение наибольшего общего делителя НОД()»

Выполнили студенты гр. ИКБ-93:

Елизарова Л. Р.

Киселёв Д. О.

Новиков А. А.

Проверил:

                                                             доц. Кушнир Д.В.

В криптографии важную роль играет теория чисел.

Некоторые задачи из теории чисел, используемые при построении криптографических преобразований.

Необходимо выбрать свой вариант (варианты) (вариант определяется номером студента в списке группы, если в бригаде несколько человек, то необходимо выполнить соответствующее число соответствующих вариантов).

Варианты 9, 12 и 19.

Задание 1. Вычисление НОД(a,b) алгоритмом Эвклида «вручную».

Алгоритм Эвклида в общем виде:
Найти: НОД(a,b)

a   = b     *q1  + r1          0≤ri<b         //q1-целое,r1-остаток от деления a на b *
b   = r1    *q2  + r2          0≤r2<r1
………………………………

rn-3= rn-2  *qn-1+rn-1
rn-2= rn-1  *qn        +0 rn=0

Ответ: НОД(a,b)=rn-1            //ответ – последний ненулевой остаток.

* Примечание: в выражении a=b  *q1 + r1 имеется ввиду, что производится деление числа а на b и вычисляется остаток r1 и количество целых q1.

Найти: НОД (88,26), НОД (52,18), НОД (56,22).

1. Вариант 9

НОД(88,26)

Промежуточные шаги выполнения:
88 = 26 * 3 + 10
26 = 10 * 2 + 6

10 = 6  * 1 + 4
6 = 4  * 1 + 2

 4 = 2  * 2 + 0
Последний ненулевой остаток 2, т.е. НОД (88,26) = 2.

1. Вариант 12

НОД(52,18)

Промежуточные шаги выполнения:
52 = 18 * 2 + 16
18 = 16 * 1 + 2

16 = 2  * 8 + 0
Последний ненулевой остаток 2, т.е. НОД (52,18) = 2.

1. Вариант 19

НОД(56,22)

Промежуточные шаги выполнения:
56 = 22 * 2 + 12
22 = 12 * 1 + 10

12 = 10 * 1 + 2
10 = 2  * 5 + 0
Последний ненулевой остаток 2, т.е. НОД (56,22) = 2.

Итоговый результат выполнения задания:

НОД (88,26) = 2, НОД (52,18) = 2, НОД (56,22) = 2.

Задание 2. Вычисление НОД(a,b) алгоритмом Эвклида в среде Excel (в ячейках таблицы).

Формализованное описание алгоритма Эвклида:

Алгоритм НОД(a,b) a>b

Начальные присвоения A=a; R=B=b;

В цикле выполняем:[pic 1]

a) R=остаток от деления A на B;

IF(R=0) B – ответ[pic 2]

b) A=B;

c) B=R;

Пример НОД(24;15)

Найти: НОД (5949114,3941396), НОД (1520081,1500329),

НОД (854779,851189).