ВВЕДЕНИЕ 3
ГЛАВА I. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ 5
1.1. Алгоритмы шифрования, в которых используются простые числа
1.1.1. Шифр RSA 6
1.1.2. Протокол Диффи-Хеллмана 8
1.1.3. Криптосистема Эль-Гамаля 9
1.2. Методы поиска простых чисел 10
1.2.1. Решето Аткина 12
1.2.2. Тест Миллера- Рабина 14
ГЛАВА II. ПСЕВДОПРОСТЫЕ ЧИСЛА И МЕТОДЫ ИХ ПОИСКА 16
2.1. Псевдопростые и строго псевдопростые числа 16
2.2. Алгоритмы поиска псевдопростых чисел 17
2.2.1. Метод перебора 17
2.2.2. Алгоритм Померанца 19
2.2.3. Алгоритм Jaeschke 20
ГЛАВА III. ОСОБЕННОСТИ РЕАЛИЗАЦИИ И РЕЗУЛЬТАТЫ 24
3.1. Инструменты реализации 24
3.2. Анализ результатов 25
ЗАКЛЮЧЕНИЕ 31
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 32
ПРИЛОЖЕНИЕ
В наше время глобальная сеть окутала весь мир. Многие даже не смогут представить свою жизнь без интернета. Его роль в жизни всего человечества возрастает с каждым годом. В сети люди работают, знакомятся, отдыхают, оплачивают коммунальные услуги, учатся...
Вместе с распространением всемирной паутины появились и новые проблемы - проблемы безопасности, анонимности, защиты данных.. .Для решения вышеприведённых задач было придумано множество алгоритмов, методов шифрования, в которых простые числа играют ключевые роли.
Простое число является натуральным и имеет только два делителя: единицу и само себя. На уникальных свойствах таких чисел основано множество криптографических алгоритмов. Например, в алгоритме RSA простые числа играют решающую роль и от них зависит стойкость всей системы[2]. Однако, возникает проблема нахождения таких чисел, особенно если они имеют большую размерность. Разработано много алгоритмов, позволяющих за то или иное время установить, принадлежит ли заданное число множеству простых. Самым практичным и часто-используемым является тест простоты Миллера-Рабина[8].
Алгоритм Миллера-Рабина представляет собой полиномиальный вероятностный тест простотых[5]. Но он не позволяет доказать простоту наверняка и даёт точный результат только при работе с составным числом. Данное свойство объясняется существованием псевдопростых чисел - составных чисел, которые обладают некоторыми признаками простого числа. Алгоритм Миллера-Рабина иногда «ошибается», распознавая псевдопростое число, как простое. Избавляются от такой погрешности увеличением числа проверок в тесте [13].
Приступая к написанию данной работы, я поставил перед собой следующие цели:
1. Разработка программного комплекса, осуществляющего поиск псевдопростых чисел.
2. Найти все псевдопростые числа по нескольким основаниям до границы 1 0 1 6.
3. На основе полученных данных выявить практические закономерности.
Для нахождения строго псевдопростых чисел был реализован алгоритм Jaeschke. В качестве границы было выбрано число B = 1016.
Составляющие алгоритма Jaeschke:
• Решето Аткина, находящие простые числа.
• Приложение вычисляющее значения I а (р ) для каждого простого числа по выбранным базам.
• Тест простоты Миллера-рабина.
• Сам алгоритм поиска spsp(a) чисел.
Для более эффективной реализации программы поиска строго псевдопростых чисел произведено распараллеливание кода функцией Map.
В ходе работы был произведен поиск псевдопростых чисел вида п = р * q (p,q- простые числа) по базам {2,3},{2,3,5} и {2,3,5,7} до фиксированной границы 1 0 1 6. Данный подход весьма эффективен, потому что большинство строго псевдопростых чисел по нескольким базам состоят из двух сомножителей.
Были приведены два возможных улучшения теста Миллера-Рабина:
1. С использованием списка строго псевдопростых чисел.
2. С определением , как наименьшего строго псевдопростого числа по первым m простым числам.
Числовые и графические зависимости, полученные в данном исследовании, могут быть использованы для построения эффективных тестов простоты и оценки ошибок в алгоритме Миллера-Рабина, а также будут полезны в дальнейшем исследовании свойства строго псевдопростых чисел.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
