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


АНАЛИЗ И УЛУЧШЕНИЕ ВЕРОЯТНОСТНОГО ТЕСТА МИЛЛЕРА - РАБИНА

Работа №77677

Тип работы

Магистерская диссертация

Предмет

информатика

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

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


ВВЕДЕНИЕ 3
2. ПОСТАНОВКА ЗАДАЧИ 4
3. ПРЕДМЕТНАЯ ОБЛАСТЬ 5
• Теорема Рабина 5
• Алгоритм Миллера - Рабина 11
• Алгоритм для поиска количества свидетелей 12
• Исследование числа свидетелей произвольного п 14
• Исследование свидетелей множества Z*2 16
• Предложение по улучшению алгоритма Миллера- Рабина 19
4. АНАЛИЗ РАБОТЫ АЛГОРИТМОВ 22
5. ЗАКЛЮЧЕНИЕ 27
6. СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ..28
7. ПРИЛОЖЕНИЕ 29

Темой магистерской диссертации является "Анализ и улучшение вероятностного теста Миллера-Рабина". Алгоритм Миллера — Рабина является вероятностным полиномиальным тестом простоты. Тест Миллера — Рабина, как и тест Ферма и тест Соловея — Штрассена, позволяет достаточно эффективно и быстро определить, является ли предложенное число составным. Тем не менее, с помощью данного алгоритма нельзя строго доказать простоту числа. Однако вероятностный тест Миллера — Рабина очень часто используется в криптографии для получения случайных больших простых чисел.
Криптостойкость многих алгоритмов для шифрования основана на секретных ключах и для создания секретных ключей используются простые числа (например, на этом основана работа шифра RSA), поэтому при создании таких ключей важно иметь возможность быстро проверить большие числа на простоту. Вероятностные тесты простоты, такие как тест Миллера- Рабина и Тест Соловея — Штрассена, показывают достаточно большую эффективность использования и простоту выражения по сравнению с детерминированными тестами. Алгоритм Миллера-Рабина позволяет выполнять проверку за очень малое время и давать при этом достаточно малую вероятность того, что число на самом деле является составным.
В данной работе планируется:
• реализовать алгоритм Миллера - Рабина
• предложить улучшение для вероятностного теста Миллера - Рабина
• реализовать предложенный алгоритм
• провести сравнительный анализ предложенного алгоритма с классическим.


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

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

Помощь студентам в написании работ!
ДИПЛОМНЫЕ МАГИСТЕРСКИЕ ДИССЕРТАЦИИ
Курсовые Статьи Диплом Рязань

В процессе работы были выполнены следующие задачи:
• реализовать алгоритм Миллера - Рабина
• предложить улучшение для вероятностного теста Миллера - Рабина
• реализовать предложенный алгоритм
• провести сравнительный анализ предложенного алгоритма с классическим.
На основе полученных в результате сравнительного анализа данных можно сделать следующие выводы:
• предложенный алгоритм показывает лучшие результаты по сравнению с классическим алгоритмом. На выбранных интервалах данных максимальная вероятность принять ошибочно составное число за простое составила 0.0020, что является гораздо меньшим числом по сравнению с вероятностью 0.25, указанной в теореме Миллера.
• классический алгоритм на выбранных интервалах составных чисел показывает лучшие результаты по сравнению с предложенным алгоритмом. Максимальная вероятность для классического алгоритма составила - 0.0017
Исходя из вышеизложенных утверждений, можно сделать вывод, что предложенный алгоритм показывает улучшение лишь в общем случае. На конкретных выбранных интервалах из - за большой вероятности данный алгоритм проигрывает. Поэтому требуется дальнейший анализ на большей выборке данных, что позволит произвести более тщательный анализ распределения свидетелей, выявить возможные проблемные с точки зрения проверки на простоту числа.



[1] Ишмухаметов Ш.Т. Избранные вопросы информационной безопасности. Лекции для магистрантов и аспирантов ИВМиИТ. Лекция 2. Исследование теста простоты Миллера-Рабина. Казанский (Приволжский) федеральный университет
[2] Гашков С.Б. Упрощенное обоснование вероятностного теста Миллера- Рабина для
проверки простоты чисел. Дискрет. матем., 10:4 (1998), 35-38
[3] Потапов Д. Обоснование теста Миллера-Рабина для проверки простоты чисел
[4] Саломаа А. Криптография с открытым ключом. Мир, Москва, 1996.
[5] Miller G. L. Riemann's hypothesis and tests for primality. J. Сотр. System Sci. (1976) 13, 300-317.
[6] Rabin M. O. Probabilistic algorithm for testing primality. J. Number Theory (1980) 12, №1, 128-138.
[7] Knuth D. The Art of Computer Programming. V.2. Seminumerical Algorithms. AddisonWesley, Reading, Mass., 1981.
[8] Crandall R. The prime numbers: a computational perspertive / R. Crandall, C. Pomerance.- sec.ed. Springer-Verlag, Berlin, 2005, 604 p.
[9] Shamil T.Ishmukhametov, B. Mubarakov. On practical aspects of the Miller- Rabin Primality Test, Lobachevskii Journal of Mathematics, October 2013, Volume 34, Issue 4, pp 304-312
[10] Pomerance, C., Selfridge, J. L., and Wagstaff, S. S. The Pseudoprimes to 25 109, Mathematics of Computation, 35, 1980, P. 1003-1026.
[11] Arnault F. Constructing Carmichael Numbers which are Strong Pseudoprimes to Several Bases // Journal of Symbolic Computation — Elsevier, 1995. — Vol.
20, Iss. 2. — P. 151-161
[12] D amgard I., Landrock P., Pomerance C. Average C ase Error Estimates for the Strong Probable Prime Test // Math. Comp. — AMS, 1993. — Vol. 61, Iss. 203. — P. 177-194.

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



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

Заказать работу

Заявка на оценку стоимости

Это краткая форма заказа. После ее заполнения вы перейдете на полную форму заказа работы

Каталог работ (129963)

Новости

06.01.2018 Помощь студентам и аспирантам в выполнении работ от наших партнеров Помощь студентам и аспирантам в выполнении работ от наших партнеров

Помощь в выполнении учебных и научных работ на заказ ОФОРМИТЬ ЗАКАЗ

дальше

»» Все новости

Заказать работу

Заявка на оценку стоимости

Это краткая форма заказа. После ее заполнения вы перейдете на полную форму заказа работы

Заказать диплом

Приглашаем авторов студенчесчких работ


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