МОЗИ 4 семестр / Лабораторная 3 / ЗАДАНИЕ_МОЗИ_Лаб_03_(Алгоритм_Эвклида_обычный_и_бинарный)
.docЛабораторная/практика №3
Нахождения наибольшего общего делителя НОД().
В криптографии важную роль играет теория чисел.
Некоторые задачи из теории чисел, используемые при построении криптографических преобразований:
I. Нахождение наибольшего общего делителя чисел a и b: НОД(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.
Пример НОД(1234,54) 1234 = 54 *22 +46 54 = 46 * 1 + 8 46 = 8 * 5 + 6 8 = 6 * 1 + 2 6 = 2 * 3 + 0 Последний ненулевой остаток 2, т.е. НОД (1234,54)=2
Формализованное описание алгоритма Эвклида:
Алгоритм НОД(a,b) a>b
Начальные присвоения A=a; R=B=b;
В цикле выполняем:
a) R=остаток от деления A на B;
I F(R=0) B – ответ
b) A=B;
c) B=R;
Пример НОД(24;15)
A |
|
B |
|
q |
|
R |
24 |
|
15 |
|
|
|
|
24 |
= |
15 |
* |
1 |
+ |
9 |
15 |
= |
9 |
* |
1 |
+ |
6 |
9 |
= |
6 |
* |
1 |
+ |
3 |
6 |
= |
3 |
* |
2 |
+ |
0 |
Бинарный алгоритм Евклида
Бинарный алгоритм Евклида вычисления НОД оказывается более быстрым при реализации этого алгоритма на компьютере, поскольку использует двоичное представление чисел а и b.
Бинарный алгоритм Евклида основан на следующих свойствах наибольшего общего делителя (считаем, что 0 < b ≤ а):
если оба числа а и b четные, то НОД(a,b) = 2 · НОД(a/2 , b/2)
если число а нечетное, число b четное, то НОД(a, b) = НОД(а, b/2);
если оба числа а и b нечетные, а > b, то НОД(а, b) = НОД(а – b, b);
если а = b, то НОД(а, b) = а.
Формализованное описание алгоритма Бинарного алгоритма Евклида.
Вход: Целые числа a, b; 0 < b ≤ а.
Выход. d = HOД(a,b).
Положить g ← 1.
Пока оба числа а и b четные, выполнять а← a/2 , b ← b/2, g ← 2g до получения хотя бы одного нечетного значения а или b.
Положить u ← a, v ← b.
Пока u ≠ 0, выполнять следующие действия.
4.1. Пока u четное, полагать u ← u/2.
4.2. Пока v четное, полагать v ← v/2.
4.3. При u ≥ v положить: u ← u–v, в противном случае: v ← v–u.
Положить d ← gv.
Результат: d. Р
Пример («ручное» вычисление): НОД(88,52)
НОД(88,52) = 2*НОД(44,26) = 4*НОД(22,13) = 4*НОД(11,13) =
= 4*НОД(13-11,11) = 4*НОД(2,11) = 4*НОД(11-2,2) = 4*НОД(9,2) =
= 4*НОД(9-2,2) = 4*НОД(7,2) = 4*НОД(5,2) = 4*НОД(5-2,2) = 4*НОД(3,2) =
= 4*НОД(3-2,2) = 4*НОД(1,2) = 4*НОД(2-1,1)=4*НОД(1,1)=4
Задание.
Необходимо выбрать свой вариант (варианты) (вариант определяется номером студента в списке группы, если в бригаде несколько человек, то необходимо выполнить соответствующее число соответствующих вариантов).
Выполнить «вручную» вычисление НОД(a,b) алгоритмом Эвклида.
Выполнить вычисление НОД(a,b) алгоритмом Эвклида в среде Excel (в ячейках таблицы) или в любой другой программной среде, которая позволяет выводить промежуточные шаги выполнения алгоритма.
Выполнить «вручную» вычисление НОД(a,b) бинарным алгоритмом Эвклида.
Выполнить вычисление НОД(a,b) бинарным алгоритмом Эвклида в среде Excel или в любой другой программной среде, которая позволяет выводить промежуточные шаги выполнения алгоритма.
Номер |
НОД(a,b) (для «ручного» выполнения) |
НОД(a,b) (для «программного» выполнения) |
||
|
a |
b |
a |
b |
1 |
22 |
28 |
558412 |
282494 |
2 |
44 |
20 |
830468 |
417526 |
3 |
26 |
44 |
1111492 |
564422 |
4 |
20 |
12 |
1509212 |
759518 |
5 |
34 |
20 |
1903996 |
956402 |
6 |
18 |
52 |
2380844 |
3643674 |
7 |
22 |
56 |
2830444 |
4298262 |
8 |
44 |
40 |
3429796 |
5212254 |
9 |
26 |
88 |
3941396 |
5949114 |
10 |
20 |
24 |
1125851 |
1129913 |
11 |
34 |
40 |
1307491 |
1316503 |
12 |
18 |
52 |
1500329 |
1520081 |
13 |
22 |
28 |
1678583 |
1689179 |
14 |
44 |
20 |
1927231 |
1933033 |
15 |
26 |
44 |
1081012 |
545222 |
16 |
20 |
12 |
1542844 |
775042 |
17 |
34 |
20 |
2123276 |
1070242 |
18 |
18 |
52 |
2687396 |
1353074 |
19 |
22 |
56 |
851189 |
854779 |
20 |
44 |
40 |
1025977 |
1030187 |
21 |
26 |
88 |
3239732 |
4877454 |
22 |
20 |
24 |
3198268 |
4859598 |
23 |
34 |
40 |
2264828 |
4261494 |
24 |
18 |
52 |
2861708 |
3438222 |
25 |
22 |
28 |
2992324 |
4900326 |
Отчет.
Содержание отчёта:
Стандартный титульный лист.
Теория по исследуемому вопросу (достаточно использовать материалы задания самой лабораторной работы).
Формулировка задание на вычисления.
Шаги выполнения вычисления.
Проверку правильности найденных решений, если применимо (для алгоритма Эвклида можно пропустить).
При выполнении заданий с помощью программирования в какой-либо среде – приводить программный код или указывать используемые формулы в соответствующей среде (например, формулы в ячейках Excel) и приводить вывод всех промежуточных шагов алгоритма. По программному коду в средах отличных от Excel возможны дополнительные вопросы с предложением внести изменения в порядок вычисления отдельных переменных или способ вывода промежуточных результатов.