АНАЛИЗ МЕТОДА ФАКТОРИЗАЦИИ НАТУРАЛЬНЫХ ЧИСЕЛ С ИСПОЛЬЗОВАНИЕМ ЭЛЛИПТИЧЕСКИХ КРИВЫХ ЭДВАРДСА
Научный руководитель - д-р физ.-мат. наук, профессор, д. н.(доцент) КФУ ИВМиИТ кафедры системного анализа и информационных технологий
Защищенность многих информационных систем зависит от сложности такого преобразования, как факторизация - разложение натурального числа на множители. На сегодня существует множество алгоритмов факторизации, некоторые из которых способны решать глобальные задачи - разложение на множители чисел большой размерности - за приемлемое время. Метод факторизации чисел с использованием эллиптических кривых является "способным". Кривые Эдвардса - специальный вид эллиптических кривых, применение которых в методе факторизации может способствовать приросту производительности за счет использования меньшего количества операций по модулю.
В настоящей работе разработано консольное приложение, в котором производятся вычисления порядка кривых методом Шенкса-Местре, на основе которых выполняется дальнейшая классификация кривых по степени их пригодности для метода факторизации Ленстры натуральных чисел с подсчетом частоты вхождения кривых в каждый класс. Стоит отметить вычислительную сложность порядка кривой для модулей больших размерностей. Как известно, для модулей p ≤ 229 есть смысл использовать прямой перебор точек. Однако, на больших модулях не представляется возможным за приемлемое время подсчитать порядок кривой таким образом. Для решения этой проблемы и был реализован алгоритм Шенкса-Местре.
Для некоторого сравнения результатов, полученных практически, приложение выполняет подсчет значения, необходимого для вычисления распределения гладких чисел на том же наборе данных, что и в первом исследовании. Сравнение уместно по причине сходства распределения гладких и степенногладких чисел на некотором интервале.
Второстепенное исследование, реализованное в приложении - зависимость "качества" кривой от параметров, входящих в запись уравнения кривой. Под качеством следует понимать степень пригодности для метода факторизации Ленстры. Результаты работы приложения по этому исследованию помимо статистики в процентном соотношении - графическое отображение проверяемой закономерности.
Результаты данного исследования можно использовать при факторизации чисел методом Ленстры в плане прицельного выбора кривых по параметрам или выбора необходимого количества случайных кривых для параллельного запуска на них процесса нахождения делителей числа. Также полученные данные могут найти применение при дальнейшем исследовании кривых Эдвардса.
