Школа естественных наук
 Скачать 23.33 Kb.
|
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Дальневосточный федеральный университет»
Криптографические методы защиты информации. Лабораторная работа №1. Алгоритмы вычисления наибольшего общего делителя. Бровко И.А Б8414 Алгоритмы вычисления наибольшего общего делителя. Цель работы – изучение алгоритмов вычисления наибольшего общего делителя целых чисел и анализ их быстродействия. Теоретические сведения: Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел. Алгоритм назван в честь греческого математика Евклида (III век до н. э.), который впервые описал его в VII и X книгах «Начал». Это один из старейших численных алгоритмов, используемых в наше время. В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары НОД – наибольший общий делитель. Алгоритм Евклида можно расширить для нахождения по заданным a и b таких целых x и y, что ax + by = d, где d – наибольший общий делитель a и b. Такой алгоритм носит название – Расширенный алгоритм Евклида. Бинарный алгоритм Евклида — метод нахождения наибольшего общего делителя двух целых чисел. Данный алгоритм быстрее обычного алгоритма Евклида, т.к. вместо медленных операций деления и умножения используются сдвиги. Бинарный алгоритм Евклида, также можно расширить для нахождения по заданным a и b таких целых x и y, что ax + by = d, где d – наибольший общий делитель a и b. Такой алгоритм носит название – Расширенный бинарный алгоритм Евклида. // Алгоритм Евклида.cpp: определяет точку входа для консольного приложения. // #include "stdafx.h" #include #include #include using namespace std; int main(int a, int b) { setlocale(LC_ALL, "Russian"); cout « "Алгоритм Евклида" « endl; cout « "Введите число а" « endl; cin » a; cout « "Введите число b" « endl; cin » b; LARGE_INTEGER t1, t2, f; QueryPerformanceCounter(&t1); while ((a != 0 & b != 0)) { if (a > b){ a = a%b; } else b = b%a; } cout «"НОД="« a + b « endl; //program QueryPerformanceCounter(&t2); QueryPerformanceFrequency(&f); double sec = double(t2.QuadPart - t1.QuadPart) / f.QuadPart; //cout « "скорость выполнения " « sec; } // бинарный алгорит Евклида.cpp: определяет точку входа для консольного приложения. // #include "stdafx.h" #include "stdafx.h" #include #include #include using namespace std; int main(int a, int b) { setlocale(LC_ALL, "Russian"); int g = 1, u, v; int d; cout « "Бинарный алгоритм Евклида" « endl; cout « "Введите число а" « endl; cin » a; cout « "Введите число b" « endl; cin » b; LARGE_INTEGER t1, t2, f; QueryPerformanceCounter(&t1); while (a % 2 == 0 & b % 2 == 0) { a = a / 2; b = b / 2; g = 2 * g; } u = a; v = b; while (u != 0) { while (u % 2 == 0) { u = u / 2; } while (v % 2 == 0) { v = v / 2; } if (u >= v) { u = u - v; } else { v = v - u; } } d = g*v; cout « "НОД= "« d « endl; //program QueryPerformanceCounter(&t2); QueryPerformanceFrequency(&f); double sec = double(t2.QuadPart - t1.QuadPart) / f.QuadPart; cout « "Время выполнения " « sec; } // Расширенный алгоритм Евклида.cpp: определяет точку входа для консольного приложения. // #include "stdafx.h" #include "stdafx.h" #include #include #include #include #include using namespace std; int main(int a, int b, int d) { setlocale(LC_ALL, "Russian"); cout « "Расширенный алгоритм Евклида" « endl; cout « "Введите число а" « endl; cin » a; cout « "Введите число b" « endl; cin » b; int x, y, q, r, A = 1, B = 0, C = 0, D = 1; while (b != 0) { q = a / b; r = a - (q * b); x = A - (q * C); y = B - (q * D); a = b; b = r; A = C; C = x; B = D; D = y; } d = a; x = A; y = B; cout « "x = " « x « ", y = " « y « ", НОД = " « d « endl; } // бинарный алгорит Евклида.cpp: определяет точку входа для консольного приложения. // #include "stdafx.h" #include "stdafx.h" #include #include #include #include #include using namespace std; int main(int a, int b) { setlocale(LC_ALL, "Russian"); cout « "Расширенный бинарный алгоритм Евклида" « endl; cout « "Введите число а" « endl; cin » a; cout « "Введите число b" « endl; cin » b; int g = 1, u, v, x, A = 1, B = 0, y, C = 0, D = 1, d, a2 = a, b2 = b; while (a % 2 == 0 & b % 2 == 0) { a = a / 2; b = b / 2; g = 2 * g; } u = a; v = b; while (u != 0) { while (u % 2 == 0) { u = u / 2; if (A % 2 == 0 && B % 2 == 0) { A = A / 2; B = B / 2; } else { A = (A + b) / 2; B = (B - a) / 2; } } while (v % 2 == 0) { v = v / 2; if (C % 2 == 0 && D % 2 == 0) { C = C / 2; D = D / 2; } else { C = (C + b) / 2; D = (D - a) / 2; } } if (u >= v) { u = u - v; A = A - C; B = B - D; } else { v = v - u; C = C - A; D = D - B; } } d = g*v; x = C; y = D; cout « "x = " « x « ", y = " « y « ", НОД = " « d « endl; } Анализ результата: В ходе работы был рассмотрен алгоритм Евклида нахождения наибольшего общего делителя, а также его модификации: бинарный алгоритм Евклида, расширенный алгоритм Евклида, бинарный расширенный алгоритм Евклида. Для проверки работоспособности и эффективности этих алгоритмов была написана программа на языке С++. Алгоритмы реализованы в виде отдельных программ, что позволяет тестировать как корректность их работы, так и быстродействие. Примеры работы алгоритмов
Вывод: в результате проделанной работы я изучил алгоритмы вычисления наибольшего общего делителя целых чисел. |