Лаб_03
.docxФедеральное государственное бюджетное образовательное учреждение высшего образования «Санкт-Петербургский государственный университет телекоммуникаций им. проф. М.А.Бонч-Бруевича»
Отчёт по лабораторной работе №3
«Расширенный алгоритм Эвклида»
Выполнил:
студент группы ИКБ-14
Травкина Е.А.
Проверил:
Доц., к.т.н., Кушнир Д.В.
Санкт-Петербург
2023
Теоретическая часть
Кроме вычисления 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:
1-й шаг: 9=24+(-1)*15
2-й шаг: 6=15-9=15-(24-15)=2*15+(-1)*24
3-й шаг: 3=9-6=24+(-1)*15-[2*15+(-1)*24]=2*24+(-3)*15; т.е. α=2; β=-3.
Алгоритм в общем виде: Найти: НОД(a,b) a =b *q1 + r1 и r1 = α * x1 + β * y1 b =r1 *q2 + r2 и r2 = α * x2 + β * y2 ………………………………
rn-3=rn-2 *qn-1 +rn-1 и rn-1= α * xn-1 + β * yn-1 //на этом шаге получаем α,β rn-2=rn-1 *qn rn=0 Ответ: НОД(a,b)=rn-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 |
Заметим, что в начале этой таблицы появились две дополнительные строчки.
Они нам помогут вычислить x1 и y1 :
x(-1)=1, y(-1)=0, x0=0, y0=1;
xj=xj-2-qj*xj-1; yj=yj-2-qj*yj-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 записывают в виде положительного числа.
Факультативное задание. Расширенный бинарный алгоритм Евклида
Вход: Целые числа а, b; 0 < b ≤ а.
Выход: d = НОД(a, b); и такие целые числа х, у, что ах + by = d.
Алгоритм:
Положить g ← 1.
Пока оба числа а и b четные, выполнять а ← a/2, b ← b/2 , g ← 2g до получения хотя бы одного нечетного значения а или b.
Положить u ← a, v ← b, А ← 1, В ← 0, С ← 0, D ← 1.
Пока u ≠ 0, выполнять следующие действия:
Пока u четное, положить u ← u/2. Если оба числа А и B четные, то положить A ← A/2, B ← B/2. В противном случае положить A ← (A+b)/2, B ← (B–a)/2
Пока v четное, положить v ← v/2.
Если оба числа С и D четные, то положить С ← C/2, D ← D/2. В противном случае положить C ← (C + b)/2, D ← (D – a)/2
При u ≥ v положить u ← u – v, А ← А – С, В ← В – D. В противном случае положить v ← v – u, C ← C–A, D ← D – B.
Если u=0, то
Положить d ← gv, x ← С, у ← D.
Результат: d, х, у.
Задание
Вычислить коэффициенты соотношения Безу для НОД(34, 40) вручную.
Вычислить коэффициенты соотношения Безу для НОД(2264828, 4261494) программными средствами.
Найти обратное к 4 по модулю 17.
Ход работы
«Вручную» расширенный алгоритм Эвклида
НОД (34, 40):
40 = 34 * 1 + 6
34 = 6 * 5 + 4
6 = 4 * 1 + 2
4 = 2 * 2 + 0
Распишем остатки в виде линейных комбинаций:
6 = 40 - 34
4 = 34 - 6 * 5 = 34 – 5 * (40 – 34) = 34 * 6 – 5 * 40
2 = 6 – 4 = 6 – 1 * (34 *6 – 5 * 40) = 6 * 40 - 7 * 34
Ответ: (6, -7)
Проверка: 6 * 40 - 7 * 34 = 240 - 238 = 2.
Выполнение алгоритма Эвклида в среде Excel и нахождение коэф. Безу (Рис. 1, 2)
Рис. 1. Код программы
Рис. 2. Вывод программы
НОД (4, 17) = 1 Коэффициенты Безу: (-4, 1) - 4 * 4 + 1* 17 = 1 Берём по модулю 16 4 * 4 = 1 mod 17 Обратное к 4 по модулю 17 : 13
|
|
Вывод:
В ходе лабораторной работы № 3 мы научились вычислять коэффициенты соотношения Безу для НОД вручную, вычислять коэффициенты соотношения Безу для НОД в среде разработки Python, находить обратное к числу по модулю.