Генерация компактных базисов системы остаточных классов
https://doi.org/10.15514/ISPRAS-2025-37(5)-3
Аннотация
Современные вычислительные задачи, связанные с обработкой больших чисел, требуют не только высокой точности, но и значительной скорости операций. В данном контексте применение системы остаточных классов предлагает подход к параллельной обработке больших чисел, который применяется в криптографии, обработке сигналов и искусственных нейронных сетях. Ключевой задачей при построении системы остаточных классов является определение её базиса. В статье представлен алгоритм генерации компактных базисов системы остаточных классов, основанный на теореме Диемитко. Предложенный алгоритм генерирует базисы в среднем на 15,5% быстрее, чем построение базисов на основе псевдо-Мерсенновских чисел, и на 75,7% быстрее, чем метод общей фильтрации. Проведённый сравнительный анализ показал, что использование компактных базисов обеспечивает в среднем 12% ускорение модульных операций по сравнению со специальными наборами модулей.
Ключевые слова
система остаточных классов,
высокопроизводительные вычисления,
специальные наборы модулей,
генерация простых чисел,
криптография.
При поддержке: Исследование выполнено за счет гранта Российского научного фонда № 25-71-30007, https://rscf.ru/project/25-71-30007/.
Об авторах
Владислав Вячеславович ЛУЦЕНКО
Северо-Кавказский федеральный университет
Россия
Россия
Аспирант кафедры вычислительной математики и кибернетики факультета математики и компьютерных наук имени профессора Н.И. Червякова ФГАОУ ВПО «Северо-Кавказский федеральный университет». Сфера научных интересов: высокопроизводительные вычисления, система остаточных классов, умный город, нейронные сети, интернет вещей.
Михаил Григорьевич БАБЕНКО
Северо-Кавказский федеральный университет
Россия
Россия
Доктор физико-математических наук, заведующий кафедры вычислительной математики и кибернетики факультета математики и компьютерных наук имени профессора Н.И. Червякова ФГАОУ ВПО «Северо-Кавказский федеральный университет». Сфера научных интересов: облачные вычисления, высокопроизводительные вычисления, система остаточных классов, нейронные сети, криптография.
Список литературы
1. Sousa L. Nonconventional computer arithmetic circuits, systems and applications. IEEE Circuits Syst. Mag, 2021, vol. 21, no. 1, pp. 6-40.
2. Garner H.L. The residue number system. Papers presented at the the March 3-5, 1959, western joint computer conference. ACM, 1959, pp. 146–153.
3. Луценко В.В., Бабенко М.Г., Хамидов М.М. Высокоскоростной метод перевода чисел из системы остаточных классов в позиционную систему счисления. Труды ИСП РАН, том 36, вып. 4, 2024 г., стр. 117-132. DOI: 10.15514/ISPRAS-2024-36(4)-9. / Lutsenko V.V., Babenko M.G., Khamidov M.M. High speed method of conversion numbers from residue number system to positional notation. Proceedings of the Institute for System Programming of the RAS, 2024, vol. 36, issue 4, pp. 117-132 (in Russian). DOI: 10.15514/ISPRAS-2024-36(4)-9.
4. Луценко В.В., Бабенко М.Г., Черных А.Н., Лапина М.А. Оптимизация алгоритма деления чисел в системе остаточных классов на основе функции ядра Акушского. Труды ИСП РАН, том 35, вып. 5, стр. 157-168. DOI: 10.15514/ISPRAS-2022-35(5)-11. / Lutsenko V.V., Babenko M.G., Tchernykh A.N., Lapina M.A. Optimization of a number division algorithm in the residue number system based on the Akushsky core function. Proceedings of the Institute for System Programming of the RAS, 2023, vol. 35, issue 5, pp. 157-168 (in Russian). DOI: 10.15514/ISPRAS-2022-35(5)-11.
5. Shiriaev E. Kucherov N., Babenko M., Nazarov A. Fast operation of determining the sign of a number in rns using the akushsky core function. Computation, 2023, vol. 11, no. 7, pp. 124.
6. Cardarilli G. C., Nannarelli A., Re M. RNS applications in digital signal processing. Embedded Systems Design with Special Arithmetic and Number Systems, 2017, pp. 181-215.
7. Schoinianakis D. Residue arithmetic systems in cryptography: a survey on modern security applications. Journal of Cryptographic Engineering, 2020, vol. 10, no. 3, pp. 249-267.
8. Nakahara H., Sasao T. A High-speed Low-power Deep Neural Network on an FPGA based on the Nested RNS: Applied to an Object Detector. 2018 IEEE international symposium on circuits and systems (ISCAS). – IEEE, 2018, pp. 1-5.
9. Ananda Mohan P. V. RNS in Cryptography. Residue Number Systems: Theory and Applications. – Cham: Springer International Publishing, 2016, pp. 263-347.
10. Fournaris A. P., Papachristodoulou L., Sklavos N. Secure and efficient rns software implementation for elliptic curve cryptography. 2017 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW). – IEEE, 2017, pp. 86-93.
11. Fournaris A. P., Papachristodoulou L., Batina L., Sklavos N. Secure and efficient RNS approach for elliptic curve cryptography, 2016.
12. Zalekian A., Esmaeildoust M., Kaabi A. Efficient implementation of NTRU cryptography using residue number system. International Journal of Computer Applications, 2015, vol. 124, no. 7.
13. Bajard J. C., Kaihara M., Plantard T. Selected RNS bases for modular multiplication. 2009 19th IEEE Symposium on Computer Arithmetic. – IEEE, 2009, pp. 25-32.
14. Bajard J. C., Fukushima K., Plantard T., Sipasseuth A. Generating very large RNS bases. IEEE Transactions on Emerging Topics in Computing, 2022, vol. 10, no. 3, pp. 1289-1301.
15. Lutsenko V., Zgonnikov M. Investigation of Neural Network Methods for Error Detection and Correction in the Residue Number System. International Workshop on Advanced Information Security Management and Applications. – Cham: Springer Nature Switzerland, 2024, pp. 194-206.
16. Omondi A. R., Premkumar A. B. Residue number systems: theory and implementation. – World Scientific, 2007, vol. 2.
17. Skavantzos A., Abdallah M., Stouraitis T. Large dynamic range RNS systems and their residue to binary converters. Journal of Circuits, Systems, and Computers, 2007, vol. 16, no. 02, pp. 267-286.
18. Molahosseini A. S., Teymouri F., Navi K. A new four-modulus RNS to binary converter. Proceedings of 2010 IEEE International Symposium on Circuits and Systems. – IEEE, 2010, pp. 4161-4164.
19. Lutsenko V.V., Kravtsov M.D., Gorlachev D.E., Mirny N.M. Research of special sets of moduli of the residue number system. Proceedings of the Institute for System Programming of the RAS, 2025, vol. 35, no. 5, pp. 157-168 (in Russian).
20. Kawamura S., Koike M., Sano F., Shimbo A. Cox-rower architecture for fast parallel montgomery multiplication. Advances in Cryptology—EUROCRYPT 2000: International Conference on the Theory and Application of Cryptographic Techniques Bruges, Belgium, May 14–18, 2000 Proceedings 19. Springer Berlin Heidelberg, 2000. pp. 523-538.
21. Diemitko N. Generating multiprecision integer with guaranted primality. Proc. of the SIFIP Int. Conf. on Comp. Sci., IFIP Security 88, Amsterdam, 19-21 May, 1988. pp. 1-8.
Дополнительные файлы
Рецензия
Для цитирования:
ЛУЦЕНКО В.В., БАБЕНКО М.Г. Генерация компактных базисов системы остаточных классов. Труды Института системного программирования РАН. 2025;37(5):43-52. https://doi.org/10.15514/ISPRAS-2025-37(5)-3
For citation:
LUTSENKO V.V., BABENKO M.G. Generating Compact Residue Number Systems Bases. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2025;37(5):43-52. https://doi.org/10.15514/ISPRAS-2025-37(5)-3
Послать статью по эл. почте 