1. Белорусский государственный университет Минск
2. Институт прикладных физических проблем Минск, Курчатова, 7

УДК: 681.301

Реферат:

Предлагается новый быстрый алгоритм умножения по большому модулю p, реализующий минимально избыточную модулярную схему Монтгомери. Главной отличительной особенностью разработанной схемы является использование интервально-индексных характеристик и интервально-модулярной формы чисел в базовых процедурах расширения кода. Достигаемая за счет этого оптими-зация синтезированного мультипликативного алгоритма обеспечивает (3,5?3,6)-кратное повышение производительности в сравнении с наиболее близким лучшим аналогом при выполнении на однопроцес-сорной ЭВМ. При этом необходимый объем табличной памяти в случае 1024- и 2462-битовых p не пре-вышает соответственно 1,2 и 6,46 Гб. Если пороговые значения размера памяти таблиц для указан-ных p составляют 141 и 334 Мб, то получаемый выигрыш в быстродействии является двухкратным.