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


ИССЛЕДОВАНИЕ ПСЕВДОПРОСТЫХ ЧИСЕЛ, ИСПОЛЬЗУЕМЫХ В КРИПТОГРАФИИ

Работа №77630
Тип работыДипломные работы, ВКР
Предметинформационная безопасность
Объем работы38
Год сдачи2017
Стоимость4295 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено 44
Не подходит работа?

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

ВВЕДЕНИЕ 3
ГЛАВА I. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ 5
1.1. Алгоритмы шифрования, в которых используются простые числа
1.1.1. Шифр RSA 6
1.1.2. Протокол Диффи-Хеллмана 8
1.1.3. Криптосистема Эль-Гамаля 9
1.2. Методы поиска простых чисел 10
1.2.1. Решето Аткина 12
1.2.2. Тест Миллера- Рабина 14
ГЛАВА II. ПСЕВДОПРОСТЫЕ ЧИСЛА И МЕТОДЫ ИХ ПОИСКА 16
2.1. Псевдопростые и строго псевдопростые числа 16
2.2. Алгоритмы поиска псевдопростых чисел 17
2.2.1. Метод перебора 17
2.2.2. Алгоритм Померанца 19
2.2.3. Алгоритм Jaeschke 20
ГЛАВА III. ОСОБЕННОСТИ РЕАЛИЗАЦИИ И РЕЗУЛЬТАТЫ 24
3.1. Инструменты реализации 24
3.2. Анализ результатов 25
ЗАКЛЮЧЕНИЕ 31
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 32
ПРИЛОЖЕНИЕ

В наше время глобальная сеть окутала весь мир. Многие даже не смогут представить свою жизнь без интернета. Его роль в жизни всего человечества возрастает с каждым годом. В сети люди работают, знакомятся, отдыхают, оплачивают коммунальные услуги, учатся...
Вместе с распространением всемирной паутины появились и новые проблемы - проблемы безопасности, анонимности, защиты данных.. .Для решения вышеприведённых задач было придумано множество алгоритмов, методов шифрования, в которых простые числа играют ключевые роли.
Простое число является натуральным и имеет только два делителя: единицу и само себя. На уникальных свойствах таких чисел основано множество криптографических алгоритмов. Например, в алгоритме RSA простые числа играют решающую роль и от них зависит стойкость всей системы[2]. Однако, возникает проблема нахождения таких чисел, особенно если они имеют большую размерность. Разработано много алгоритмов, позволяющих за то или иное время установить, принадлежит ли заданное число множеству простых. Самым практичным и часто-используемым является тест простоты Миллера-Рабина[8].
Алгоритм Миллера-Рабина представляет собой полиномиальный вероятностный тест простотых[5]. Но он не позволяет доказать простоту наверняка и даёт точный результат только при работе с составным числом. Данное свойство объясняется существованием псевдопростых чисел - составных чисел, которые обладают некоторыми признаками простого числа. Алгоритм Миллера-Рабина иногда «ошибается», распознавая псевдопростое число, как простое. Избавляются от такой погрешности увеличением числа проверок в тесте [13].
Приступая к написанию данной работы, я поставил перед собой следующие цели:
1. Разработка программного комплекса, осуществляющего поиск псевдопростых чисел.
2. Найти все псевдопростые числа по нескольким основаниям до границы 1 0 1 6.
3. На основе полученных данных выявить практические закономерности.


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

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

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


Для нахождения строго псевдопростых чисел был реализован алгоритм Jaeschke. В качестве границы было выбрано число B = 1016.
Составляющие алгоритма Jaeschke:
• Решето Аткина, находящие простые числа.
• Приложение вычисляющее значения I а (р ) для каждого простого числа по выбранным базам.
• Тест простоты Миллера-рабина.
• Сам алгоритм поиска spsp(a) чисел.
Для более эффективной реализации программы поиска строго псевдопростых чисел произведено распараллеливание кода функцией Map.
В ходе работы был произведен поиск псевдопростых чисел вида п = р * q (p,q- простые числа) по базам {2,3},{2,3,5} и {2,3,5,7} до фиксированной границы 1 0 1 6. Данный подход весьма эффективен, потому что большинство строго псевдопростых чисел по нескольким базам состоят из двух сомножителей.
Были приведены два возможных улучшения теста Миллера-Рабина:
1. С использованием списка строго псевдопростых чисел.
2. С определением , как наименьшего строго псевдопростого числа по первым m простым числам.
Числовые и графические зависимости, полученные в данном исследовании, могут быть использованы для построения эффективных тестов простоты и оценки ошибок в алгоритме Миллера-Рабина, а также будут полезны в дальнейшем исследовании свойства строго псевдопростых чисел.



1. Crandall R., Pomerance C. The prime numbers: a computational perspective. —Springer-Verlag, Berlin, 2005. — 604 p.
2. A.O.L. Atkin, D.J. Bernstein,Prime sieves using binary quadratic forms, Math. Comp. 73 (2004). P — 1023-1030.
3. Pritchard, Paul, "Linear prime-number sieves: a family tree," Sci. Comput. Programming 9:1 (1987), P. 17-35.
4. Rivest R. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems / R. Rivest, A.Shamir, L. Adleman // Communications of the ACM. - 1978. - Vol. 21(2). - P. 120-126.
5. Rabin M. Probabilistic algorithm for testing primality, J. Numb.Theory, 12, 1, 1980, p. 128-138.
6. Baillie R., Samuel S. Lucas Pseodoprimes Math. Comput. 35, 1980, p. 1391¬1417.
7. Pomerance C., Selfrifge J., Samuel S. The Pseudoprimes to 25-109. Math. Comput. 35, 1980, p. 1003-1026.
8. Jaeschke G. On Strong Pseudoprimes to Several Bases. Math. Comput. 61, 1993, p. 915-926.
9. Whitfield Diffie and Martin E. Hellman New Directions in Cryptography. IEEE Transaactions of information theory, november 1976, p. 644-645.
10. Bulat G. Mubarakov, Andrey S. Mochalov and Ramilya G. Rubtsova Investigation of Distribution of Pseudosimple Numbers. Medwell Journals, 2015, p.358-364.
11. Ishmukhametov S., Mubarakov B. On practical aspects of the Miller-Rabin Primarily Test / Lobachevskii Journal of Mathematics, 2013, v.3, 13 p.
12. Stewart V.A. Algebraic Number Theory and Fermat’s Last Theorem / I. Stewart, D. Tall - Third Ed., Massachusetts: AK Peters, 2002, 314p.
13. Jonathan P. Sorenson, Jonathan Webster, Strong Pseudoprimes to Twelve Prime Bases, arXiv: 1509.00864 math.NT, 2015, 17p.
14. J.Jiang, Y.Deng. Strong pseudoprimes to the first 9 prime bases. arXiv:1207.0063v1 math.NT, 2012, 12 p.
15. Lenstra H.W. Factoring integers with elliptic curves / H.W. Lenstra. - Ann.Math. v.126 (1987), p. 649-674.
16. Brent R.P. Some parallel algorithms for integer factorisation / R.P. Brent.- Lect.Notes in Comp.Sci, 1999, v.1685, p. 1-22.
17. Gardner M. A new kind of cipher that would take millions years to break /M. Gardner. — Sci. Amer. 1977, p. 120-124.
18. Pollard J.M. Factoring with cubic numbers./ J.M. Pollard. - in Lenstra et alt[1993], p. 4-10.
19. Pomerance C. Smooth Numbers and the Quadratic Sieve / C. Pomerance. - MSRI publications, v.44 - 2008, p. 69-82.
20. Ribenboim P. The New Book Of Prime Number Records,/ P. Ribenboim. - 3rd ed. Springer, 1996, 541 p.
21. Schoof R. Four primarity testing algorithms./ R. Schoof. - in Surveys in
Algorithmic Number Theory, ed.J.B.Buchler, P.Stevenhagen,
Math.Sci.Res.Inst.Publ. 44, Cambridge Univ.Press, New York, 2008, p.101¬126.
22. Shoup V. A Computational Introduction to Number Theory and Algebra/ V. Shoup. - Cambridge University Press, Sec.Edition, 2005, 600 p.
23. Ишмухаметов Ш.Т. Методы факторизации натуральных чисел. — учебное пособие, 2011. — 190с.
24. Ишмухаметов Ш.Т. Бойко А.А. Мубараков Б.Г. Об одном классе строго псевдопростых чисел // Научный журнал. — 2014. — С. 97-110.
25. Аграновский А.В. Практическая криптография: алгоритмы и их программирование / А.В. Аграновский, Р.А. Хади.- М.: Солон-Пресс,
2009. — 256 с.
26. Айерленд К. Классическое введение в современную теорию чисел. / К. Айерленд, М. Роузен. - М.: Мир, 1987. — 428 с.
Т7. Боревич З.И. Теория чисел. / З.И. Боревич, И.Р. Шафаревич. - 3-е издание, М.: Наука, 1985. — 504 с.
28. Коблиц Н. Курс теории чисел и криптографии / Н. Коблиц. - М.: ТВП, 2001. — 260 с.
29. Лазарева С.В. Математические основы криптологии: тесты простоты и факторизация / С.В. Лазарева, А.А. Овчинников. Учебное пособие, Санкт-Петербург, СПбГУАП, 2006. — 65 с.
30. Дербишир Дж. Простая одержимость — АСТ Астрель, 2010 стр. — 463 с.


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



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


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