DOI: 10.17587/prin.7.21-28

УДК: 512.742.72

Эффективный алгоритм скалярного умножения точки эллиптической кривой на основе NAF-метода

Д. С. Хлебородов, аспирант, e-mail: dkhleborodov@gmail.com, Московский государственный технический университет имени Н. Э. Баумана

Представлен алгоритм эффективного скалярного умножения точки эллиптической кривой, определенной над простым полем, на основе метода бинарного несовместного представления скаляра (Non-Adjacent Form, NAF). Для оценки эффективности полученных и известных на настоящее время алгоритмов введен критерий эффективности, основанный на средней вычислительной сложности. Для получения нового, более эффективного алгоритма использованы: эффективные операции в простом поле; операции с точкой, включая сложение, удвоение; операция "удвоить и сложить", масштабирование; свойства аффинной координатной системы; свойства координатной системы Якоби. Для предложенного алгоритма сформулировано и доказано утверждение относительно его вычислительной сложности.

Ключевые слова: эллиптические кривые, скалярное умножение, операции с точкой, быстрые алгоритмы, вычислительная сложность, преобразования на эллиптических кривых, алгоритм

Стр. 21–28