Preview

Informatics

Advanced search

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

Abstract

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

For citations:


 ,   . Informatics. 2010;(3(27)):31-48. (In Russ.)

Views: 679


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


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