📄Работа №77616
Тема: АНАЛИЗ И РЕАЛИЗАЦИЯ АЛГОРИТМА ЕВКЛИДА ВЫЧИСЛЕНИЯ НОД В МУЛЬТИПРОЦЕССОРНЫХ СИСТЕМАХ
Тип работы
Дипломные работы, ВКР
Предмет
информационная безопасность
Объем:
22 листов
Год:
2017
Просмотров:
323
4360
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
ВВЕДЕНИЕ 3
1. КРАТКИЙ ОБЗОР ОСНОВНЫХ АЛГОРИТМОВ ВЫЧИСЛЕНИЯ НОД 4
1.1 Алгоритм Евклида 4
1.2 Улучшение алгоритма Евклида по Леммеру 5
1.3 Бинарный алгоритм Евклида 7
2. К-АРНЫЙ АЛГОРИТМ ЕВКЛИДА 9
2.1 Классический к-арный алгоритм 9
2.2 Аппроксимирующий к-арный алгоритм 11
2.2.1 Описание алгоритма 11
2.2.2 Рассмотрение примера 13
2.2.3 Анализ алгоритма 14
2.2.4 Параллельное вычисление 15
3. ПРАКТИЧЕСКИЕ РЕЗУЛЬТАТЫ 17
ЗАКЛЮЧЕНИЕ 21
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 22
Приложения должны быть в работе, но в данный момент отсутствуют
1. КРАТКИЙ ОБЗОР ОСНОВНЫХ АЛГОРИТМОВ ВЫЧИСЛЕНИЯ НОД 4
1.1 Алгоритм Евклида 4
1.2 Улучшение алгоритма Евклида по Леммеру 5
1.3 Бинарный алгоритм Евклида 7
2. К-АРНЫЙ АЛГОРИТМ ЕВКЛИДА 9
2.1 Классический к-арный алгоритм 9
2.2 Аппроксимирующий к-арный алгоритм 11
2.2.1 Описание алгоритма 11
2.2.2 Рассмотрение примера 13
2.2.3 Анализ алгоритма 14
2.2.4 Параллельное вычисление 15
3. ПРАКТИЧЕСКИЕ РЕЗУЛЬТАТЫ 17
ЗАКЛЮЧЕНИЕ 21
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 22
Приложения должны быть в работе, но в данный момент отсутствуют
📖 Введение
Вычисление НОД для двух натуральных чисел на сегодняшний день имеет высокое значение в математике, как и шифрование информации является одной из важнейших задач в области безопасности при передачи данных. Существующие методы шифрования, например схема RSA [1] (это название является аббревиатурой фамилий его создателей - Rivest, Shamir и Aldeman), схема Эль-Гамаля, или шифрование на основе эллиптических кривых, в той или иной степени используют вычисление обратного элемента в конечном поле, что напрямую связано с задачей нахождения НОД двух натуральных чисел.
Вместе с приходом многопроцессорных компьютеров появилась возможность реализации множества математических алгоритмов, используя параллельные вычисления.
В настоящее время не существует полностью реализованного алгоритма Евклида с использованием параллельного вычисления. В данной работе будут рассмотрены основные вариации алгоритма Евклида, а так же практическая реализация с учетом мультипроцессорности.
Целью данной работы является получение увеличения скорости выполнения вычисления НОД для больших чисел путем распараллеливания алгоритма.
Задачи данной работы определяются поставленной целью: рассмотреть методику вычисления НОД при помощи алгоритма Евклида, рассмотреть возможные улучшения для алгоритма и их распараллеливание, программно реализовать параллельное вычисление НОД.
Вместе с приходом многопроцессорных компьютеров появилась возможность реализации множества математических алгоритмов, используя параллельные вычисления.
В настоящее время не существует полностью реализованного алгоритма Евклида с использованием параллельного вычисления. В данной работе будут рассмотрены основные вариации алгоритма Евклида, а так же практическая реализация с учетом мультипроцессорности.
Целью данной работы является получение увеличения скорости выполнения вычисления НОД для больших чисел путем распараллеливания алгоритма.
Задачи данной работы определяются поставленной целью: рассмотреть методику вычисления НОД при помощи алгоритма Евклида, рассмотреть возможные улучшения для алгоритма и их распараллеливание, программно реализовать параллельное вычисление НОД.
✅ Заключение
В данной работе были рассмотрены различные алгоритмы поиска НОД двух чисел и были реализованы классический алгоритм Евклида, бинарный алгоритм Евклида а так же удалось распараллелить к-арный алгоритм Евклида. Полученные результаты в ходе практической реализации подтвердили теорию о возможности получения улучшения по времени выполнения при помощи модификаций классического алгоритма Евклида, но они отличались от теоретических. Так, например, теоретическая разница параллельного применения к-арного алгоритма с классическим алгоритмом Евклида составляла порядка 450%, однако, на практике мы получили улучшение результата лишь на 190%. Считаю, что это по большей части обусловлено самим алгоритмом, так как он основан на определенной вероятности и числах, которые могут быть заведомо нам известны, однако есть и результаты, которые дают плохие данные по времени выполнения.
Также хотелось бы отметить, что для к-арного алгоритма использование разница по параметру k оказалась не сильно заметна, так как мы получили некое ускорение, перейдя с параметра k = 64 к k =256, однако, при следующем увеличении с k = 256 до k = 1024 время выполнения вновь увеличилось, поэтому на практике не удалось получить увеличение времени выполнения с увеличением параметра k.
Также хотелось бы отметить, что для к-арного алгоритма использование разница по параметру k оказалась не сильно заметна, так как мы получили некое ускорение, перейдя с параметра k = 64 к k =256, однако, при следующем увеличении с k = 256 до k = 1024 время выполнения вновь увеличилось, поэтому на практике не удалось получить увеличение времени выполнения с увеличением параметра k.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.