ИССЛЕДОВАНИЕ МЕТОДОВ ПОИСКА ПСЕВДОПРОСТЫХ ЧИСЕЛ

ВВЕДЕНИЕ 3
Глава 1. Псевдопростые числа 5
Глава 2. Алгоритмы поиска сильно псевдопростых чисел 6
2.1. Алгоритм Померанца, Селфриджа и Вагстаффа (PSW) 6
2.2. Алгоритм Джаешке 8
2.3. Алгоритм Джиянга и Денга 10
2.4. Алгоритм Соренсона 12
Глава 3. Реализация алгоритмов 16
Глава 4. Результаты тестирования 19
ЗАКЛЮЧЕНИЕ 26
СПИСОК ЛИТЕРАТУРЫ 27
ПРИЛОЖЕНИЯ
Купить

В виду быстрого развития информационных технологий одной из наиболее актуальных проблем современности является проблема защиты информации или информационной безопасности. Как известно для ее решения используются различные методы, в том числе и технические. В техническом направлении наиболее важную роль играют криптографические методы защиты информации, основанные на различных алгоритмах, примерами которых могут служить алгоритм RSA, алгоритм Эль - Гамаля и эллиптические кривые, используемые в электронной цифровой подписи. В выше указанных алгоритмах шифрование производится посредством использования многоразрядных простых чисел (512 бит, 1024 бита). А так как использование таких больших простых чисел связано с трудностью их обнаружения, а, следовательно, с трудностью взлома этих алгоритмов, то генерация и последующая работа с ними очень важна в криптографии.
Тестом простоты называют процедуру проверки простоты заданного числа п. В настоящий момент существуют множество тестов простоты, которые можно разделить на детерминированные, то бишь, истинные, и на вероятностные. Если число п проходит любой из вероятностных тестов, то его весьма вероятно можно назвать «простым числом», если же п не пройдет хотя бы один из выбранных тестов, то его называют «составным числом». Тем не менее при проведении тестов на простоту можно встретить такие составные числа, которые будут иметь некоторые свойства простых чисел и, соответственно, пройдут этот тест. Такие числа называют псевдопростыми числами [1]. Среди вероятностных тестов простоты часто используемым является тест простоты Миллера - Рабина [2, 10], который играет немаловажную роль, ведь составные числа, успешно проходящие данный тест называются «сильно псевдопростыми числами». Чтобы уменьшить вероятность неправильного определения составного числа п, увеличивают число итераций, то бишь, проверок в тесте. Отсюда вытекает проблема, какое число итераций необходимо провести, чтобы гарантированно дать определение «простое» проверяемому числу. Иными словами, до какого минимального сильно псевдопростого числа по заданной базе стоит производить проверки.
Проблема изучения и поиска сильно псевдопростых чисел является актуальной и с теоретической точки зрения, и с практической уже на протяжении нескольких десятков лет: авторы [3] вычислили для т = 2, 3 и 4; Джаешке [4] продлил эту последовательность до ^8, а Джиянг и Денгдо. Последней публикацией можно считать работу [6], авторы которой проверили работу предыдущих и вычислили для т = 12 и 13.
Целью работы является проведение сравнительного анализа различных алгоритмов поиска сильно псевдопростых чисел.
В ходе проведения исследования предполагаются следующие задачи:
- теоретическое рассмотрение нескольких алгоритмом поиска spsp,
- выбор 2-х алгоритмов для практической реализации,
- оценка теоретической сложности и времени выполнения,
- оценка границ диапазонов хорошей работы,
- определение преимуществ и недостатков каждого из них,
- возможное предложение идеи по повышению эффективности данных алгоритмов.

Купить