informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-532Research ArticleПАРАЛЛЕЛЬНЫЕ АРХИТЕКТУРЫ И ВЫЧИСЛЕНИЯPARALLEL ARCHITECTURES AND COMPUTINGУМНОЖЕНИЕ ПО БОЛЬШОМУ МОДУЛЮ В МИНИМАЛЬНО ИЗБЫТОЧНОЙ МОДУЛЯРНОЙ СИСТЕМЕ СЧИСЛЕНИЯ С ПРИМЕНЕНИЕМ ОПЕРАЦИЙ МАСШТАБИРОВАНИЯКолядаА. А.КолядаН. А.РевинскийВ. В.ЧернявскийА. Ф.ШабинскаяЕ. В.Институт прикладных физических проблем им. А.Н. Севченко БГУBelarus20092410201804(24)4965Copyright © Коляда А.А., Коляда Н.А., Ревинский В.В., Чернявский А.Ф., Шабинская Е.В., 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/532

Предлагается новый метод умножения по большим простым модулям в минимально избыточной модулярной системе счисления (МИМСС). Его основу составляют быстросходящаяся рекурсивная схема приведения к остатку (схема спуска Ферма) и высокоскоростной алгоритм масштабирования табличного типа. Исследуются проблемы корректности метода и даются оценки его эффективности. Синтезируется мультипликативный алгоритм, который в сравнении с аналогами позволяет уменьшить количество таблиц для формирования базовых интегральных характеристик на 35–40 % и сократить временные затраты как минимум в 1,6  раза.

ReferencesВысокоскоростные методы и системы цифровой обработки информации / А.Ф. Чернявский [и др.]. – Минск : Университетское, 1996.  376 с.Высокоскоростные методы и системы цифровой обработки информации / А.Ф. Чернявский [и др.]. – Минск : Университетское, 1996.  376 с.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.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.Hiasat, A.A. New efficient structure for a modular multiplier for RNS / A.A. Hiasat // IEEE Trans. Comput. – 2000. – Vol. 49, № 2. – P. 170174.Hiasat, A.A. New efficient structure for a modular multiplier for RNS / A.A. Hiasat // IEEE Trans. Comput. – 2000. – Vol. 49, № 2. – P. 170174.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.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.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 /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.S.- M. Yen [et al.] // Lect. Notes Comput. Sci. – 2002. – Vol. 2288. – P. 297–413.Hiasat, A.A. Semi-custo VLSI design an implementation of a new efficient RNS division algorithm / A.A. Hiasat, Z.H. Abdelati // Comput.1. – 1999. – Vol. 42, № 3. – P. 232–240.Hiasat, A.A. Semi-custo VLSI design an implementation of a new efficient RNS division algorithm / A.A. Hiasat, Z.H. Abdelati // Comput.1. – 1999. – Vol. 42, № 3. – P. 232–240.Talahmeh, S. Arithmetic division in RNS using Galois field GF(p) / S. Talahmeh, P. Siy // Comput. Arc. Math. Appl. – 2000. – Vol. 39, № 5–6. – P. 227–238.Talahmeh, S. Arithmetic division in RNS using Galois field GF(p) / S. Talahmeh, P. Siy // Comput. Arc. Math. Appl. – 2000. – Vol. 39, № 5–6. – P. 227–238.Posch, K.S. Modulo reduction in residue number system / K.S. Posch, R. Posch // IEEE Trans. on parallel and distributed syst. – 1995. – Vol. 6, № 5. – P. 449–454.Posch, K.S. Modulo reduction in residue number system / K.S. Posch, R. Posch // IEEE 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.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.Bajard, J.-C. A Full RNS Implementation of RSA / J.-C. Bajard, L. Imbert // IEEE Trans. Comp. – 2004. – Vol. 53, № 6. – P. 769–774.Bajard, J.-C. A Full RNS Implementation of RSA / J.-C. Bajard, L. Imbert // IEEE Trans. Comp. – 2004. – Vol. 53, № 6. – P. 769–774.Shenoy, A.P. Residue to Binary Conversion for RNS Arithmetic Using Only Modular Look-up Tables / A.P. Shenoy, R. Kumaresan // IEEE Trans. on Circuit and Systems. – 1988. – Vol. 35, № 9. – P. 1158–1162.Shenoy, A.P. Residue to Binary Conversion for RNS Arithmetic Using Only Modular Look-up Tables / A.P. Shenoy, R. Kumaresan // IEEE Trans. on Circuit and Systems. – 1988. – Vol. 35, № 9. – P. 1158–1162.Shenoy, A.P. Fast Base Extension Using a Redundant Modulus in RNS / A.P. Shenoy, R. Kumaresan // IEEE Trans. Comput. – 1989. – Vol. 38, № 2. – P. 292–297.Shenoy, A.P. Fast Base Extension Using a Redundant Modulus in RNS / A.P. Shenoy, R. Kumaresan // IEEE Trans. Comput. – 1989. – Vol. 38, № 2. – P. 292–297.Евдокимов, А.А. Метод и алгоритм масштабирования для многомашинных и мультипроцессорных систем модулярной обработки информации / А.А. Евдокимов, Н.А. Коляда, В.В. Ревинский // Весцi НАН Беларусi. Сер. фiз.-тэхн. навук. – 2006. – № 1. – С. 104–111.Евдокимов, А.А. Метод и алгоритм масштабирования для многомашинных и мультипроцессорных систем модулярной обработки информации / А.А. Евдокимов, Н.А. Коляда, В.В. Ревинский // Весцi НАН Беларусi. Сер. фiз.-тэхн. навук. – 2006. – № 1. – С. 104–111.Коляда, А.А. Модулярные структуры конвейерной обработки цифровой информации / А.А. Коляда, И.Т. Пак. – Минск : Университетское, 1992. – 256 с.Коляда, А.А. Модулярные структуры конвейерной обработки цифровой информации / А.А. Коляда, И.Т. Пак. – Минск : Университетское, 1992. – 256 с.Устройство для деления чисел в системе остаточных классов : а.с. №1287152 СССР / А.А. Коляда // Открытия. Изобретения. – 1987. – № 4.Устройство для деления чисел в системе остаточных классов : а.с. №1287152 СССР / А.А. Коляда // Открытия. Изобретения. – 1987. – № 4.Устройство для деления чисел : а.с. №1683013 СССР / В.Н. Ахременко, А.А. Коляда, М.Ю. Селянинов // Открытия. Изобретения. – 1991. – № 37.Устройство для деления чисел : а.с. №1683013 СССР / В.Н. Ахременко, А.А. Коляда, М.Ю. Селянинов // Открытия. Изобретения. – 1991. – № 37.Амербаев, В.М. Теоретические основы машинной арифметики / В.М. Амербаев. – Алма-Ата : Наука, 1976. – 324 c.Амербаев, В.М. Теоретические основы машинной арифметики / В.М. Амербаев. – Алма-Ата : Наука, 1976. – 324 c.Устройство для деления чисел в модулярной системе счисления : а.с. №1756887 СССР / В.Н. Ахременко [и др.] // Открытия. Изобретения. – 1992. – № 31.Устройство для деления чисел в модулярной системе счисления : а.с. №1756887 СССР / В.Н. Ахременко [и др.] // Открытия. Изобретения. – 1992. – № 31.Banerji, D.K. A high-speed division method in residue arithmetic / D.K. Banerji, T.Y. Chueng, V. Ganesan // Proc. 5-th Simp. Comput. Arithmetic. – N.Y., 1981. – P. 158–164.Banerji, D.K. A high-speed division method in residue arithmetic / D.K. Banerji, T.Y. Chueng, V. Ganesan // Proc. 5-th Simp. Comput. Arithmetic. – N.Y., 1981. – P. 158–164.Харин, Ю.С. Компьютерный практикум по математическим методам защиты информации / Ю.С. Харин, С.В. Агиевич. – Mинск : БГУ, 2001. – 190 c.Харин, Ю.С. Компьютерный практикум по математическим методам защиты информации / Ю.С. Харин, С.В. Агиевич. – Mинск : БГУ, 2001. – 190 c.Математические и компьютерные основы криптологии / Ю.С. Харин [и др.]. – Минск : Новое знание, 2003. – 382 с.Математические и компьютерные основы криптологии / Ю.С. Харин [и др.]. – Минск : Новое знание, 2003. – 382 с.Коляда, А.А. Общая технология вычисления интегральных характеристик модулярного кода / А.А. Коляда, А.Ф. Чернявский // Доклады НАН Беларуси. – 2008. – T. 52, № 4. – С. 38–44.Коляда, А.А. Общая технология вычисления интегральных характеристик модулярного кода / А.А. Коляда, А.Ф. Чернявский // Доклады НАН Беларуси. – 2008. – T. 52, № 4. – С. 38–44.Функциональные особенности и общие принципы реализации модулярной вычислительной технологии на диапазонах большой мощности / С.М. Завгороднев [и др.] // Электроника инфо. – 2008. – № 12. – С. 50–55.Функциональные особенности и общие принципы реализации модулярной вычислительной технологии на диапазонах большой мощности / С.М. Завгороднев [и др.] // Электроника инфо. – 2008. – № 12. – С. 50–55.

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