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