informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-406Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGУМНОЖЕНИЕ ПО БОЛЬШИМ МОДУЛЯМ С ИСПОЛЬЗОВАНИЕМ МИНИМАЛЬНО ИЗБЫТОЧНОЙ МОДУЛЯРНОЙ СХЕМЫ МОНТГОМЕРИКолядаА. А.ЧернявскийА. Ф.Институт прикладных физических проблем им. А.Н. Севченко БГУBelarus20100205201803(27)3148Copyright © Коляда А.А., Чернявский А.Ф., 20182018Коляда А.А., Чернявский А.Ф.Коляда А.А., Чернявский А.Ф.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/406

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

ReferencesИнютин, С.А. Модулярные вычисления в сверхбольших компьютерных диапазонах /Инютин, С.А. Модулярные вычисления в сверхбольших компьютерных диапазонах /С.А. Инютин // Изв. вузов. Электрон. − 2001. − № 6. − С. 65−73.С.А. Инютин // Изв. вузов. Электрон. − 2001. − № 6. − С. 65−73.Инютин, С.А. Основы многоразрядной алгоритмики / С.А. Инютин. − Сургут : РИО,Инютин, С.А. Основы многоразрядной алгоритмики / С.А. Инютин. − Сургут : РИО,– 137 с.– 137 с.Четырехмодульная система модулярной обработки информации для высокоточных вычислений / А.А. Коляда [и др.] // Информатика. − 2008. − № 1 (21). − С. 18−30.Четырехмодульная система модулярной обработки информации для высокоточных вычислений / А.А. Коляда [и др.] // Информатика. − 2008. − № 1 (21). − С. 18−30.Умножение по большому модулю в минимально избыточной модулярной системеУмножение по большому модулю в минимально избыточной модулярной системесчисления с применением операций масштабирования / А.Ф. Чернявский [и др.] // Информатика. − 2009. − № 4 (24). − С. 49−65.счисления с применением операций масштабирования / А.Ф. Чернявский [и др.] // Информатика. − 2009. − № 4 (24). − С. 49−65.Posch, K.S. Modulo reduction in residue number system / K.S. Posch, R. Posch // IEEEPosch, K.S. Modulo reduction in residue number system / K.S. Posch, R. Posch // IEEETrans. on parallel and distributed syst. – 1995. – Vol 6, № 5. – P. 449–454.Trans. on parallel and distributed syst. – 1995. – Vol 6, № 5. – P. 449–454.Schwemmlein, J. RNS-modulo reduction upon a restricted base value set and its applicability to RSA cryptography / J. Schwemmlein, K.S. Posch, R. Posch // Comput. and security. – 1998. – Vol. 17, № 7. – P. 637–650.Schwemmlein, J. RNS-modulo reduction upon a restricted base value set and its applicability to RSA cryptography / J. Schwemmlein, K.S. Posch, R. Posch // Comput. and security. – 1998. – Vol. 17, № 7. – P. 637–650.Bajart, J.-C. An RNS montgomery modular multiplication algorithm / J.-C. Bajart,Bajart, J.-C. An RNS montgomery modular multiplication algorithm / J.-C. Bajart,L.-S. Didier, P. Kornerup // IEEE Trans. Comput. − 1998. − Vol. 47, № 7. – P. 766−776.L.-S. Didier, P. Kornerup // IEEE Trans. Comput. − 1998. − Vol. 47, № 7. – P. 766−776.Hiasat, A.A. New efficient structure for a modular multiplier for RNS / A.A. Hiasat // IEEEHiasat, A.A. New efficient structure for a modular multiplier for RNS / A.A. Hiasat // IEEETrans. Comput. – 2000. – Vol. 49, № 2. – P. 170−174.Trans. Comput. – 2000. – Vol. 49, № 2. – P. 170−174.Cox-Rower architecture for fast parallel Montgomery multiplication / S. Kawamura [et al.] // Eurocrypt 2000, LNCS. – Berlin, 2000. – Vol. 1807. – P. 523–538.Cox-Rower architecture for fast parallel Montgomery multiplication / S. Kawamura [et al.] // Eurocrypt 2000, LNCS. – Berlin, 2000. – Vol. 1807. – P. 523–538.Implementation of RSA Algorithm Based on RNS Montgomery Multiplication / H. NozakiImplementation of RSA Algorithm Based on RNS Montgomery Multiplication / H. Nozaki[et al.] // Proc. Cryptographic Hardware and Embedded Systems (CHES 2001). – USA, 2001. –[et al.] // Proc. Cryptographic Hardware and Embedded Systems (CHES 2001). – USA, 2001. –P. 364–376.P. 364–376.Alia, G. Fast modular exponentiation of large number with large exponents / G. Alia,Alia, G. Fast modular exponentiation of large number with large exponents / G. Alia,E. Martinelli // J. Syst. Archit. – 2002. – Vol. 47, № 14–15. – P. 1079–1088.E. Martinelli // J. Syst. Archit. – 2002. – Vol. 47, № 14–15. – P. 1079–1088.Lee, K.-J. Systolic multiplier for Montgomery’s algorithm / K.-J. Lee, K.-J. Yoo // Integration. – 2002. – Vol. 32, № 1–2. – P. 99–109.Lee, K.-J. Systolic multiplier for Montgomery’s algorithm / K.-J. Lee, K.-J. Yoo // Integration. – 2002. – Vol. 32, № 1–2. – P. 99–109.RSA speedup with residue number system immune against hardware fault cryptanalysis / S.-M. Yen [et al.] // Lect. Notes Comput. Sci. – 2002. – Vol. 2288. – P. 297–413.RSA speedup with residue number system immune against hardware fault cryptanalysis / S.-M. Yen [et al.] // Lect. Notes Comput. Sci. – 2002. – Vol. 2288. – P. 297–413.Bajard, J.-C. A Full RNS Implementation of RSA / J.-C. Bajard, L. Imbert // IEEE Trans.Bajard, J.-C. A Full RNS Implementation of RSA / J.-C. Bajard, L. Imbert // IEEE Trans.Comp. – 2004. – Vol. 53, № 6. – P. 769–774.Comp. – 2004. – Vol. 53, № 6. – P. 769–774.Lim, Z. An RNS-Enhanced microprocessor implementation of public key cryptography /Lim, Z. An RNS-Enhanced microprocessor implementation of public key cryptography /Z. Lim, B.J. Phillips // Signals, Systems and Computers. ACSSC 2007. Conf. Rec. of the forte-first Asilomar Conf. – USA, 2007. – 2007. – P. 1430–1434.Z. Lim, B.J. Phillips // Signals, Systems and Computers. ACSSC 2007. Conf. Rec. of the forte-first Asilomar Conf. – USA, 2007. – 2007. – P. 1430–1434.Коляда, А.А. Модулярные структуры конвейерной обработки цифровой информации / А.А. Коляда, И.Т. Пак. – Минск : Университетское, 1992. – 256 с.Коляда, А.А. Модулярные структуры конвейерной обработки цифровой информации / А.А. Коляда, И.Т. Пак. – Минск : Университетское, 1992. – 256 с.Чернявский, А.Ф. Общая технология вычисления интегральных характеристик модулярного кода / А.Ф. Чернявский, А.А. Коляда // Доклады НАН Беларуси. – 2008. – Т. 52, № 4. – C. 38–44.Чернявский, А.Ф. Общая технология вычисления интегральных характеристик модулярного кода / А.Ф. Чернявский, А.А. Коляда // Доклады НАН Беларуси. – 2008. – Т. 52, № 4. – C. 38–44.Montgomery, P.L. Modular multiplication without trial division / P.L. Montgomery //Montgomery, P.L. Modular multiplication without trial division / P.L. Montgomery //Mathematics of Computation. – 1985. – Vol. 170, № 44. – P. 519–521.Mathematics of Computation. – 1985. – Vol. 170, № 44. – P. 519–521.Харин, Ю.С. Компьютерный практикум по математическим методам защиты инфор-Харин, Ю.С. Компьютерный практикум по математическим методам защиты инфор-мации / Ю.С. Харин, С.В. Агиевич. – Mинск : БГУ, 2001. – 190 c.мации / Ю.С. Харин, С.В. Агиевич. – Mинск : БГУ, 2001. – 190 c.Математические и компьютерные основы криптологии / Ю.С. Харин [и др.] – Минск : Новое знание, 2003. – 382 с.Математические и компьютерные основы криптологии / Ю.С. Харин [и др.] – Минск : Новое знание, 2003. – 382 с.Функциональные особенности и общие принципы реализации модулярной вычислительной технологии на диапазонах большой мощности / С.М. Завгороднев [и др.] // Электроника инфо. – 2008. – № 12. – С. 50–55.Функциональные особенности и общие принципы реализации модулярной вычислительной технологии на диапазонах большой мощности / С.М. Завгороднев [и др.] // Электроника инфо. – 2008. – № 12. – С. 50–55.Чернявский, А.Ф. Умножение по большим простым модулям на основе минимально избыточной модулярной схемы Барретта / А.Ф. Чернявский, А.А. Коляда // Доклады НАН Беларуси. – 2010. – Т. 54, № 2. – С. 40−53.Чернявский, А.Ф. Умножение по большим простым модулям на основе минимально избыточной модулярной схемы Барретта / А.Ф. Чернявский, А.А. Коляда // Доклады НАН Беларуси. – 2010. – Т. 54, № 2. – С. 40−53.

The authors declare that there are no conflicts of interest present.