Задача вычисления Наибольшего общего делителя для пар натуральных чисел имеет большое значение для математики и применимы во множестве задач. В особенности, с развитием сферы защиты информации возрастает необходимость быстрых и эффективных алгоритмов нахождения НОД для продуктивный работы криптографических программ.
Некоторые, криптографические протоколы, например RSA ECDSA
или ГОСТ 34.10 (использующий эллиптические кривые), используют этот алгоритм для генерации своих параметров и для шифрования секретных сообщений или для установки цифровых подписей.
С развитием многопроцессорных систем многие математические алгоритмы получили свои быстрые параллельные реализации.
В данной работе мы проводим анализ и реализацию к-арного алогритма Евклида с целью ускорить его с помощью параллельных вычислений, для повышения эффективности и рациональности использования ресурсов компьютера.
Мы рассмотрим другие существующие решения и проводим его практическое сравнение с ними. Мы рассмотрим классический алгоритм Евклида, бинарный алгоритм, алгоритм Лермера, и к-арный алгоритмом нахождения наибольшего общего делителя.
В данной работе были изучены научные работы и материалы по теме
быстрого нахождения наибольшего общего делителя. Для проверки и
анализа работы алгоритма, а также проведения численных экспериментов было выполнено:
•реализованы несколько известных алгоритмов (указанных выше), для построения сравнительной таблицы их работы •сгенерированы несколько наборов пар чисел различной размерности для входных данных
• входные данные сгруппированы по размеру и поданы на вход программе для анализа скорости работы алгоритма, результаты работы сохранялись для отображения в виде таблиц и графиков
• реализован параллельный к-арный алгоритм Евклида для работы на многопоточной системы
В этой работе мы рассмотрели алгоритмы нахождения наибольшего общего делителя. Мы реализовали классический алгоритм Евклида, бинарный алгоритм, алгоритм Лермера, и к-арный алгоритмом нахождения наибольшего общего делителя. Мы провели анализ и реализацию к-арного алогритма Евклида и ускорили его с помощью параллельных вычислений, для повышения эффективности и рациональности использования ресурсов компьютера. На полученных нами данных видно, что к=арный алгоритм Евклида превосходит другие реализации нахождения НОД. Параллелизация дала нам, в среднем, выигрыш по скорости в = 2,295.
