Разработка эффективных алгоритмов вычисления НОД натуральных чисел для криптографии и теории чисел

Первая глава посвящена постановке задачи и обзору основных ал­ горитмов вычисления наибольшего общего делителя (НОД) натуральных чисел. Целью данной главы является анализ и сравнение эффективности существующих методов поиска НОД. Самым древним из которых является классический алгоритм Евклида (КАЕ). Этот алгоритм имеет многочис­ ленное применение в теории чисел и криптографии и остается одним из самых эффективных алгоритмов вычисления НОД. Его расширенная версия (РАЕ) используется во многих криптографических и теоретико-чис­ ловых алгоритмах, поэтому оценка его производительности играет важную роль в расчетах эффективности криптографических алгоритмов. Алгоритм Евклида имеет многочисленное применение в теории чисел и криптографии. Приведем некоторые примеры. В теории чисел: —Его расширенная версия используется для нахождения обратных элементов в конечных полях. —Алгоритм используется при решении линейных диофантовых урав­ нений. Частный случай линейного диофантового уравнения - это соотношение Безу . НОД (А,В) = хА + уВ, которое легко решается при помощи расширенной версии алгорит­ ма. —При помощи алгоритма можно представить любое вещественное число в виде непрерывной (цепной) дроби, если это число рацио­ нально. А В до + д\ + 92+ i r [go;gr,92;---;9n] где qi - значение A div В на г-ой итерации алгоритма Евклида, при г = 0 . . . п. —Также при помощи алгоритма можно определить являются ли два числа взаимно простыми, то есть не имеют никаких общих делите­ лей, кроме 1. В криптографии: —Алгоритм используется для генерации открытого и секретного ключей в методе шифрования RSA. —Используется для генерации параметров точек на эллиптических кривых и вычисления их кратного.13 13Ишмухаметов Ш.Т., Мубараков В.Г., Аль-Анни К.М. Вычисление коэффициентов Везу для fc-арного алгоритма нахождения НОД / / Известия высших учебных заведений. Математика. — 2017. —№ 11. — С. 30-38. 9