Тип работы:
Предмет:
Язык работы:


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

Работа №39092

Тип работы

Дипломные работы, ВКР

Предмет

информационные системы

Объем работы52
Год сдачи2019
Стоимость6500 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
364
Не подходит работа?

Узнай цену на написание


ВВЕДЕНИЕ 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-х алгоритмов для практической реализации,
- оценка теоретической сложности и времени выполнения,
- оценка границ диапазонов хорошей работы,
- определение преимуществ и недостатков каждого из них,
- возможное предложение идеи по повышению эффективности данных алгоритмов.


Возникли сложности?

Нужна помощь преподавателя?

Помощь студентам в написании работ!


В ходе работы были проведены тестирования работы алгоритмов поиска сильно псевдопростых чисел Джаешке и Джиянга-Денга, сравнены и исследованы полученные результаты при 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.



1. Bulat G. Mubarakov, Andrey S. Mochalov and Ramilya G. Rubtsova Investigation of Distribution of Pseudosimple Numbers. [Текст] / Research Journal of Applied Sciences. - 2015. - №. 10. - C. 358-364.
2. Rabin M. O. Probabilistic algorithm for testing primality [Текст] / Journal of number theory. - 1980. - Т. 12. - №. 1. - С. 128-138.
3. C. Pomerance, C. Selfridge, S. Wagstaff. The Pseudoprimes to 25 * 109 [Текст] / Math. Comput. - 1980. - P. 1003-1026.
4. Jaeschke G. On strong pseudoprimes to several bases [Текст] / Mathematics of Computation. - 1993. - Т. 61. - №. 204. - С. 915-926.
5. Jiang Y., Deng Y. Strong pseudoprimes to the first 9 prime bases [Текст] / arXiv preprint arXiv: 1207.0063. - 2012.
6. Sorenson J., Webster J. Strong pseudoprimes to twelve prime bases [Текст] / Mathematics of Computation. - 2017. - Т. 86. - №. 304. - С. 985-1003.
7. Zhang Z., Tang M. Finding strong pseudoprimes to several bases. II [Текст] / Mathematics of computation. - 2003. - Т. 72. - №. 244. - С. 2085-2097.
8. Ишмухаметов Ш. Т. Об одном классе строго псевдопростых чисел [Текст] / Ш.Т. Ишмухаметов, Б.Г. Мубараков // Эвристические алгоритмы и распределенные вычисления. - 2014. - Т. 1. - №. 1. - С. 64-73.
9. Пчелкина Н.И. Отчет по практике по получению первичных профессиональных навыков [Текст] / Казанский (Приволжский) федеральный университет. - 2019. - 10 стр.
10. Пчелкина Н.И. Исследование эффективности теста простоты Миллера-Рабина: курсовая работа [Текст] / Казанский (Приволжский) федеральный университет. - 2019. - 29 стр.
11. Псевдопростое число - Википедия [Электронный ресурс]. - URL:
https://m.wikipedia.org/wiki/Псевдопростое_число (дата обращения 31.05.2019) .
12. Псевдопростое число Люка - Википедия [Электронный ресурс]. -
URL: https://ru.wikipedia.org/wiki/Псевдопростое_число_Люка (дата
обращения 31.05.2019).
13. Китайская теорема об остатках - Википедия [Электронный ресурс]. - URL: https://m.wikipedia.org/wiki/Китайская_теорема_об_остатках (дата обращения 31.05.2019).
14. Модуль gmpy2 [Электронный ресурс]. - URL: https://pypi.org/project/gmpy2/ (дата обращения 2.06.2019).
15. Модуль ecdsa [Электронный ресурс]. - URL: https://pypi.org/project/ecdsa/ - (дата обращения 2.06.2019).
16. Библиотека numpy [Электронный ресурс]. - URL:
https://pypi.org/project/numpy/ (дата обращения 2.06.2019).
17. Библиотека numba [Электронный ресурс]. - URL:
https://pypi.org/project/numba/ (дата обращения 2.06.2019).
18. LLVM - Википедия [Электронный ресурс]. - URL : https://ru.wikipedia.org/wiki/LLVM (дата обращения 2.06.2019).
19. Репозиторий Github [Электронный ресурс]. - URL:
https://github.com/pchelkanat/spsp.git (дата обращения 2.06.2019).
20. Google Cloud Platform [Электронный ресурс]. - URL: https://cloud.google.com (дата обращения 2.06.2019).


Работу высылаем на протяжении 30 минут после оплаты.



Подобные работы


©2024 Cервис помощи студентам в выполнении работ