УМНОЖЕНИЕ ПО БОЛЬШИМ МОДУЛЯМ С ИСПОЛЬЗОВАНИЕМ МИНИМАЛЬНО ИЗБЫТОЧНОЙ МОДУЛЯРНОЙ СХЕМЫ МОНТГОМЕРИ
Аннотация
Предлагается новый быстрый алгоритм умножения по большому модулю p, реализующий минимально избыточную модулярную схему Монтгомери. Главной отличительной особенностью разработанной схемы является использование интервально-индексных характеристик и интервальномодулярной формы чисел в базовых процедурах расширения кода. Достигаемая за счет этого оптимизация синтезированного мультипликативного алгоритма обеспечивает (3,5−3,6)-кратное повышение производительности в сравнении с наиболее близким лучшим аналогом при выполнении на однопроцессорной ЭВМ. При этом необходимый объем табличной памяти в случае 1024- и 2462-битовых p не превышает соответственно 1,2 и 6,46 Гб. Если пороговые значения размера памяти таблиц для указанных p составляют 141 и 334 Мб, то получаемый выигрыш в быстродействии является двухкратным.
Об авторах
А. А. Коляда
Институт прикладных физических проблем им. А.Н. Севченко БГУ
Беларусь
Беларусь
А. Ф. Чернявский
Институт прикладных физических проблем им. А.Н. Севченко БГУ
Беларусь
Беларусь
Список литературы
1. Инютин, С.А. Модулярные вычисления в сверхбольших компьютерных диапазонах /
2. С.А. Инютин // Изв. вузов. Электрон. − 2001. − № 6. − С. 65−73.
3. Инютин, С.А. Основы многоразрядной алгоритмики / С.А. Инютин. − Сургут : РИО,
4. – 137 с.
5. Четырехмодульная система модулярной обработки информации для высокоточных вычислений / А.А. Коляда [и др.] // Информатика. − 2008. − № 1 (21). − С. 18−30.
6. Умножение по большому модулю в минимально избыточной модулярной системе
7. счисления с применением операций масштабирования / А.Ф. Чернявский [и др.] // Информатика. − 2009. − № 4 (24). − С. 49−65.
8. Posch, K.S. Modulo reduction in residue number system / K.S. Posch, R. Posch // IEEE
9. Trans. on parallel and distributed syst. – 1995. – Vol 6, № 5. – P. 449–454.
10. 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.
11. Bajart, J.-C. An RNS montgomery modular multiplication algorithm / J.-C. Bajart,
12. L.-S. Didier, P. Kornerup // IEEE Trans. Comput. − 1998. − Vol. 47, № 7. – P. 766−776.
13. Hiasat, A.A. New efficient structure for a modular multiplier for RNS / A.A. Hiasat // IEEE
14. Trans. Comput. – 2000. – Vol. 49, № 2. – P. 170−174.
15. Cox-Rower architecture for fast parallel Montgomery multiplication / S. Kawamura [et al.] // Eurocrypt 2000, LNCS. – Berlin, 2000. – Vol. 1807. – P. 523–538.
16. Implementation of RSA Algorithm Based on RNS Montgomery Multiplication / H. Nozaki
17. [et al.] // Proc. Cryptographic Hardware and Embedded Systems (CHES 2001). – USA, 2001. –
18. P. 364–376.
19. Alia, G. Fast modular exponentiation of large number with large exponents / G. Alia,
20. E. Martinelli // J. Syst. Archit. – 2002. – Vol. 47, № 14–15. – P. 1079–1088.
21. Lee, K.-J. Systolic multiplier for Montgomery’s algorithm / K.-J. Lee, K.-J. Yoo // Integration. – 2002. – Vol. 32, № 1–2. – P. 99–109.
22. 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.
23. Bajard, J.-C. A Full RNS Implementation of RSA / J.-C. Bajard, L. Imbert // IEEE Trans.
24. Comp. – 2004. – Vol. 53, № 6. – P. 769–774.
25. Lim, Z. An RNS-Enhanced microprocessor implementation of public key cryptography /
26. 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.
27. Коляда, А.А. Модулярные структуры конвейерной обработки цифровой информации / А.А. Коляда, И.Т. Пак. – Минск : Университетское, 1992. – 256 с.
28. Чернявский, А.Ф. Общая технология вычисления интегральных характеристик модулярного кода / А.Ф. Чернявский, А.А. Коляда // Доклады НАН Беларуси. – 2008. – Т. 52, № 4. – C. 38–44.
29. Montgomery, P.L. Modular multiplication without trial division / P.L. Montgomery //
30. Mathematics of Computation. – 1985. – Vol. 170, № 44. – P. 519–521.
31. Харин, Ю.С. Компьютерный практикум по математическим методам защиты инфор-
32. мации / Ю.С. Харин, С.В. Агиевич. – Mинск : БГУ, 2001. – 190 c.
33. Математические и компьютерные основы криптологии / Ю.С. Харин [и др.] – Минск : Новое знание, 2003. – 382 с.
34. Функциональные особенности и общие принципы реализации модулярной вычислительной технологии на диапазонах большой мощности / С.М. Завгороднев [и др.] // Электроника инфо. – 2008. – № 12. – С. 50–55.
35. Чернявский, А.Ф. Умножение по большим простым модулям на основе минимально избыточной модулярной схемы Барретта / А.Ф. Чернявский, А.А. Коляда // Доклады НАН Беларуси. – 2010. – Т. 54, № 2. – С. 40−53.
Рецензия
Для цитирования:
Коляда А.А., Чернявский А.Ф. УМНОЖЕНИЕ ПО БОЛЬШИМ МОДУЛЯМ С ИСПОЛЬЗОВАНИЕМ МИНИМАЛЬНО ИЗБЫТОЧНОЙ МОДУЛЯРНОЙ СХЕМЫ МОНТГОМЕРИ. Информатика. 2010;(3(27)):31-48.
Просмотров: 664
Послать статью по эл. почте 