ВВЕДЕНИЕ 3
АЛГОРИТМЫ НАХОЖДЕНИЯ НОД 5
АЛГОРИТМ ЕВКЛИДА 5
БИНАРНЫЙ АЛГОРИТМ ЕВКЛИДА 7
АЛГОРИТМ ЛЕМЕРА 9
К-АРНЫЙ АЛГОРИТМ ЕВКЛИДА 10
К-арный Алгоритм Евклида с правым сдвигом 10
К-арный Алгоритм Евклида с левым сдвигом 16
СЛОЖНОСТЬ К-АРНОГО АЛГОРИТМА ЕВКЛИДА 22
ПАРАЛЛЕЛИЗАЦИЯ К-АРНОГО АЛГОРИТМА ЕВКЛИДА 24
ГЕНЕРАЦИЯ ПАРАМЕТРОВ И РЕЗУЛЬТАТЫ РАБОТЫ АЛГОРИТМОВ 26
ВЫВОДЫ, ТАБЛИЦЫ И ГРАФИКИ 27
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 40
Купить

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

Купить