📄Работа №77183
Тема: Алгоритмы вычисления наибольшего общего делителя
Характеристики работы
Тип работы
Дипломные работы, ВКР
Предмет
Информатика и вычислительная техника
Объем:
47 листов
Год:
2017
Просмотров:
372
4320
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
ВВЕДЕНИЕ 3
1. ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ 4
1.1. Определение НОД 4
1.2. Бинарный алгоритм Евклида нахождения НОД 4
1.3. k-арный алгоритм Евклида нахождения НОД 5
1.4. Комбинированный алгоритм Джебелеана-Вебера нахождения НОД 7
Постановка задачи 10
2. РАЗРАБОТКА ПРОГРАММЫ 11
2.1. Средства реализации 11
2.2 Реализация алгоритма 11
2.2.1 Сравнение алгоритмов нахождения НОД и исследование алгоритма
Джебелеана-Вебера 11
2.2.2 Общие выводы по работе алгоритмов 15
3. РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ 16
3.1. Исследование алгоритмов 16
3.1.1 Сравнения, проводимые внутри алгоритмов 16
3.1.2 Сравнение алгоритмов между собой 21
3.2. Зависимость производительности алгоритма Джебелеана-Вебера от
параметра s 25
ЗАКЛЮЧЕНИЕ 28
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 29
ПРИЛОЖЕНИЕ
1. ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ 4
1.1. Определение НОД 4
1.2. Бинарный алгоритм Евклида нахождения НОД 4
1.3. k-арный алгоритм Евклида нахождения НОД 5
1.4. Комбинированный алгоритм Джебелеана-Вебера нахождения НОД 7
Постановка задачи 10
2. РАЗРАБОТКА ПРОГРАММЫ 11
2.1. Средства реализации 11
2.2 Реализация алгоритма 11
2.2.1 Сравнение алгоритмов нахождения НОД и исследование алгоритма
Джебелеана-Вебера 11
2.2.2 Общие выводы по работе алгоритмов 15
3. РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ 16
3.1. Исследование алгоритмов 16
3.1.1 Сравнения, проводимые внутри алгоритмов 16
3.1.2 Сравнение алгоритмов между собой 21
3.2. Зависимость производительности алгоритма Джебелеана-Вебера от
параметра s 25
ЗАКЛЮЧЕНИЕ 28
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 29
ПРИЛОЖЕНИЕ
📖 Введение
В современном мире - в век информационных технологий, информация для нас является одной из самых ценных вещей. С развитием мощных компьютеров, глобальных компьютерных сетей, да и информационных технологий, в общем, проблема защиты информации является весьма актуальной.
И решением как раз таких проблем занимается криптография.
Криптография - это одна из древнейших наук, которая занимается обеспечением безопасности данных.
Одной из немаловажных тематик изучения криптографических методов защиты информации является нахождение наибольшего общего делителя для целых чисел. Все потому что, многие криптосистемы основываются на вычисли-тельной сложности задачи факторизации. Ну а во многих алгоритмах факторизации, в свою очередь, присутствует задача нахождения наибольшего делителя. Примером таких алгоритмов является ро-алгоритм Полларда, Полларда- Штрассена, метод Лемана, метод непрерывных дробей и т.д.
Одним из эффективных алгоритмов для нахождения наибольшего общего делителя для целых чисел является Алгоритм Евклида.
Алгоритм назван в честь греческого математика Евклида, который описал его в своих книгах около 300 лет назад до н.э. Не смотря на то, что Алгоритм Евклида является одной из старейших численных алгоритмов, для него и в наше время существует множество теоретических и практических применений. В частности, он является основой для криптографического алгоритма с открытым ключом RSA, широко распространённого в электронной коммерции.
И решением как раз таких проблем занимается криптография.
Криптография - это одна из древнейших наук, которая занимается обеспечением безопасности данных.
Одной из немаловажных тематик изучения криптографических методов защиты информации является нахождение наибольшего общего делителя для целых чисел. Все потому что, многие криптосистемы основываются на вычисли-тельной сложности задачи факторизации. Ну а во многих алгоритмах факторизации, в свою очередь, присутствует задача нахождения наибольшего делителя. Примером таких алгоритмов является ро-алгоритм Полларда, Полларда- Штрассена, метод Лемана, метод непрерывных дробей и т.д.
Одним из эффективных алгоритмов для нахождения наибольшего общего делителя для целых чисел является Алгоритм Евклида.
Алгоритм назван в честь греческого математика Евклида, который описал его в своих книгах около 300 лет назад до н.э. Не смотря на то, что Алгоритм Евклида является одной из старейших численных алгоритмов, для него и в наше время существует множество теоретических и практических применений. В частности, он является основой для криптографического алгоритма с открытым ключом RSA, широко распространённого в электронной коммерции.
✅ Заключение
В ходе исследования установлено, что каждый из изучаемых алгоритмов работает дольше, когда требуется найти НОД двух чисел схожей длины, чем когда эти числа имеют заметно различную размерность. Также удалось установить, что алгоритмы работают гораздо дольше, если числа взаимно простые, чем когда НОД двух чисел отличен от единицы.
По итогам сравнения оказалось, что алгоритм Джебелеана-Вебера является лучшим из изучаемых по количеству проведенных итераций. Но время работы алгоритма для любых пар используемых в работе чисел меньше у бинарного алгоритма гораздо меньше первого за счет менее весомых операций, проводимых на каждой итерации алгоритма.
Несмотря на это, алгоритм Джебелеана-Вебера, наряду с бинарным алгоритмом, способен решать глобальные задачи, находя свое применение во многих областях защиты информации: при генерировании параметров криптосистем с открытым ключом (RSA), при поиске нетривиальных делителей натуральных чисел (факторизации чисел), при построении ЭЦП, при вычислении обратного элемента в конечном поле (задача инвертирования), при шифровании и расшифровке ин-формации и т.д.
По итогам сравнения оказалось, что алгоритм Джебелеана-Вебера является лучшим из изучаемых по количеству проведенных итераций. Но время работы алгоритма для любых пар используемых в работе чисел меньше у бинарного алгоритма гораздо меньше первого за счет менее весомых операций, проводимых на каждой итерации алгоритма.
Несмотря на это, алгоритм Джебелеана-Вебера, наряду с бинарным алгоритмом, способен решать глобальные задачи, находя свое применение во многих областях защиты информации: при генерировании параметров криптосистем с открытым ключом (RSA), при поиске нетривиальных делителей натуральных чисел (факторизации чисел), при построении ЭЦП, при вычислении обратного элемента в конечном поле (задача инвертирования), при шифровании и расшифровке ин-формации и т.д.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.