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


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

Работа №77616

Тип работы

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

Предмет

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

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

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


ВВЕДЕНИЕ 3
1. КРАТКИЙ ОБЗОР ОСНОВНЫХ АЛГОРИТМОВ ВЫЧИСЛЕНИЯ НОД 4
1.1 Алгоритм Евклида 4
1.2 Улучшение алгоритма Евклида по Леммеру 5
1.3 Бинарный алгоритм Евклида 7
2. К-АРНЫЙ АЛГОРИТМ ЕВКЛИДА 9
2.1 Классический к-арный алгоритм 9
2.2 Аппроксимирующий к-арный алгоритм 11
2.2.1 Описание алгоритма 11
2.2.2 Рассмотрение примера 13
2.2.3 Анализ алгоритма 14
2.2.4 Параллельное вычисление 15
3. ПРАКТИЧЕСКИЕ РЕЗУЛЬТАТЫ 17
ЗАКЛЮЧЕНИЕ 21
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 22

Приложения должны быть в работе, но в данный момент отсутствуют

Вычисление НОД для двух натуральных чисел на сегодняшний день имеет высокое значение в математике, как и шифрование информации является одной из важнейших задач в области безопасности при передачи данных. Существующие методы шифрования, например схема RSA [1] (это название является аббревиатурой фамилий его создателей - Rivest, Shamir и Aldeman), схема Эль-Гамаля, или шифрование на основе эллиптических кривых, в той или иной степени используют вычисление обратного элемента в конечном поле, что напрямую связано с задачей нахождения НОД двух натуральных чисел.
Вместе с приходом многопроцессорных компьютеров появилась возможность реализации множества математических алгоритмов, используя параллельные вычисления.
В настоящее время не существует полностью реализованного алгоритма Евклида с использованием параллельного вычисления. В данной работе будут рассмотрены основные вариации алгоритма Евклида, а так же практическая реализация с учетом мультипроцессорности.
Целью данной работы является получение увеличения скорости выполнения вычисления НОД для больших чисел путем распараллеливания алгоритма.
Задачи данной работы определяются поставленной целью: рассмотреть методику вычисления НОД при помощи алгоритма Евклида, рассмотреть возможные улучшения для алгоритма и их распараллеливание, программно реализовать параллельное вычисление НОД.


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

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

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

В данной работе были рассмотрены различные алгоритмы поиска НОД двух чисел и были реализованы классический алгоритм Евклида, бинарный алгоритм Евклида а так же удалось распараллелить к-арный алгоритм Евклида. Полученные результаты в ходе практической реализации подтвердили теорию о возможности получения улучшения по времени выполнения при помощи модификаций классического алгоритма Евклида, но они отличались от теоретических. Так, например, теоретическая разница параллельного применения к-арного алгоритма с классическим алгоритмом Евклида составляла порядка 450%, однако, на практике мы получили улучшение результата лишь на 190%. Считаю, что это по большей части обусловлено самим алгоритмом, так как он основан на определенной вероятности и числах, которые могут быть заведомо нам известны, однако есть и результаты, которые дают плохие данные по времени выполнения.
Также хотелось бы отметить, что для к-арного алгоритма использование разница по параметру k оказалась не сильно заметна, так как мы получили некое ускорение, перейдя с параметра k = 64 к k =256, однако, при следующем увеличении с k = 256 до k = 1024 время выполнения вновь увеличилось, поэтому на практике не удалось получить увеличение времени выполнения с увеличением параметра k.



1. Whitfield Diffie, Martin E. Hellman. New Directions in Cryptography // IEEE Transactions on Information Theory. - Nov. 1976. - V. IT-22. - P. 644-654.
2. Dixon J. The Number of Steps of the Euclidian Algorithm // Journal of Number Theory. - 1970. - V.1. - P. 414-422.
3. Akhavi, A., Vallee, B. Average Bit-Complexity of Euclidean Algorithms // Proceedings ICALP’00, Lecture Notes Computer Science 1853. - 2000. - P. 373-387.
4. Stein, J. Computational problems associated with Racah algebra // Journal of Computational Physics. - 1967. - V. 1 (3). - P. 397-405.
5. Sorenson, J.Two fast GCD Algorithms // Journal of Algorithms. - 1994. - V. 16 (1). - P. 110-144.
6. Sorenson J. An analysis of the generalized binary GCD algorithm / J. Sorenson, A. van der Poorten, A. Stein // Lectures in Honour of Hugh Cowie Williams. - Banff, Alberta, Canada. - AMS Math. Review. - 2004. - V. 41.-P. 254-258.
7. Jebelean T. A generalization of the binary GCD Algorithm. // Proc. of the Intern. Symp. on Symbolic and Algebraic Computation (ISSAC93). - 1993.-P. 111-116.
8. Weber K. The accelerated integer GCD algorithm // ACM Transactions of Math. Software. - 1995. - V. 21 (1). - P. 111-122.
9. Ishmukhametov S. An Approximating k-ary GCD Algorithm // Lobachevskii Journal of Mathematics. - 2016. - V. 37. - P. 722-728.
10. Hardy G.H., Wright E.M. An Introduction to the Theory of Numbers // Oxford, Calrendon Press. - 1959. - V. 4.

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



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

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

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

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

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

Новости

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

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

дальше

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

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

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

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

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

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


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