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


ИССЛЕДОВАНИЕ СВИДЕТЕЛЕЙ ПРОСТОТЫ В ТЕСТЕ МИЛЛЕРА-РАБИНА

Работа №45589

Тип работы

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

Предмет

информационная безопасность

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

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


ВВЕДЕНИЕ 3
1. ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ 4
1.1. Тесты простоты 4
1.2. Детерминированные тесты простоты 4
1.3. Недетерминированные тесты простоты 7
1.4. Тест Миллера-Рабина 8
1.5. Задачи исследования 12
2. РАЗРАБОТКА ПРОГРАММЫ 13
2.1. Средства реализации 13
2.2 Реализация алгоритма 13
2.2.1 Анализ свидетелей 14
2.2.2 Анализ тестов 16
3. РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ 18
3.1. Анализ свидетелей 18
3.2. Анализ тестов 23
ЗАКЛЮЧЕНИЕ 29
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 30
ПРИЛОЖЕНИЕ

Учитывая, что существуют такие криптосистемы, в которых используются простые числа, например, в популярной криптосистеме RSA простые числа используются при создании секретного ключа, то встает вопрос о быстром определении принадлежности числа к множеству простых чисел или составных.
Для решения этого вопроса были разработаны различные алгоритмы для определения составности или простоты числа и разделены на две большие группы: детерминированные тесты и недетерминированные(вероятностные).
Несмотря на то, что детерминированные тесты простоты легки в реализации, они работают, либо достаточно медленно, либо работают лишь для определенного вида простых чисел. К примеру, сложность метода перебора делителей в худшем случае оценивается как O(n2), а тест Пепина работает лишь для чисел Ферма, которые имеют вид Fn=22n+ 1 (где n > 1).
По этой причине в криптосистемах, которые в этом нуждаются, используются вероятностные тесты простоты, к которым и относится тест Миллера — Рабина.
Одним из важнейшим этапом алгоритма является выбор случайного числа, которое в конечном счете будет определено как свидетель простоты или же даст вывод о том, что исследуемое число является составным. Но среди этих случайных чисел есть такие числа, которые чаще остальных являются свидетелем простоты, хотя проверяемое число является составным.
Таким образом, определив такие числа и исключив их из проверки, мы можем уменьшить вероятность ошибки для теста Миллера-Рабина. Аналогично можно выявить такие числа, которые реже всего допускают ошибку при проверке числа на его принадлежность к простым числам и использовать их в первую очередь, если условия нам это позволяют.


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

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

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


В ходе исследования было установлено, что при использовании приоритета свидетелей простоты можно добиться чуть лучших результатов для тестирования простых чисел. Если быть точнее, то на составные числа будет затрачиваться меньше итераций. Также были выявлены отличительные черты свидетелей попадающих под категорию чисел с низким приоритетом. Список лучших свидетелей простоты более динамичен, чем список худших свидетелей простоты.
По итогам сравнения выяснилось, что скорость убывания ошибок при использовании приоритетов становится выше.
Таким образом, мы имеем возможность отсеивать большие составные числа за меньшее количество итераций при использовании приоритетов выбора случайного просто числа. Исходя из этого мы меньше тратим времени при генерировании параметров криптосистем с открытым ключом.



1. Василенко О. Н. «Теоретико-числовые алгоритмы в криптографии», 2003.
2. Егоров Д. Ф. «Элементы теории чисел», 1923
3. Ишмухаметов Ш.Т., Рубцова Р.Г. Лабораторная работа по курсу "Распределенная обработка данных" - Поиск строго псевдопростых чисел и использование их для ускорения алгоритма Миллера-Рабина проверки простоты натуральных чисел / Казанский федеральный университет - 8 с.
4. Крэндалл Ричард, Померанс Карл. Простые числа: Криптографические и вычислительные аспекты. Пер. с англ. / Под ред. и с предисл. В.Н. Чубарикова. - М.: УРСС: Книжный дом «ЛИБРОКОМ», 2011.
5. Ященко В.В. «Введение в криптографию», 2000.
6. Arnault F. Constructing Carmichael Numbers which are Strong Pseudo-primes to Several Bases // Journal of Symbolic Computation , 1995.


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



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


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