📄Работа №77677
Тема: АНАЛИЗ И УЛУЧШЕНИЕ ВЕРОЯТНОСТНОГО ТЕСТА МИЛЛЕРА - РАБИНА
Тип работы
Магистерская диссертация
Предмет
информатика
Объем:
38 листов
Год:
2017
Просмотров:
341
4810
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
ВВЕДЕНИЕ 3
2. ПОСТАНОВКА ЗАДАЧИ 4
3. ПРЕДМЕТНАЯ ОБЛАСТЬ 5
• Теорема Рабина 5
• Алгоритм Миллера - Рабина 11
• Алгоритм для поиска количества свидетелей 12
• Исследование числа свидетелей произвольного п 14
• Исследование свидетелей множества Z*2 16
• Предложение по улучшению алгоритма Миллера- Рабина 19
4. АНАЛИЗ РАБОТЫ АЛГОРИТМОВ 22
5. ЗАКЛЮЧЕНИЕ 27
6. СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ..28
7. ПРИЛОЖЕНИЕ 29
2. ПОСТАНОВКА ЗАДАЧИ 4
3. ПРЕДМЕТНАЯ ОБЛАСТЬ 5
• Теорема Рабина 5
• Алгоритм Миллера - Рабина 11
• Алгоритм для поиска количества свидетелей 12
• Исследование числа свидетелей произвольного п 14
• Исследование свидетелей множества Z*2 16
• Предложение по улучшению алгоритма Миллера- Рабина 19
4. АНАЛИЗ РАБОТЫ АЛГОРИТМОВ 22
5. ЗАКЛЮЧЕНИЕ 27
6. СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ..28
7. ПРИЛОЖЕНИЕ 29
📖 Введение
Темой магистерской диссертации является "Анализ и улучшение вероятностного теста Миллера-Рабина". Алгоритм Миллера — Рабина является вероятностным полиномиальным тестом простоты. Тест Миллера — Рабина, как и тест Ферма и тест Соловея — Штрассена, позволяет достаточно эффективно и быстро определить, является ли предложенное число составным. Тем не менее, с помощью данного алгоритма нельзя строго доказать простоту числа. Однако вероятностный тест Миллера — Рабина очень часто используется в криптографии для получения случайных больших простых чисел.
Криптостойкость многих алгоритмов для шифрования основана на секретных ключах и для создания секретных ключей используются простые числа (например, на этом основана работа шифра RSA), поэтому при создании таких ключей важно иметь возможность быстро проверить большие числа на простоту. Вероятностные тесты простоты, такие как тест Миллера- Рабина и Тест Соловея — Штрассена, показывают достаточно большую эффективность использования и простоту выражения по сравнению с детерминированными тестами. Алгоритм Миллера-Рабина позволяет выполнять проверку за очень малое время и давать при этом достаточно малую вероятность того, что число на самом деле является составным.
В данной работе планируется:
• реализовать алгоритм Миллера - Рабина
• предложить улучшение для вероятностного теста Миллера - Рабина
• реализовать предложенный алгоритм
• провести сравнительный анализ предложенного алгоритма с классическим.
Криптостойкость многих алгоритмов для шифрования основана на секретных ключах и для создания секретных ключей используются простые числа (например, на этом основана работа шифра RSA), поэтому при создании таких ключей важно иметь возможность быстро проверить большие числа на простоту. Вероятностные тесты простоты, такие как тест Миллера- Рабина и Тест Соловея — Штрассена, показывают достаточно большую эффективность использования и простоту выражения по сравнению с детерминированными тестами. Алгоритм Миллера-Рабина позволяет выполнять проверку за очень малое время и давать при этом достаточно малую вероятность того, что число на самом деле является составным.
В данной работе планируется:
• реализовать алгоритм Миллера - Рабина
• предложить улучшение для вероятностного теста Миллера - Рабина
• реализовать предложенный алгоритм
• провести сравнительный анализ предложенного алгоритма с классическим.
✅ Заключение
В процессе работы были выполнены следующие задачи:
• реализовать алгоритм Миллера - Рабина
• предложить улучшение для вероятностного теста Миллера - Рабина
• реализовать предложенный алгоритм
• провести сравнительный анализ предложенного алгоритма с классическим.
На основе полученных в результате сравнительного анализа данных можно сделать следующие выводы:
• предложенный алгоритм показывает лучшие результаты по сравнению с классическим алгоритмом. На выбранных интервалах данных максимальная вероятность принять ошибочно составное число за простое составила 0.0020, что является гораздо меньшим числом по сравнению с вероятностью 0.25, указанной в теореме Миллера.
• классический алгоритм на выбранных интервалах составных чисел показывает лучшие результаты по сравнению с предложенным алгоритмом. Максимальная вероятность для классического алгоритма составила - 0.0017
Исходя из вышеизложенных утверждений, можно сделать вывод, что предложенный алгоритм показывает улучшение лишь в общем случае. На конкретных выбранных интервалах из - за большой вероятности данный алгоритм проигрывает. Поэтому требуется дальнейший анализ на большей выборке данных, что позволит произвести более тщательный анализ распределения свидетелей, выявить возможные проблемные с точки зрения проверки на простоту числа.
• реализовать алгоритм Миллера - Рабина
• предложить улучшение для вероятностного теста Миллера - Рабина
• реализовать предложенный алгоритм
• провести сравнительный анализ предложенного алгоритма с классическим.
На основе полученных в результате сравнительного анализа данных можно сделать следующие выводы:
• предложенный алгоритм показывает лучшие результаты по сравнению с классическим алгоритмом. На выбранных интервалах данных максимальная вероятность принять ошибочно составное число за простое составила 0.0020, что является гораздо меньшим числом по сравнению с вероятностью 0.25, указанной в теореме Миллера.
• классический алгоритм на выбранных интервалах составных чисел показывает лучшие результаты по сравнению с предложенным алгоритмом. Максимальная вероятность для классического алгоритма составила - 0.0017
Исходя из вышеизложенных утверждений, можно сделать вывод, что предложенный алгоритм показывает улучшение лишь в общем случае. На конкретных выбранных интервалах из - за большой вероятности данный алгоритм проигрывает. Поэтому требуется дальнейший анализ на большей выборке данных, что позволит произвести более тщательный анализ распределения свидетелей, выявить возможные проблемные с точки зрения проверки на простоту числа.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.