Умножение по большим модулям методом Монтгомери с применением минимально избыточной модулярной арифметики

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

Умножение по большим модулям методом Монтгомери с применением минимально избыточной модулярной арифметики

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

научная статья Страницы: 3-8

¹ д. т. н., профессор, академик НАН Беларуси, зав. отд. информатики НИИПФП им. А. Н. Севченко БГУ
² д. ф.-м. н., доцент, гл. научн. сотр. лаборатории специализированных вычислительных систем (СВС) НИИПФП им. А. Н. Севченко БГУ
³ научн. сотр. лаборатории СВС НИИПФП им. А. Н. Севченко БГУ
⁴ научн. сотр. лаб. СВС НИИПФП им. А. Н. Севченко БГУ

Ключевые слова: модулярная схема Монтгомери интервально-модульная форма числа

Аннотация

Для синтеза алгоритмов умножения по большим модулям разработана минимально избыточная модулярная схема Монтгомери. В базовой процедуре расширения кода используются интервально-индексные характеристики и интервально-модулярная форма чисел. При однопроцессорной реализации это обеспечивает (3,5−3,6)-кратное повышение производительности в сравнении с лучшим модулярным аналогом (разработкой фирмы Toshiba).

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

Чернявский А.Ф., Коляда А.А., Коляда Н.А., Шабинская Е.В. Умножение по большим модулям методом Монтгомери с применением минимально избыточной модулярной арифметики // Нейрокомпьютеры: разработка, применение. 2010. № 9. С. 3–8.

Список источников

Коляда А. А. и др. Четырехмодульная система модулярной обработки информации для высокоточных вычислений // Информатика. 2008. № 1. С. 18-30.
Чернявский А. Ф.и др. Умножение по большому модулю в минимально избыточной модулярной системе счисления с применением операций масштабирования // Информатика. 2009. № 4. С. 49 - 65.
Чернявский А. Ф., Коляда А. А. Умножение по большим простым модулям на основе минимально избыточной модулярной схемы Барретта // Доклады НАН Беларуси. 2010. Т. 54, № 2. С. 40−53.
Posch, K. S.,Posch, R., Modulo reduction in residue number system // IEEE Trans. on parallel and distributed syst. 1995. V. 6. No. 5. P. 449-454.
Bajart, J.-C., Didier, L.-S., Kornerup, P., An RNS montgomery modular multiplication algorithm // IEEE Trans. Comput. 1998. V. 47, No. 7. P. 766-776.
Hiasat, A. A., New efficient structure for a modular multiplier for RNS // IEEE Trans. Comput. 2000. V. 49. No. 2. P. 170-174.
Kawamura, S. Cox-Rower architecture for fast parallel Montgomery multiplication / Shinichi Kawamura // Eurocrypt 2000. LNCS. 2000. V. 1807. Berlin. P. 523-538.
Lee, K.-J., Yoo, K.-J., Systolic multiplier for Montgomery-s algorithm // Integration. 2002. V. 32, No. 1-2. P. 99-109.
Bajard, J.-C., Imbert, L., A Full RNS Implementation of RSA // IEEE Trans. Comp. 2004. V. 53, No. 6. P. 769-774.
Коляда А. А., Пак И. Т. Модулярные структуры конвейерной обработки цифровой информации // Минск: Университетское. 1992.
Чернявский А. Ф., Коляда А. А., Общая технология вычисления интегральных характеристик модулярного кода // Доклады НАН Беларуси. 2008. Т. 52. № 4. C. 38-44.
Завгороднев С. М. и др. Функциональные особенности и общие принципы реализации модулярной вычислительной технологии на диапазонах большой мощности // Электроника инфо. 2008. № 12. С. 50-55.

[1] Коляда А. А. и др. Четырехмодульная система модулярной обработки информации для высокоточных вычислений // Информатика. 2008. № 1. С. 18-30.

[2] Чернявский А. Ф.и др. Умножение по большому модулю в минимально избыточной модулярной системе счисления с применением операций масштабирования // Информатика. 2009. № 4. С. 49 - 65.

[3] Чернявский А. Ф., Коляда А. А. Умножение по большим простым модулям на основе минимально избыточной модулярной схемы Барретта // Доклады НАН Беларуси. 2010. Т. 54, № 2. С. 40−53.

[4] Posch, K. S.,Posch, R., Modulo reduction in residue number system // IEEE Trans. on parallel and distributed syst. 1995. V. 6. No. 5. P. 449-454.

[5] Bajart, J.-C., Didier, L.-S., Kornerup, P., An RNS montgomery modular multiplication algorithm // IEEE Trans. Comput. 1998. V. 47, No. 7. P. 766-776.

[6] Hiasat, A. A., New efficient structure for a modular multiplier for RNS // IEEE Trans. Comput. 2000. V. 49. No. 2. P. 170-174.

[7] Kawamura, S. Cox-Rower architecture for fast parallel Montgomery multiplication / Shinichi Kawamura // Eurocrypt 2000. LNCS. 2000. V. 1807. Berlin. P. 523-538.

[8] Lee, K.-J., Yoo, K.-J., Systolic multiplier for Montgomery-s algorithm // Integration. 2002. V. 32, No. 1-2. P. 99-109.

[9] Bajard, J.-C., Imbert, L., A Full RNS Implementation of RSA // IEEE Trans. Comp. 2004. V. 53, No. 6. P. 769-774.

[10] Коляда А. А., Пак И. Т. Модулярные структуры конвейерной обработки цифровой информации // Минск: Университетское. 1992.

[11] Чернявский А. Ф., Коляда А. А., Общая технология вычисления интегральных характеристик модулярного кода // Доклады НАН Беларуси. 2008. Т. 52. № 4. C. 38-44.

[12] Завгороднев С. М. и др. Функциональные особенности и общие принципы реализации модулярной вычислительной технологии на диапазонах большой мощности // Электроника инфо. 2008. № 12. С. 50-55.