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

А. А. Коляда; Н. А. Коляда; В. В. Ревинский; А. Ф. Чернявский; Е. В. Шабинская

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

А. А. Коляда, Н. А. Коляда, В. В. Ревинский, А. Ф. Чернявский, Е. В. Шабинская

Полный текст:

PDF (Rus) |

сгенерировать QR код

Аннотация

Предлагается новый метод умножения по большим простым модулям в минимально избыточной модулярной системе счисления (МИМСС). Его основу составляют быстросходящаяся рекурсивная схема приведения к остатку (схема спуска Ферма) и высокоскоростной алгоритм масштабирования табличного типа. Исследуются проблемы корректности метода и даются оценки его эффективности. Синтезируется мультипликативный алгоритм, который в сравнении с аналогами позволяет уменьшить количество таблиц для формирования базовых интегральных характеристик на 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. 766776.

3. 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.

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.

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

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

Информатика

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

Полный текст:

Аннотация

Об авторах

Список литературы

Рецензия

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

Логин
Пароль
	Запомнить меня

Войти

Информатика

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

Полный текст:

Аннотация

Об авторах

Список литературы

Рецензия

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

Использование куки-файлов