Searching of Optimal Weights for the Akushsky Core Function

Vladislav V. Lutsenko
North-Caucasus Federal University

Dmitry E. Gorlacev
North-Caucasus Federal University

Nikita M. Mirny
North-Caucasus Federal University

Mikhail G. Babenko
North-Caucasus Federal University


Abstract


Modern computational tasks involving the processing of large numbers require not only high accuracy but also significant speed. In this context, the use of the residue number system offers an approach to parallel big data processing used in cryptography, signal processing and artificial neural networks. Despite the advantages of the residue number system, its diffusion has been slow due to the computational complexity of the so-called non-modular operations of the residual class system. One of the universal tools for realising non-modular operations is the Akushsky core function. This paper studies the Akushsky core function as a tool for determining the positional characteristic of a number in the residue number system. The application of Monte Carlo method and genetic algorithm is proposed to find the optimal weights of the core function. Experimental results demonstrate that the genetic algorithm provides more stable results when the number of moduli increases, while the Monte Carlo method is effective on small dimensions. The genetic algorithm is on average 38% faster than the Monte Carlo method, making it the preferred choice. Additionally, the computation time of the core function with optimal weights and the Pirlo function were compared. The results showed that the core function with optimal weights is on average 14% faster than the Pirlo function.

Keywords


residue number system; high-performance computing; Akushsky core function; Monte Carlo method; genetic algorithm

References


Schoinianakis D. Residue arithmetic systems in cryptography: a survey on modern security applications. Journal of Cryptographic Engineering. 2020. Vol. 10, no. 3. P. 249–267. DOI: 10.1007/s13389-020-00231-w.

Cardarilli G.C., Nunzio L.D., Fazzolari R. An RNS-based initial absolute position

estimator for Electrical Encoders. IEEE Access. 2023. Vol. 11. P. 98586–98595. DOI: 10.1109/access.2023.3312619.

Mohan P.V.A. Residue number systems: algorithms and architectures. Springer Science & Business Media, 2002.

Omondi A.R., Premkumar A.B. Residue number systems: theory and implementation. World Scientific, 2007. Vol. 2.

Bajard J.C., Eynard J. RNS Approach in Lattice-Based Cryptography. Embedded Systems Design with Special Arithmetic and Number Systems. 2017. P. 345–368. DOI: 10.1007/978-3-319-49742-6_13.

Valueva M.V., Nagornov N.N., Lyakhov P.A., et al. Application of the residue number system to reduce hardware costs of the convolutional neural network implementation. Mathematics and Computers in Simulation. 2020. Vol. 177. P. 232–243. DOI: 10.1016/j.matcom.2020.04.031.

Roohi A., Taheri M.R., Angizi S., et al. Rnsim: Efficient deep neural network accelerator using residue number systems. 2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD). IEEE, 2021. P. 1–9. DOI: 10.1109/iccad51958.2021.9643531.

Lutsenko V., Babenko M., Deryabin M. Construction of Akushsky Core Functions Without Critical Cores. Mathematics. 2024. Vol. 12, no. 21. P. 3399. DOI: 10.3390/math12213399.

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, no. 4. P. 117–132. DOI: 10.15514/ispras-2024-36(4)-9.

Shiriaev E., Kucherov N., Babenko M., et al. Fast operation of determining the sign of a number in RNS using the Akushsky core function. Computation. 2023. Vol. 11, no. 7. P. 124. DOI: 10.3390/computation11070124.

Lutsenko V., Geryugova A., Babenko M., et al. High-Speed Parity Number Detection Algorithm in RNS Based on Akushsky Core Function. International Conference on Communication and Computational Technologies / eds. by S. Kumar, S. Hiranwal, R. Garg, S.D. Purohit. Cham: Springer, Singapore, 2024. P. 491–504. DOI: 10.1007/978-981-97-7423-4_38.

Lutsenko V.V., Babenko M.G., Chernykh A.N., Lapina M.A. Optimization of a number division algorithm in the residue number system based on the Akushsky core function. Proceedings of ISP RAS. 2023. Vol. 35, no. 5. P. 157–168. (in Russian) DOI: 10.15514/ispras-2022-35(5)-11.

Wang Y. Residue-to-binary converters based on new Chinese remainder theorems. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing. 2000. Vol. 47, no. 3. P. 197–205. DOI: 10.1109/82.826745.

Akushskiy I.Ya., Burtsev V.M., Pak I.T. About new positional characteristic of nonpositional code and its application. Theory of Coding and Optimisation of Complex Systems. Alma-Ata, Nauka, KazSSR. 1977. P. 8–16. (in Russian)

Metropolis N., Ulam S. The Monte Carlo method. Journal of the American Statistical Association. 1949. Vol. 44. no. 247. P. 335–341.

Kroese D.P., Brereton T., Taimre T., et al. Why the Monte Carlo method is so important today. Wiley Interdisciplinary Reviews: Computational Statistics. 2014. Vol. 6, no. 6. P. 386–392. DOI: 10.1002/wics.1314.

Shiriaev E., Kucherov N., M Babenko M., et al. Algorithm for determining the optimal weights for the Akushsky core function with an approximate rank. Applied Sciences. 2023. Vol. 13, no. 18. P. 10495. DOI: 10.3390/app131810495.

Kureichik V.M. Genetic algorithms. Izvestiya Yuzhny Federal University. Technical Sciences. 1998. Vol. 8, no. 2. P. 4–7. (in Russian)

Mirjalili S. Evolutionary algorithms and neural networks. Studies in Computational Intelligence. 2019. Vol. 780, no. 1. P. 43–53. DOI: 10.1007/978-3-319-93025-1.

Pirlo G., Impedovo D. A new class of monotone functions of the residue number system. International Journal of Mathematical Models and Methods in Applied Sciences. 2013. Vol. 7, no. 9. P. 802–809.




DOI: http://dx.doi.org/10.14529/cmse250202