УМНОЖЕНИЕ ПО БОЛЬШОМУ МОДУЛЮ В МИНИМАЛЬНО ИЗБЫТОЧНОЙ МОДУЛЯРНОЙ СИСТЕМЕ СЧИСЛЕНИЯ С ПРИМЕНЕНИЕМ ОПЕРАЦИЙ МАСШТАБИРОВАНИЯ
Аннотация
Предлагается новый метод умножения по большим простым модулям в минимально избыточной модулярной системе счисления (МИМСС). Его основу составляют быстросходящаяся рекурсивная схема приведения к остатку (схема спуска Ферма) и высокоскоростной алгоритм масштабирования табличного типа. Исследуются проблемы корректности метода и даются оценки его эффективности. Синтезируется мультипликативный алгоритм, который в сравнении с аналогами позволяет уменьшить количество таблиц для формирования базовых интегральных характеристик на 35–40 % и сократить временные затраты как минимум в 1,6 раза.
Об авторах
А. А. Коляда
Институт прикладных физических проблем им. А.Н. Севченко БГУ
Беларусь
Беларусь
Н. А. Коляда
Институт прикладных физических проблем им. А.Н. Севченко БГУ
Беларусь
Беларусь
В. В. Ревинский
Институт прикладных физических проблем им. А.Н. Севченко БГУ
Беларусь
Беларусь
А. Ф. Чернявский
Институт прикладных физических проблем им. А.Н. Севченко БГУ
Беларусь
Беларусь
Е. В. Шабинская
Институт прикладных физических проблем им. А.Н. Севченко БГУ
Беларусь
Беларусь
Список литературы
1. Высокоскоростные методы и системы цифровой обработки информации / А.Ф. Чернявский [и др.]. – Минск : Университетское, 1996. 376 с.
2. 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. 766776.
3. Hiasat, A.A. New efficient structure for a modular multiplier for RNS / A.A. Hiasat // IEEE Trans. Comput. – 2000. – Vol. 49, № 2. – P. 170174.
4. 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.
5. Lee, K.-J. Systolic multiplier for Montgomery’s algorithm / K.-J. Lee, K.-J. Yoo // Integration. – 2002. – Vol. 32, № 1–2. – P. 99–109.
6. RSA speedup with residue number system immune against hardware fault cryptanalysis /
7. S.- M. Yen [et al.] // Lect. Notes Comput. Sci. – 2002. – Vol. 2288. – P. 297–413.
8. 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.
9. 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.
10. 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.
11. 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.
12. Cox-Rower architecture for fast parallel Montgomery multiplication / S. Kawamura [et al.] // Eurocrypt 2000, LNCS. – Berlin, 2000. – Vol. 1807. – P. 523–538.
13. Bajard, J.-C. A Full RNS Implementation of RSA / J.-C. Bajard, L. Imbert // IEEE Trans. Comp. – 2004. – Vol. 53, № 6. – P. 769–774.
14. 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.
15. 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.
16. Евдокимов, А.А. Метод и алгоритм масштабирования для многомашинных и мультипроцессорных систем модулярной обработки информации / А.А. Евдокимов, Н.А. Коляда, В.В. Ревинский // Весцi НАН Беларусi. Сер. фiз.-тэхн. навук. – 2006. – № 1. – С. 104–111.
17. Коляда, А.А. Модулярные структуры конвейерной обработки цифровой информации / А.А. Коляда, И.Т. Пак. – Минск : Университетское, 1992. – 256 с.
18. Устройство для деления чисел в системе остаточных классов : а.с. №1287152 СССР / А.А. Коляда // Открытия. Изобретения. – 1987. – № 4.
19. Устройство для деления чисел : а.с. №1683013 СССР / В.Н. Ахременко, А.А. Коляда, М.Ю. Селянинов // Открытия. Изобретения. – 1991. – № 37.
20. Амербаев, В.М. Теоретические основы машинной арифметики / В.М. Амербаев. – Алма-Ата : Наука, 1976. – 324 c.
21. Устройство для деления чисел в модулярной системе счисления : а.с. №1756887 СССР / В.Н. Ахременко [и др.] // Открытия. Изобретения. – 1992. – № 31.
22. 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.
23. Харин, Ю.С. Компьютерный практикум по математическим методам защиты информации / Ю.С. Харин, С.В. Агиевич. – Mинск : БГУ, 2001. – 190 c.
24. Математические и компьютерные основы криптологии / Ю.С. Харин [и др.]. – Минск : Новое знание, 2003. – 382 с.
25. Коляда, А.А. Общая технология вычисления интегральных характеристик модулярного кода / А.А. Коляда, А.Ф. Чернявский // Доклады НАН Беларуси. – 2008. – T. 52, № 4. – С. 38–44.
26. Функциональные особенности и общие принципы реализации модулярной вычислительной технологии на диапазонах большой мощности / С.М. Завгороднев [и др.] // Электроника инфо. – 2008. – № 12. – С. 50–55.
Рецензия
Для цитирования:
Коляда А.А., Коляда Н.А., Ревинский В.В., Чернявский А.Ф., Шабинская Е.В. УМНОЖЕНИЕ ПО БОЛЬШОМУ МОДУЛЮ В МИНИМАЛЬНО ИЗБЫТОЧНОЙ МОДУЛЯРНОЙ СИСТЕМЕ СЧИСЛЕНИЯ С ПРИМЕНЕНИЕМ ОПЕРАЦИЙ МАСШТАБИРОВАНИЯ. Информатика. 2009;(4(24)):49-65.
Просмотров: 477
Послать статью по эл. почте 