📄Работа №39140
Тема: ИССЛЕДОВАНИЕ МЕТОДОВ ФАКТОРИЗАЦИИ НАТУРАЛЬНЫХ ЧИСЕЛ
Характеристики работы
Тип работы
Дипломные работы, ВКР
Предмет
Информатика и вычислительная техника
Объем:
49 листов
Год:
2019
Просмотров:
1257
6500
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
ВВЕДЕНИЕ 4
Глава 1. Алгоритмы факторизации 7
1.1. Метод Ферма 7
1.2. р-алгоритм Полларда 7
1.3. P-1 алгоритм Полларда 8
1.4. Метод квадратичных форм Шенкса 9
1.5. Метод Лемана 10
1.6. Алгоритм Диксона 10
1.7. Метод непрерывных дробей. Метод Лемера и Пауэрса 11
Глава 2. Реализация алгоритмов 14
2.1. Метод Ферма 14
2.3. Р-1 алгоритм Полларда 14
2.4. Метод квадратичных форм Шенкса 14
2.5. Метод Лемана 15
2.6. Алгоритм Диксона 15
2.7. Метод непрерывных дробей. Вариант Лемера и Пауэрса 16
2.8. Метод непрерывных дробей. Вариант Моррисона и Бриллхарта .. 16
Глава 3. Сравнение алгоритмов 18
3.1. Сравнение экспоненциальных алгоритмов 18
3.1.1. Метод Ферма 18
3.1.2. р-алгоритм Полларда 19
3.1.3. P-1 алгоритм Полларда 19
3.1.4. Метод квадратичных форм Шенкса 20
3.1.5. Метод Лемана 21
3.1.6. Сравнение алгоритмов на интервале 10л2 - 10л3 22
3.1.7. Сравнение алгоритмов на интервале 10Л3 - 10Л4 23
3.1.8. Сравнение алгоритмов на интервале 10Л4 - 10Л5 24
3.1.9. Сравнение алгоритмов на интервале 10Л5 - 10Л6 25
3.1.10. Сравнение алгоритмов на интервале 10Л6 - 10Л7 26
3.1.11. Сравнение алгоритмов на интервале 10Л7 - 10л8 27
3.2. Сравнение субэкспоненциальных алгоритмов 28
3.2.1. Алгоритм Диксона 28
3.2.2. Метод непрерывных дробей(вариант Лемера и Пауэрса) 29
3.2.3. Метод непрерывных дробей(вариант Моррисона и Бриллхарта) 30
3.2.4. Сравнение алгоритмов на интервале 10Л9 - 10Л10 31
3.2.5. Сравнение алгоритмов на интервале 10Л15 - 10Л16 32
3.2.6. Сравнение алгоритмов на интервале 10Л21 - 10Л22 33
ЗАКЛЮЧЕНИЕ 35
СПИСОК ЛИТЕРАТУРЫ 37
ПРИЛОЖЕНИЯ 40
Глава 1. Алгоритмы факторизации 7
1.1. Метод Ферма 7
1.2. р-алгоритм Полларда 7
1.3. P-1 алгоритм Полларда 8
1.4. Метод квадратичных форм Шенкса 9
1.5. Метод Лемана 10
1.6. Алгоритм Диксона 10
1.7. Метод непрерывных дробей. Метод Лемера и Пауэрса 11
Глава 2. Реализация алгоритмов 14
2.1. Метод Ферма 14
2.3. Р-1 алгоритм Полларда 14
2.4. Метод квадратичных форм Шенкса 14
2.5. Метод Лемана 15
2.6. Алгоритм Диксона 15
2.7. Метод непрерывных дробей. Вариант Лемера и Пауэрса 16
2.8. Метод непрерывных дробей. Вариант Моррисона и Бриллхарта .. 16
Глава 3. Сравнение алгоритмов 18
3.1. Сравнение экспоненциальных алгоритмов 18
3.1.1. Метод Ферма 18
3.1.2. р-алгоритм Полларда 19
3.1.3. P-1 алгоритм Полларда 19
3.1.4. Метод квадратичных форм Шенкса 20
3.1.5. Метод Лемана 21
3.1.6. Сравнение алгоритмов на интервале 10л2 - 10л3 22
3.1.7. Сравнение алгоритмов на интервале 10Л3 - 10Л4 23
3.1.8. Сравнение алгоритмов на интервале 10Л4 - 10Л5 24
3.1.9. Сравнение алгоритмов на интервале 10Л5 - 10Л6 25
3.1.10. Сравнение алгоритмов на интервале 10Л6 - 10Л7 26
3.1.11. Сравнение алгоритмов на интервале 10Л7 - 10л8 27
3.2. Сравнение субэкспоненциальных алгоритмов 28
3.2.1. Алгоритм Диксона 28
3.2.2. Метод непрерывных дробей(вариант Лемера и Пауэрса) 29
3.2.3. Метод непрерывных дробей(вариант Моррисона и Бриллхарта) 30
3.2.4. Сравнение алгоритмов на интервале 10Л9 - 10Л10 31
3.2.5. Сравнение алгоритмов на интервале 10Л15 - 10Л16 32
3.2.6. Сравнение алгоритмов на интервале 10Л21 - 10Л22 33
ЗАКЛЮЧЕНИЕ 35
СПИСОК ЛИТЕРАТУРЫ 37
ПРИЛОЖЕНИЯ 40
📖 Введение
Всю систему шифрования можно поделить на 2 класса: симметричные и ассиметричные алгоритмы шифрования. Суть симметричных алгоритмов состоит в том, что и шифрующий, и дешифрующий человек должны знать алгоритм шифрования, называемый ключом. Самым известным устройством, работающим симметричным методом, была немецкая шифровальная машина «Энигма». Ассиметричные алгоритмы шифрования являются более надежными[1], так как в них используются 2 ключа - открытый и закрытый. Открытый применяется для шифрования информации, а закрытый - для дешифрования. Таким образом, шанс попадания обоих ключей в руки взломщика очень мал. К тому же, зная закрытый ключ, достаточно просто узнать открытый, но из открытого ключа получить закрытый практически невозможно: для подбора закрытого ключа понадобится очень много времени, так как вариантов может быть столько, что даже самый мощный компьютер будет подбирать их несколько десятков лет.
Одним из самых популярных алгоритмов шифрования на сегодняшний день является алгоритм ассиметричного шифрования RSA. В его основе лежит задача факторизации произведения двух больших чисел, результат которой и определяет криптостойкость алгоритма.
Что же такое факторизация? Факторизация - это разложение числа на простые множители[2]. Существует много алгоритмов, которые решают данную задачу, и поиск новых ведется до сих пор. К сожалению, на данный момент совершенного алгоритма пока нет. Несмотря на то, что существуют алгоритмы, способные правильно разложить число на множители, ни один из них не в силах разложить достаточно большое число за разумное время.
Все алгоритмы факторизации делятся на 2 типа: экспоненциальные и субэкспоненциальные. Сложность экспоненциальных алгоритмов зависит от длины входящих параметров, а для субэкспоненциальных алгоритмов сложность приято обозначать L - нотацией[3]:
Ln(a,c) := 0(e((c+o(i))(logn)a(loglogn)1
где n - число, подлежащее факторизации, а 0 < а < 1 и с — некоторые константы.
К экспоненциальным алгоритмам относятся такие алгоритмы, как:
- перебор возможных делителей;
- метод факторизации Ферма;
- р-алгоритм Полларда;
- Р-1 алгоритм Полларда;
- алгоритм Ленстры;
- алгоритм Полларда-Штрассена;
- метод квадратичных форм Шенкса;
- метод Лемана.
К субэкспоненциальным алгоритмам относятся такие алгоритмы, как:
- алгоритм Диксона;
- факторизация методом непрерывных дробей;
- метод квадратичного решета;
- факторизация с помощью эллиптических кривых.
Вопрос о существовании алгоритма с полиномиальной сложностью, который будет работать на обычном компьютере, до сих пор остается открытым и является достаточно важной проблемой. Но также же существует алгоритм с полиномиальной сложностью, работающий на квантовом компьютере - алгоритм Шора[4].
В данной работе рассматривались как экспоненциальные, так и субэкспоненциальные алгоритмы. Из экспоненциальных алгоритмов были выбраны такие как:
- метод факторизации Ферма;
- р - алгоритм Полларда;
- Р-1 - алгоритм Полларда;
- метод квадратичных форм Шенкса;
- метод Лемана.
Из субэкспоненциальных алгоритмов были отобраны следующие алгоритмы:
- алгоритм Диксона;
- метод непрерывных дробей. Метод Лемера и Пауэрса;
- метод непрерывных дробей. Метод Моррисона и Бриллхарта[5]. Целью данной работы является исследование алгоритмов факторизации и проведения сравнительного анализа.
По ходу работы были выявлены следующие задачи:
- рассмотрение нескольких алгоритмов факторизации натуральных чисел;
- их реализация на языке программирования Python;
- исследование каждого алгоритма и выявление зависимости времени работы от размера факторизуемого числа;
- сравнение времени работы алгоритмов между собой на разных числовых интервалах;
- подведение итогов.
Одним из самых популярных алгоритмов шифрования на сегодняшний день является алгоритм ассиметричного шифрования RSA. В его основе лежит задача факторизации произведения двух больших чисел, результат которой и определяет криптостойкость алгоритма.
Что же такое факторизация? Факторизация - это разложение числа на простые множители[2]. Существует много алгоритмов, которые решают данную задачу, и поиск новых ведется до сих пор. К сожалению, на данный момент совершенного алгоритма пока нет. Несмотря на то, что существуют алгоритмы, способные правильно разложить число на множители, ни один из них не в силах разложить достаточно большое число за разумное время.
Все алгоритмы факторизации делятся на 2 типа: экспоненциальные и субэкспоненциальные. Сложность экспоненциальных алгоритмов зависит от длины входящих параметров, а для субэкспоненциальных алгоритмов сложность приято обозначать L - нотацией[3]:
Ln(a,c) := 0(e((c+o(i))(logn)a(loglogn)1
где n - число, подлежащее факторизации, а 0 < а < 1 и с — некоторые константы.
К экспоненциальным алгоритмам относятся такие алгоритмы, как:
- перебор возможных делителей;
- метод факторизации Ферма;
- р-алгоритм Полларда;
- Р-1 алгоритм Полларда;
- алгоритм Ленстры;
- алгоритм Полларда-Штрассена;
- метод квадратичных форм Шенкса;
- метод Лемана.
К субэкспоненциальным алгоритмам относятся такие алгоритмы, как:
- алгоритм Диксона;
- факторизация методом непрерывных дробей;
- метод квадратичного решета;
- факторизация с помощью эллиптических кривых.
Вопрос о существовании алгоритма с полиномиальной сложностью, который будет работать на обычном компьютере, до сих пор остается открытым и является достаточно важной проблемой. Но также же существует алгоритм с полиномиальной сложностью, работающий на квантовом компьютере - алгоритм Шора[4].
В данной работе рассматривались как экспоненциальные, так и субэкспоненциальные алгоритмы. Из экспоненциальных алгоритмов были выбраны такие как:
- метод факторизации Ферма;
- р - алгоритм Полларда;
- Р-1 - алгоритм Полларда;
- метод квадратичных форм Шенкса;
- метод Лемана.
Из субэкспоненциальных алгоритмов были отобраны следующие алгоритмы:
- алгоритм Диксона;
- метод непрерывных дробей. Метод Лемера и Пауэрса;
- метод непрерывных дробей. Метод Моррисона и Бриллхарта[5]. Целью данной работы является исследование алгоритмов факторизации и проведения сравнительного анализа.
По ходу работы были выявлены следующие задачи:
- рассмотрение нескольких алгоритмов факторизации натуральных чисел;
- их реализация на языке программирования Python;
- исследование каждого алгоритма и выявление зависимости времени работы от размера факторизуемого числа;
- сравнение времени работы алгоритмов между собой на разных числовых интервалах;
- подведение итогов.
✅ Заключение
Факторизацией натурального числа называется его разложение на простые множители. Данная задача имеет очень большую вычислительную сложность. Алгоритм RSA, основанный на трудоемкости задачи факторизации длинных чисел, является одним из самых популярных методов криптографии с открытым ключом[21].
Проведение экспериментов для различных методов, показало, что время выполнения алгоритма напрямую зависит от его типа и вычислительной сложности.
В данной работе были рассмотрены несколько известных алгоритмов для решения задачи факторизации и также было проведено их сравнение.
Была достигнута цель реализовать метод факторизации Ферма, р- алгоритм Полларда, Р-1 алгоритм Полларда, метод квадратичных форм Шенкса, метод Лемана, алгоритм Диксона, метод непрерывных дробей (метод Лемера и Пауэрса) и метод непрерывных дробей (метод Моррисона и Бриллхарта). На основе полученных результатов был проведен сравнительный анализ данных алгоритмов[22].
У каждого алгоритма можно отметить как плюсы, так и минусы:
- метод факторизации Ферма работает вполне эффективно, только если делители числа N находятся близко к друг другу. В противном случае эффективность данного алгоритма падает до сложности полного перебора;
- р-алгоритм Полларда является вероятностным алгоритмом и эффективность данного алгоритма во многом зависит от исходного полинома. Но не смотря на это он мало затратный по памяти, и к тому же его сложность зависит только от величины делителя р, а не входного числа N. То есть главное достоинство этого алгоритма: он применим в тех случаях, когда остальные алгоритмы, зависящие напрямую от числа N, перестают быть эффективными;
- Р-1 алгоритм Полларда работает достаточно быстро на фоне остальных выбранных экспоненциальных алгоритмов. Он быстро находит небольшой простой делитель р, который является степенно-гладким для выбранной границы. Однако выбор правильной границы является сложным дополнением;
- метод квадратичных форм Шенкса довольно легкий в плане реализации, к тому же число итераций первого и второго циклов алгоритма определяется числом сомножителей факторизуемого числа N;
- метод Лемана так же, как и Р-1 алгоритм Полларда, работает достаточно быстро на фоне остальных выбранных экспоненциальных алгоритмов. Это связано с тем, что он развивает идеи, на которых была основана теорема Ферма;
- алгоритм Диксона имеет субэкспоненциальную сложность, но его эффективность для факторизации чисел в рамках моей работы просматривается недостаточно хорошо;
- метод непрерывных дробей (вариант Лемера и Пауэрса) показал лучшие результаты среди остальных субэкспоненциальных алгоритмов благодаря относительной легкости реализации. Здесь не нужно было вычислять факторную базу и вычислять линейно независимые вектора, как для алгоритма Диксона и второго варианта Моррисона и Бриллхарта метода непрерывных дробей.
В итоге благодаря результатам, полученным в ходе экспериментальных работ, получилось еще раз обосновать теоретические данные.
Проведение экспериментов для различных методов, показало, что время выполнения алгоритма напрямую зависит от его типа и вычислительной сложности.
В данной работе были рассмотрены несколько известных алгоритмов для решения задачи факторизации и также было проведено их сравнение.
Была достигнута цель реализовать метод факторизации Ферма, р- алгоритм Полларда, Р-1 алгоритм Полларда, метод квадратичных форм Шенкса, метод Лемана, алгоритм Диксона, метод непрерывных дробей (метод Лемера и Пауэрса) и метод непрерывных дробей (метод Моррисона и Бриллхарта). На основе полученных результатов был проведен сравнительный анализ данных алгоритмов[22].
У каждого алгоритма можно отметить как плюсы, так и минусы:
- метод факторизации Ферма работает вполне эффективно, только если делители числа N находятся близко к друг другу. В противном случае эффективность данного алгоритма падает до сложности полного перебора;
- р-алгоритм Полларда является вероятностным алгоритмом и эффективность данного алгоритма во многом зависит от исходного полинома. Но не смотря на это он мало затратный по памяти, и к тому же его сложность зависит только от величины делителя р, а не входного числа N. То есть главное достоинство этого алгоритма: он применим в тех случаях, когда остальные алгоритмы, зависящие напрямую от числа N, перестают быть эффективными;
- Р-1 алгоритм Полларда работает достаточно быстро на фоне остальных выбранных экспоненциальных алгоритмов. Он быстро находит небольшой простой делитель р, который является степенно-гладким для выбранной границы. Однако выбор правильной границы является сложным дополнением;
- метод квадратичных форм Шенкса довольно легкий в плане реализации, к тому же число итераций первого и второго циклов алгоритма определяется числом сомножителей факторизуемого числа N;
- метод Лемана так же, как и Р-1 алгоритм Полларда, работает достаточно быстро на фоне остальных выбранных экспоненциальных алгоритмов. Это связано с тем, что он развивает идеи, на которых была основана теорема Ферма;
- алгоритм Диксона имеет субэкспоненциальную сложность, но его эффективность для факторизации чисел в рамках моей работы просматривается недостаточно хорошо;
- метод непрерывных дробей (вариант Лемера и Пауэрса) показал лучшие результаты среди остальных субэкспоненциальных алгоритмов благодаря относительной легкости реализации. Здесь не нужно было вычислять факторную базу и вычислять линейно независимые вектора, как для алгоритма Диксона и второго варианта Моррисона и Бриллхарта метода непрерывных дробей.
В итоге благодаря результатам, полученным в ходе экспериментальных работ, получилось еще раз обосновать теоретические данные.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.
🔍 ПОХОЖИЕ РАБОТЫ ПО ТЕМЕ
Информационные системы
Физика
Математика
📎 ДИПЛОМНЫЕ РАБОТЫ, ВКР ПО ПРЕДМЕТУ «ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА»
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника