Исследование и реализация тестов на простоту: Гольдвассера-Киллиана, Миллера-Рабина, Соловея-Штрассена
Заказать уникальную дипломную работу- 105105 страниц
- 0 + 0 источников
- Добавлена 10.08.2019
- Содержание
- Часть работы
- Список литературы
- Вопросы/Ответы
Введение 4
Глава 1. Теоретические основы разработки тестов на простоту 6
1.1 Основные понятия и классификация тестов на простоту 6
1.2 Теоретические основы разработки теста на простоту Миллера-Рабина 8
1.3 Теоретические основы разработки тестов на простоту Соловея-Штрассена 12
1.4 Теоретические основы разработки теста на простоту Гольдвассера-Киллиана 15
Глава 2. Практическая реализация тестов на простоту 18
2.1 Выбор языка программирования 18
2.2 Практическая реализация теста на простоту Гольдвассера-Киллиана 20
2.3 Практическая реализация теста на простоту Миллера-Рабина 25
2.4 Практическая реализация теста на простоту Соловея-Штрассена 30
Глава 3. Анализ эффективности тестов на простоту 35
3.1 Методика анализа эффективности тестов на простоту 35
3.2 Анализ эффективности теста на простоту Миллера-Рабина 39
3.3 Анализ эффективности теста на простоту Соловея-Штрассена 53
3.4 Анализ эффективности теста на простоту Гольдвассера-Киллиана 67
Заключение 75
Список литературы 77
Приложение 81
ДаРабота выполнена согласно МУ?Не применимо, так как МУ отсутствуютОбщий % соответствия работы требованиям, указанным в заказе95%ВЫВОДЫ ЭКСПЕРТНОЙ ОЦЕНКИДостоинства работыВо введении отражена цель и задачи работы.В первой главе приведены теоретические основы рассматриваемых тестов с указанием на особенности именно того варианта теста, который входил в исходное задание заказчика.Во второй главе обоснован выбор языка программирования, используемого для реализации тестов на простоту, а также алгоритмы работы разрабатываемого программного обеспечения для каждого из трех тестов..В третьей главе приведена методика оценки эффективности разработанного программного обеспечения и результаты оценки эффективности каждого из трех тестов согласно данной методике.Недостатки работыВ третьей главе отсутствуют четкие указание на то, какой именно вариант программы тестировался для первого и второго тестов, а также на разновидность модификации теста Гольдвассера-Киллиана, которая тестировалась, что допускает различные трактовки результатов тестирования.Заключение/рекомендации эксперта:Претензии заказчика не обоснованы, так как работа в целом соответствует согласованному с заказчиком плану (если план не соответствовал исходному заданию, то заказчик не должен был его согласовывать), данные в таблицах оставлены по первому варианту программы с его ведома, а указанные им в претензии корректировки по оформлению были выполнены.В то же время необходимо отметить, что более четкое указание на варианты реализации тестов в третьей главе могли бы уменьшить количество недопониманий между руководителем заказчика, заказчиком и исполнителем.
1. Тимошин, П. А. Перспективы развития и использования систем электронной цифровой подписи / П.А. Тимошин. - М.: Синергия, 2017. - 740 c.
2. Рассел, Джесси Быстрая цифровая подпись / Джесси Рассел. - М.: VSD, 2017. - 569 c.
3. Бернет С., Пейн С. Криптография. Официальное руководство RSA Security. - М.: Бином-Пресс, 2002. – 392 с.
4. Федеральный закон от 10.01.2002 г. № 1-ФЗ «Об электронной цифровой подписи» (в ред. от 23. 06.2005 г.) // Российская газета. – 12.01.2002. - № 6.
5. Нестеренко А. Введение в современную криптографию.Теоретико-числовые алгоритмы. — 2011. — С. 79 - 90. — 190 с. — ISBN 978-5-94506-320-4.
6. Х. К. А. ван Тилборг. Основы криптологии. — Москва: «Мир», 2006. — ISBN 5-03-003639-3 УДК 519.6.
7. Коблиц Н. Курс теории чисел и криптографии. — 2-ое. — М.: Научное издательство ТВП, 2001. — С. 149 - 160. — 254 с. — ISBN 5-94057-103-4.
8. Саломаа А. Криптография с открытым ключом / Пер. с англ. И.А. Вихлянцева. — М.: Мир, 1995. — С. 176 - 184. — 318 с. — ISBN 5-03-001991-X.
9. Lawrence C. Washington. Elliptic Curves: Number Theory and Cryptography. — New York: Chapman & Hall/CRC, 2003. — Т. 50. — (Discrete Mathematics and its applications). — ISBN 978-1-4200-7146-7.
10. Черемушкин А. В. Лекции по арифметическим алгоритмам в криптографии. — М.: МЦНМО, 2001. — С. 42 - 59. — 104 с. — ISBN 5-94057-060-7.
11. Ю. В. Нестеренко. Глава 4.4. Как отличить составное число от простого // Введение в криптографию / Под ред. В. В. Ященко. — Питер, 2001. — 288 с. — ISBN 5-318-00443-1.
12. Menezes A. J., Oorschot P. v., Vanstone S. A. Handbook of Applied Cryptography — CRC Press, 1996. — 816 p. — (Discrete Mathematics and Its Applications) — ISBN 978-0-8493-8523-0
13. Miller G. Riemann's Hypothesis and Tests for Primality // STOC '75: Proceedings of seventh annual ACM symposium on Theory of computing — New York, NY, USA: ACM, 1975. — P. 234–239. — doi:10.1145/800116.803773
14. Rabin M. O. Probabilistic algorithm for testing primality // J. Number Theor. / D. Goss — Elsevier, 1980. — Vol. 12, Iss. 1. — P. 128–138. — ISSN 0022-314X; 1096-1658 — doi:10.1016/0022-314X(80)90084-0
15. R. Schoof. Counting Points on Elliptic Curves over Finite Fields // J. Theor. Nombres Bordeaux. — 1995. — Вып. 7. — С. 219–254.
16. Josefsson, S.; Liusvaara, I. (January 2017). Edwards-Curve Digital Signature Algorithm (EdDSA). Internet Engineering Task Force. doi:10.17487/RFC8032. ISSN 2070—1721. RFC 8032. Retrieved 2017-07-3Daniel J. Bernstein; Marc Joye; Tanja Lange; Peter Birkner; Christiane Peters, Twisted Edwards Curves
17. Campbell Parallel Programming with Microsoft® Visual C++® / Campbell. - Москва: Гостехиздат, 2011. - 784 c.
18. Альфред, В. Ахо Компиляторы. Принципы, технологии и инструментарий / Альфред В. Ахо и др. - Москва: Высшая школа, 2015. - 882 c.
19. Балена, Франческо Современная практика программирования на Microsoft Visual Basic и Visual C# / Франческо Балена , Джузеппе Димауро. - М.: Русская Редакция, 2015. - 640 c.
20. Боровский, А. C++ и Pascal в Kylix 3. Разработка интернет-приложений и СУБД / А. Боровский. - М.: БХВ-Петербург, 2015. - 544 c.
21. Давыдов, В. Visual C++. Разработка Windows-приложений с помощью MFC и API-функций / В. Давыдов. - М.: БХВ-Петербург, 2014. - 576 c.
22. Довбуш, Галина Visual C++ на примерах / Галина Довбуш , Анатолий Хомоненко. - М.: БХВ-Петербург, 2012. - 528 c.
23. Зиборов, В. MS Visual C++ 2010 в среде .NET / В. Зиборов. - М.: Питер, 2012. - 320 c.
24. Кетков, Юлий Практика программирования: Visual Basic, C++ Builder, Delphi. Самоучитель (+ дискета) / Юлий Кетков , Александр Кетков. - М.: БХВ-Петербург, 2012. - 464 c.
25. Мешков, А. Visual C++ и MFC / А. Мешков, Ю. Тихомиров. - М.: БХВ-Петербург, 2013. - 546 c.
26. Неформальное введение в C++ и Turbo Vision. - Москва: ИЛ, 2010. - 384 c.
27. Панюкова, Т. А. Языки и методы программирования. Создание простых GUI-приложений с помощью Visual С++. Учебное пособие / Т.А. Панюкова, А.В. Панюков. - Москва: Мир, 2015. - 144 c.
28. Пахомов, Б. C/C++ и MS Visual C++ 2010 для начинающих / Б. Пахомов. - М.: БХВ-Петербург, 2011. - 736 c.
29. Пахомов, Борис C/C++ и MS Visual C++ 2012 для начинающих / Борис Пахомов. - Москва: СИНТЕГ, 2015. - 518 c.
30. Пахомов, Борис С/С++ и MS Visual C++ 2012 для начинающих / Борис Пахомов. - М.: "БХВ-Петербург", 2013. - 502 c.
31. Полубенцева, М. C/C++. Процедурное программирование / М. Полубенцева. - М.: БХВ-Петербург, 2014. - 448 c.
32. Поляков, А. Методы и алгоритмы компьютерной графики в примерах на Visual C++ / А. Поляков, В. Брусенцев. - М.: БХВ-Петербург, 2011. - 560 c.
33. Понамарев, В. Программирование на C++/C# в Visual Studio .NET 2003 / В. Понамарев. - М.: БХВ-Петербург, 2015. - 917 c.
34. Роберт, С. Сикорд Безопасное программирование на C и C++ / Роберт С. Сикорд. - Москва: РГГУ, 2014. - 496 c.
35. Секунов, Н. Программирование на C++ в Linux / Н. Секунов. - М.: БХВ-Петербург, 2016. - 425 c.
36. Сидорина, Татьяна Самоучитель Microsoft Visual Studio C++ и MFC / Татьяна Сидорина. - М.: "БХВ-Петербург", 2014. - 848 c.
37. Генри С. Уоррен, мл. Глава 16. Формулы для простых чисел // Алгоритмические трюки для программистов = Hacker’s Delight. — М.: Вильямс, 2007. — 288 с. — ISBN 0-201-91465-4.
38. Джек Фолк, Сэм Канер, Енг. Кек Нгуен. Тестирование программного обеспечения. Издательство ДиаСофт, 2001.
39. Рекс Блек. Ключевые процессы тестирования - М.: Издательство Лори, 2014. - 544 с.
40. Савин Роман. Тестирование DOT COM. Издательство Дело, 2007.
Вопрос-ответ:
Что такое тесты на простоту?
Тесты на простоту - это алгоритмы, которые позволяют определить, является ли число простым или составным.
Какие есть тесты на простоту?
Существует несколько известных тестов на простоту, таких как тесты Гольдвассера-Киллиана, Миллера-Рабина, Соловея-Штрассена и др.
Как работает тест Миллера-Рабина?
Тест Миллера-Рабина основан на случайном выборе чисел и проверке их свойств. Он имеет вероятностную природу и может давать ложноположительные или ложноотрицательные результаты, однако его вероятность ошибки можно сделать пренебрежимо малой.
Что такое тест Гольдвассера-Киллиана?
Тест Гольдвассера-Киллиана - это алгоритм, использующий теорию вероятности и математические доказательства для определения простоты числа. Он работает сравнительно быстро и имеет небольшую вероятность ошибки.
Какую роль играют тесты на простоту в криптографии?
Тесты на простоту являются важной частью криптографии, так как позволяют выбрать большие простые числа для использования в криптографических алгоритмах. Это обеспечивает безопасность системы и предотвращает взлом.
Какие есть основные понятия и классификация тестов на простоту?
В статье рассматриваются основные понятия и классификация тестов на простоту. Это позволяет систематизировать и классифицировать различные методы и алгоритмы, используемые для определения простоты чисел. Классификация включает тесты на основе разложения числа на множители, тесты на основе проверки существования простых делителей, а также вероятностные тесты, основанные на случайных числах.
Какие теоретические основы лежат в основе разработки теста на простоту Миллера-Рабина?
Разработка теста на простоту Миллера-Рабина основана на малой теореме Ферма и сильной псевдопростоте чисел. Алгоритм Миллера-Рабина основан на идее проверки простоты числа с помощью ряда случайных тестов. Он имеет высокую вероятность правильного определения простоты числа, но не является абсолютно точным.
Какие теоретические основы лежат в основе разработки тестов на простоту Соловея-Штрассена?
Тесты на простоту Соловея-Штрассена основаны на проверке числа на существование простых делителей. Эти тесты используют теорему Лукаса и проверку чисел Соловея для определения простоты числа. Они могут быть более точными, чем вероятностные тесты, но имеют большую вычислительную сложность.
Какие теоретические основы лежат в основе разработки теста на простоту Гольдвассера-Киллиана?
Разработка теста на простоту Гольдвассера-Киллиана основана на проверке числа на существование простого делителя. Этот тест использует понятие эйлеровой функции и проверку чисел Гольдвассера-Киллиана для определения простоты числа. Этот тест также может быть более точным, чем вероятностные тесты, но имеет большую вычислительную сложность.