Умножение и возведение в степень по большим модулям с использованием минимально избыточной модулярной арифметики

Abstract

Предлагаются новые быстрые алгоритмы умножения и возведения в степень по большому модулю, основанные на минимально избыточной модулярной схеме Монтгомери. Главной отличительной особенностью разработанной схемы является использование интервально-индексных характеристик и интервально-модулярной формы чисел в базовых процедурах расширения кода. Достигаемая за счет этого оптимизация синтезированных мультипликативных алгоритмов обеспечивает (3,5−3,6)-кратное повышение производительности (в сравнении с наиболее близким модулярным аналогом) при выполнении на однопроцессорной ЭВМ. В случае мультипроцессорной реализации получаемый выигрыш в быстродействии является (7−8)-кратным. Созданные алгоритмы предназначены для применения в криптосистемах с открытым ключом.