ВВЕДЕНИЕ 3
1. ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ 4
1.1. Тесты простоты 4
1.2. Детерминированные тесты простоты 4
1.3. Недетерминированные тесты простоты 7
1.4. Тест Миллера-Рабина 8
1.5. Задачи исследования 12
2. РАЗРАБОТКА ПРОГРАММЫ 13
2.1. Средства реализации 13
2.2 Реализация алгоритма 13
2.2.1 Анализ свидетелей 14
2.2.2 Анализ тестов 16
3. РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ 18
3.1. Анализ свидетелей 18
3.2. Анализ тестов 23
ЗАКЛЮЧЕНИЕ 29
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 30
ПРИЛОЖЕНИЕ
Купить

Учитывая, что существуют такие криптосистемы, в которых используются простые числа, например, в популярной криптосистеме RSA простые числа используются при создании секретного ключа, то встает вопрос о быстром определении принадлежности числа к множеству простых чисел или составных.
Для решения этого вопроса были разработаны различные алгоритмы для определения составности или простоты числа и разделены на две большие группы: детерминированные тесты и недетерминированные(вероятностные).
Несмотря на то, что детерминированные тесты простоты легки в реализации, они работают, либо достаточно медленно, либо работают лишь для определенного вида простых чисел. К примеру, сложность метода перебора делителей в худшем случае оценивается как O(n2), а тест Пепина работает лишь для чисел Ферма, которые имеют вид Fn=22n+ 1 (где n > 1).
По этой причине в криптосистемах, которые в этом нуждаются, используются вероятностные тесты простоты, к которым и относится тест Миллера — Рабина.
Одним из важнейшим этапом алгоритма является выбор случайного числа, которое в конечном счете будет определено как свидетель простоты или же даст вывод о том, что исследуемое число является составным. Но среди этих случайных чисел есть такие числа, которые чаще остальных являются свидетелем простоты, хотя проверяемое число является составным.
Таким образом, определив такие числа и исключив их из проверки, мы можем уменьшить вероятность ошибки для теста Миллера-Рабина. Аналогично можно выявить такие числа, которые реже всего допускают ошибку при проверке числа на его принадлежность к простым числам и использовать их в первую очередь, если условия нам это позволяют.

Купить