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