Тема: ИССЛЕДОВАНИЕ СВИДЕТЕЛЕЙ ПРОСТОТЫ В ТЕСТЕ МИЛЛЕРА-РАБИНА

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

Купить

В ходе исследования было установлено, что при использовании приоритета свидетелей простоты можно добиться чуть лучших результатов для тестирования простых чисел. Если быть точнее, то на составные числа будет затрачиваться меньше итераций. Также были выявлены отличительные черты свидетелей попадающих под категорию чисел с низким приоритетом. Список лучших свидетелей простоты более динамичен, чем список худших свидетелей простоты.
По итогам сравнения выяснилось, что скорость убывания ошибок при использовании приоритетов становится выше.
Таким образом, мы имеем возможность отсеивать большие составные числа за меньшее количество итераций при использовании приоритетов выбора случайного просто числа. Исходя из этого мы меньше тратим времени при генерировании параметров криптосистем с открытым ключом.

Купить