Preview

Информатика

Расширенный поиск

УМНОЖЕНИЕ ПО БОЛЬШИМ МОДУЛЯМ С ИСПОЛЬЗОВАНИЕМ МИНИМАЛЬНО ИЗБЫТОЧНОЙ МОДУЛЯРНОЙ СХЕМЫ МОНТГОМЕРИ

Аннотация

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

Для цитирования:


Коляда А.А., Чернявский А.Ф. УМНОЖЕНИЕ ПО БОЛЬШИМ МОДУЛЯМ С ИСПОЛЬЗОВАНИЕМ МИНИМАЛЬНО ИЗБЫТОЧНОЙ МОДУЛЯРНОЙ СХЕМЫ МОНТГОМЕРИ. Информатика. 2010;(3(27)):31-48.

Просмотров: 690


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)