ВВЕДЕНИЕ 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, а Джиянг и Денг
[5] до . Последней публикацией можно считать работу [6], авторы которой проверили работу предыдущих и вычислили для т = 12 и 13.
Целью работы является проведение сравнительного анализа различных алгоритмов поиска сильно псевдопростых чисел.
В ходе проведения исследования предполагаются следующие задачи:
- теоретическое рассмотрение нескольких алгоритмом поиска spsp,
- выбор 2-х алгоритмов для практической реализации,
- оценка теоретической сложности и времени выполнения,
- оценка границ диапазонов хорошей работы,
- определение преимуществ и недостатков каждого из них,
- возможное предложение идеи по повышению эффективности данных алгоритмов.
В ходе работы были проведены тестирования работы алгоритмов поиска сильно псевдопростых чисел Джаешке и Джиянга-Денга, сравнены и исследованы полученные результаты при t = 2, построены графики и подведены итоги.
Для t> 3 вновь запущенные вычисления занимают намного больше времени, так как для данных случаев последовательно ищутся все подходящие простые числа q (повторяются вычисления для t — 1, но с другим набором ограничений), они же будущие множители, с одинаковой с р1 сигнатурой. Тем не менее можно исключить это момент задав поиск одинаковых сигнатур для списка простых чисел из файла primes_1m.txt (1 млн простых чисел, максимальное из которых ~15,48 млн). Для одной базы треть данного подсчета занимает >20 часов, что можно считать одним из недостатков. Также стоит отметить, что по тенденции число подходящих чисел будет сокращаться с увеличением числа баз, но также увеличиваться с возрастанием интервала. Тем не менее, среди этих чисел может не оказаться псевдопростого числа для нахождения spsp.
Теоретическая сложность алгоритмов такова: Джаешке - О (В In В), Джиянг и Денг - 0(В2/3+о(1). На практике было подтверждено, что Алгоритм Джиянга и Денга работает намного быстрее и эффективнее, так как в нем прописаны множество условий (~700 строк кода), а в Алгоритме Джаешке (~300 строк кода) такого нет. Такая работа непосредственно связана со следующим его преимуществом - разделением простых чисел на модульные остатки, и как я поняла, в основном все базируется на них. Согласно проведенным опытам хорошим диапазоном работы для первого является интервал < 1010, для второго < 108.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
